Timezone: »

 
Poster
Faster Algorithms for Binary Matrix Factorization
Ravi Kumar · Rina Panigrahy · Ali Rahimi · David Woodruff

Thu Jun 13 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #144
in Posters Thu »
We give faster approximation algorithms for well-studied variants of Binary Matrix Factorization (BMF), where we are given a binary $m \times n$ matrix $A$ and would like to find binary rank-$k$ matrices $U, V$ to minimize the Frobenius norm of $U \cdot V - A$. In the first setting, $U \cdot V$ denotes multiplication over $\mathbb{Z}$, and we give a constant-factor approximation algorithm that runs in $2^{O(k^2 \log k)} \textrm{poly}(mn)$ time, improving upon the previous $\min(2^{2^k}, 2^n) \textrm{poly}(mn)$ time. Our techniques generalize to minimizing $\|U \cdot V - A\|_p$ for $p \geq 1$, in $2^{O(k^{\lceil p/2 \rceil + 1}\log k)} \textrm{poly}(mn)$ time. For $p = 1$, this has a graph-theoretic consequence, namely, a $2^{O(k^2)} \poly(mn)$-time algorithm to approximate a graph as a union of disjoint bicliques. In the second setting, $U \cdot V$ is over $\GF(2)$, and we give a bicriteria constant-factor approximation algorithm that runs in $2^{O(k^3)} \poly(mn)$ time to find binary rank-$O(k \log m)$ matrices $U$, $V$ whose cost is as good as the best rank-$k$ approximation, improving upon $\min(2^{2^k}mn, \min(m,n)^{k^{O(1)}} \textrm{poly}(mn))$ time.
Keywords: Dimensionality Reduction · Matrix Factorization · Randomized Linear Algebra

Author Information

Ravi Kumar (Google)
Rina Panigrahy (Google)
Ali Rahimi (Google)
David Woodruff (Carnegie Mellon University)

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

More from the Same Authors