Low Rank Approximation with Entrywise $\ell_1$-Norm Error
  We study the $\ell_1$-low rank approximation problem, where for a given $n
\times d$ matrix $A$ and approximation factor $\alpha \geq 1$, the goal is to
output a rank-$k$ matrix $\widehat{A}$ for which
  $$\|A-\widehat{A}\|_1 \leq \alpha \cdot \min_{\textrm{rank-}k\textrm{
matrices}~A'}\|A-A'\|_1,$$ where for an $n \times d$ matrix $C$, we let
$\|C\|_1 = \sum_{i=1}^n \sum_{j=1}^d |C_{i,j}|$. This error measure is known to
be more robust than the Frobenius norm in the presence of outliers and is
indicated in models where Gaussian assumptions on the noise may not apply. The
problem was shown to be NP-hard by Gillis and Vavasis and a number of
heuristics have been proposed. It was asked in multiple places if there are any
approximation algorithms.
  We give the first provable approximation algorithms for $\ell_1$-low rank
approximation, showing that it is possible to achieve approximation factor
$\alpha = (\log d) \cdot \mathrm{poly}(k)$ in $\mathrm{nnz}(A) + (n+d)
\mathrm{poly}(k)$ time, where $\mathrm{nnz}(A)$ denotes the number of non-zero
entries of $A$. If $k$ is constant, we further improve the approximation ratio
to $O(1)$ with a $\mathrm{poly}(nd)$-time algorithm. Under the Exponential Time
Hypothesis, we show there is no $\mathrm{poly}(nd)$-time algorithm achieving a
$(1+\frac{1}{\log^{1+\gamma}(nd)})$-approximation, for $\gamma > 0$ an
arbitrarily small constant, even when $k = 1$.
  We give a number of additional results for $\ell_1$-low rank approximation:
nearly tight upper and lower bounds for column subset selection, CUR
decompositions, extensions to low rank approximation with respect to
$\ell_p$-norms for $1 \leq p < 2$ and earthmover distance, low-communication
distributed protocols and low-memory streaming algorithms, algorithms with
limited randomness, and bicriteria algorithms. We also give a preliminary
empirical evaluation.
