Matrix factorization with binary components Matrix factorization with binary components
Paper summary This paper discusses a new approach to binary matrix factorization that is motivated by recent developments in non-negative matrix factorization. The goal of the paper is to present an algorithm for finding a factorization of a matrix in the form $D = T A$ where the entries of $T$ are in $\{0,1\}$. Such a model has wide applicability and is of interest to the ML community. The algorithm has provable recovery guarantees in the case of noiseless observations. A modified algorithm is applied to the noisy setting; however, the authors do not establish recovery guarantees. The paper presents an algorithm for low-rank matrix factorization with constraints on one of the factors should be binary. The paper has several novel contributions for this problem. The algorithm guarantees the exact solution with the time complexity of $O(mr2^r+mnr)$, where previous approach (E. Meeds et al., NIPS 2007) uses MCMC algorithm so that it cannot guarantee a global convergence. Under additional assumptions on the binary factor matrix $T$, the uniqueness of $T$ is proved which means that each data point has a unique representation with the columns of $T$. Using Littlewood-Offord lemma, the paper computes a theoretical speed-up factor for their heuristic of the candidate binary vector set reduction step.

Your comment: allows researchers to publish paper summaries that are voted on and ranked!