Faster Algorithms for Binary Matrix Factorization
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:35513559, 2019.
Abstract
We give faster approximation algorithms for wellstudied 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 constantfactor 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 graphtheoretic 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 constantfactor 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.
Related Material


