Boolean Matrix Factorization and Noisy Completion via Message Passing
arXiv:1509.08535
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.
References in corpus (9)
- Message Passing Algorithms for Compressed Sensing
- Bilinear Generalized Approximate Message Passing
- Maximum Weight Matching via Max-Product Belief Propagation
- LDPC Codes for Compressed Sensing
- Phase transitions and sample complexity in Bayes-optimal matrix factorization
- Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction
- NIMFA: A Python Library for Nonnegative Matrix Factorization
- Augmentative Message Passing for Traveling Salesman Problem and Graph Partitioning
- Perturbed Message Passing for Constraint Satisfaction Problems