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.