# Approximation Schemes for Low-Rank Binary Matrix Approximation Problems

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2018.

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

- [Symmetric Sparse Boolean Matrix Factorization and Applications](https://mlsanity.com/paper/2102.01570/) (2021)
- [Boolean Matrix Factorization via Nonnegative Auxiliary Optimization](https://mlsanity.com/paper/2106.04708/) (2021)
- [Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorization](https://mlsanity.com/paper/2306.01869/) (2023)
- [Boolean and mathbbFp-Matrix Factorization: From Theory to Practice](https://mlsanity.com/paper/2207.11917/) (2022)
- [Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity](https://mlsanity.com/paper/2512.03718/) (2025)
- [Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics](https://mlsanity.com/paper/2512.03807/) (2025)

## Abstract (arXiv)

We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constrains. The new constrained clustering problem encompasses a number of problems and by solving it, we obtain the first linear time-approximation schemes for a number of well-studied fundamental problems concerning clustering of binary vectors and low-rank approximation of binary matrices. Among the problems solvable by our approach are textscLow GF(2)-Rank Approximation, textscLow Boolean-Rank Approximation, and various versions of textscBinary Clustering. For example, for textscLow GF(2)-Rank Approximation problem, where for an m× n binary matrix A and integer r>0, we seek for a binary matrix B of GF2 rank at most r such that ℓ0 norm of matrix A-B is minimum, our algorithm, for any ε>0 in time  f(r,ε)· n· m, where f is some computable function, outputs a (1+ε)-approximate solution with probability at least (1-frac1e). Our approximation algorithms substantially improve the running times and approximation factors of previous works. We also give (deterministic) PTASes for these problems running in time n^f(r)frac1ε2log frac1ε, where f is some function depending on the problem. Our algorithm for the constrained clustering problem is based on a novel sampling lemma, which is interesting in its own.