  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.
