Approximation Algorithms for $\ell_0$-Low Rank Approximation
This addresses a fundamental problem in computational mathematics and data analysis for scenarios without underlying metrics, offering the first provable guarantees for $k > 1$ and novel sublinear-time results for $k = 1$, though it is incremental relative to prior work on low-rank approximation variants.
The paper tackles the NP-hard $\ell_0$-Low Rank Approximation Problem, which minimizes the number of non-zero entry disagreements in matrix approximation, by providing algorithms that improve running time and approximation factors; for $k > 1$, it achieves a rank $O(k \log(n/k))$ matrix with $\|A'-A\|_0 \leq O(k^2 \log(n/k)) \mathrm{OPT}$ in polynomial time, and for $k = 1$, it gives a $(2+\epsilon)$-approximation in sublinear time, with a $(1+O(\psi))$-approximation for binary matrices.
We study the $\ell_0$-Low Rank Approximation Problem, where the goal is, given an $m \times n$ matrix $A$, to output a rank-$k$ matrix $A'$ for which $\|A'-A\|_0$ is minimized. Here, for a matrix $B$, $\|B\|_0$ denotes the number of its non-zero entries. This NP-hard variant of low rank approximation is natural for problems with no underlying metric, and its goal is to minimize the number of disagreeing data positions. We provide approximation algorithms which significantly improve the running time and approximation factor of previous work. For $k > 1$, we show how to find, in poly$(mn)$ time for every $k$, a rank $O(k \log(n/k))$ matrix $A'$ for which $\|A'-A\|_0 \leq O(k^2 \log(n/k)) \mathrm{OPT}$. To the best of our knowledge, this is the first algorithm with provable guarantees for the $\ell_0$-Low Rank Approximation Problem for $k > 1$, even for bicriteria algorithms. For the well-studied case when $k = 1$, we give a $(2+ε)$-approximation in {\it sublinear time}, which is impossible for other variants of low rank approximation such as for the Frobenius norm. We strengthen this for the well-studied case of binary matrices to obtain a $(1+O(ψ))$-approximation in sublinear time, where $ψ= \mathrm{OPT}/\lVert A\rVert_0$. For small $ψ$, our approximation factor is $1+o(1)$.