Timezone: »

 
Poster
Matrix factorization with binary components
Martin Slawski · Matthias Hein · Pavlo Lutsik

Fri Dec 06 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
in Poster Session »
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 $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 operations of the order $O(m r 2^r + mnr)$ in the worst case. To obtain that result, we invoke theory centered around a fundamental result in combinatorics, the Littlewood-Offord lemma.
[ PDF] 

Author Information

Martin Slawski (Saarland University)
Matthias Hein (University of Tübingen)
Pavlo Lutsik (Saarland University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors