Approximation Algorithms for $\ell_0$-Low Rank Approximation
  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+\epsilon)$-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(\psi))$-approximation in sublinear time, where $\psi =
\mathrm{OPT}/\lVert A\rVert_0$. For small $\psi$, our approximation factor is
$1+o(1)$.
