Matrix factorization with Binary Components

Abstract

Motivated by an application in computational biology, we consider low-rank matrix factorization with $\{0,1\}$-constraints on one of the factors and optionally convex constraints on the second one. In addition to the non-convexity shared with other matrix factorization schemes, our problem is further complicated by a combinatorial constraint set of size $2^{m\cdot 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 $O(mr{2}^r+mnr+r^{2}n)$ operations for $n$ datapoints. To obtain this result, we use theory around the Littlewood-Offord lemma from combinatorics.

appeared in NIPS 2013

References in corpus (2)

• Factoring nonnegative matrices with linear programs
• Convex Sparse Matrix Factorizations

Cited by in corpus (3)

• Learning Binary Latent Variable Models: A Tensor Eigenpair Approach
• Matrix Completion and Performance Guarantees for Single Individual Haplotyping
• Binary Matrix Factorization via Dictionary Learning