Abstract:
We introduce efficient -approximation algorithms for the binary matrix factorization (BMF) problem, where the inputs are a matrix , a rank parameter , as well as an accuracy parameter , and the goal is to approximate as a product of low-rank factors and . Equivalently, we want to find and that minimize the Frobenius loss . Before this work, the state-of-the-art for this problem was the approximation algorithm of Kumar et. al. [ICML 2019], which achieves a -approximation for some constant . We give the first -approximation algorithm using running time singly exponential in , where is typically a small integer. Our techniques generalize to other common variants of the BMF problem, admitting bicriteria -approximation algorithms for loss functions and the setting where matrix operations are performed in . Our approach can be implemented in standard big data models, such as the streaming or distributed models.
Chat is not available.