Boolean factor analysis is the task of decomposing a Binary matrix to the Boolean product of two binary factors. This unsupervised data-analysis approach is desirable due to its interpretability, but hard to perform due its NP-hardness. A closely related problem is low-rank Boolean matrix completion from noisy observations. We treat these problems as maximum a posteriori inference problems, and present message passing solutions that scale 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 outperform existing techniques in real-world applications, such as large-scale binary valued collaborative filtering tasks.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.