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

arXiv: https://arxiv.org/abs/2306.01869 · HTML: https://mlsanity.com/paper/2306.01869/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 69 references that are in the map.
- First posted on arXiv 2 Jun 2023.

## Builds on (most cited first, 19 of 19)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [Optimal Algorithms for L1-subspace Signal Processing](https://mlsanity.com/paper/1405.6785/) (2014)
- [L1 Regression with Lewis Weights Subsampling](https://mlsanity.com/paper/2105.09433/) (2021)
- [Boolean Matrix Factorization and Noisy Completion via Message Passing](https://mlsanity.com/paper/1509.08535/) (2015)
- [Fast Regression for Structured Inputs](https://mlsanity.com/paper/2203.07557/) (2022)
- [On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation](https://mlsanity.com/paper/1509.09236/) (2015)
- [NIMFA: A Python Library for Nonnegative Matrix Factorization](https://mlsanity.com/paper/1808.01743/) (2018)
- [Regularized Weighted Low Rank Approximation](https://mlsanity.com/paper/1911.06958/) (2019)
- [Approximation Schemes for Low-Rank Binary Matrix Approximation Problems](https://mlsanity.com/paper/1807.07156/) (2018)
- [Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations](https://mlsanity.com/paper/1511.01699/) (2015)
- [Near-Linear Sample Complexity for Lp Polynomial Regression](https://mlsanity.com/paper/2211.06790/) (2022)
- [Symmetric Sparse Boolean Matrix Factorization and Applications](https://mlsanity.com/paper/2102.01570/) (2021)
- [Approximation Algorithms for ℓ0-Low Rank Approximation](https://mlsanity.com/paper/1710.11253/) (2017)
- [Linear Independent Component Analysis over Finite Fields: Algorithms and Bounds](https://mlsanity.com/paper/1809.05815/) (2018)

## Built on by (most cited first, 3 of 3)

- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [Guessing Efficiently for Constrained Subspace Approximation](https://mlsanity.com/paper/2504.20883/) (2025)

## Abstract (arXiv)

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.