# Parameterized Low-Rank Binary Matrix Approximation

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

## Key facts

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

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

- [Structured Neural Networks for Density Estimation and Causal Inference](https://mlsanity.com/paper/2311.02221/) (2023)
- [Boolean Matrix Factorization via Nonnegative Auxiliary Optimization](https://mlsanity.com/paper/2106.04708/) (2021)
- [Boolean and mathbbFp-Matrix Factorization: From Theory to Practice](https://mlsanity.com/paper/2207.11917/) (2022)
- [Bi-objective Optimization in Role Mining](https://mlsanity.com/paper/2403.16757/) (2024)
- [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 number of algorithmic results for the following family of problems: For a given binary m× n matrix A and integer k, decide whether there is a "simple" binary matrix B which differs from A in at most k entries. For an integer r, the "simplicity" of B is characterized as follows. - Binary r-Means: Matrix B has at most r different columns. This problem is known to be NP-complete already for r=2. We show that the problem is solvable in time 2O(klog k)·(nm)O(1) and thus is fixed-parameter tractable parameterized by k. We prove that the problem admits a polynomial kernel when parameterized by r and k but it has no polynomial kernel when parameterized by k only unless NPsubseteq coNP/poly. We also complement these result by showing that when being parameterized by r and k, the problem admits an algorithm of running time 2^O(r· √klog(k+r))(nm)O(1), which is subexponential in k for r∈ O(k1/2 -ε) for any ε>0. - Low GF(2)-Rank Approximation: Matrix B is of GF(2)-rank at most r. This problem is known to be NP-complete already for r=1. It also known to be W[1]-hard when parameterized by k. Interestingly, when parameterized by r and k, the problem is not only fixed-parameter tractable, but it is solvable in time 2^O(r 3/2· √klogk)(nm)O(1), which is subexponential in k. - Low Boolean-Rank Approximation: Matrix B is of Boolean rank at most r. The problem is known to be NP-complete for k=0 as well as for r=1. We show that it is solvable in subexponential in k time 2^O(r2r· √klog k)(nm)O(1).