Matrix factorization with binary components

Motivated by an application in computational biology, we consider constrained low-rank matrix factorization problems with {0,1}-constraints on one of the factors. In addition to the the non-convexity shared with more general matrix factorization schemes, our problem is further complicated by a combinatorial constraint set of size 2m⋅r, where m is the dimension of the data points and r the rank of the factorization. Despite apparent intractability, we provide −in the line of recent work on non-negative matrix factorization by Arora et al.~(2012)− an algorithm that provably recovers the underlying factorization in the exact case with operations of the order O(mr2r+mnr) in the worst case. To obtain that result, we invoke theory centered around a fundamental result in combinatorics, the Littlewood-Offord lemma.