Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorization

We introduce efficient (1+varepsilon)-approximation algorithms for the binary matrix factorization (BMF) problem, where the inputs are a matrix A∈0,1n× d, a rank parameter k>0, as well as an accuracy parameter varepsilon>0, and the goal is to approximate A as a product of low-rank factors U∈0,1n× k and V∈0,1k× d. Equivalently, we want to find U and V that minimize the Frobenius loss |UV - A|F2. Before this work, the state-of-the-art for this problem was the approximation algorithm of Kumar et. al. [ICML 2019], which achieves a C-approximation for some constant C≥ 576. We give the first (1+varepsilon)-approximation algorithm using running time singly exponential in k, where k is typically a small integer. Our techniques generalize to other common variants of the BMF problem, admitting bicriteria (1+varepsilon)-approximation algorithms for Lp loss functions and the setting where matrix operations are performed in mathbbF2. Our approach can be implemented in standard big data models, such as the streaming or distributed models.