# Boolean Matrix Factorization and Noisy Completion via Message Passing

Source: [Boolean Matrix Factorization and Noisy Completion via Message Passing](<https://www.sota2.com/research/paper/68fa528e1e209131ce97be6c>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T11:57:02.264Z

Authors: Siamak Ravanbakhsh, Barnabas Poczos, Russell Greiner

Published: 2015-09-28T23:11:16.000Z

## Abstract

Boolean matrix factorization and Boolean matrix completion from noisy observations are desirable unsupervised data-analysis methods due to their interpretability, but hard to perform due to their NP-hardness. We treat these problems as maximum a posteriori inference problems in a graphical model and present a message passing approach that scales linearly with the number of observations and factors. Our empirical study demonstrates that message passing is able to recover low-rank Boolean matrices, in the boundaries of theoretically possible recovery and compares favorably with state-of-the-art in real-world applications, such collaborative filtering with large-scale Boolean data.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Collaborative Filtering on MovieLens 100k](<https://www.sota2.com/research/sota/collaborative-filtering-on-movielens-100k.md>): Collaborative Filtering; MovieLens 100k; Reconstruction Accuracy: 69.5.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1509.08535>)

[PDF](<https://arxiv.org/pdf/1509.08535.pdf>)