Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank
  Approximation
  We study the problem of entrywise $\ell_1$ low rank approximation. We give
the first polynomial time column subset selection-based $\ell_1$ low rank
approximation algorithm sampling $\tilde{O}(k)$ columns and achieving an
$\tilde{O}(k^{1/2})$-approximation for any $k$, improving upon the previous
best $\tilde{O}(k)$-approximation and matching a prior lower bound for column
subset selection-based $\ell_1$-low rank approximation which holds for any
$\text{poly}(k)$ number of columns. We extend our results to obtain tight upper
and lower bounds for column subset selection-based $\ell_p$ low rank
approximation for any $1 < p < 2$, closing a long line of work on this problem.
  We next give a $(1 + \varepsilon)$-approximation algorithm for entrywise
$\ell_p$ low rank approximation, for $1 \leq p < 2$, that is not a column
subset selection algorithm. First, we obtain an algorithm which, given a matrix
$A \in \mathbb{R}^{n \times d}$, returns a rank-$k$ matrix $\hat{A}$ in
$2^{\text{poly}(k/\varepsilon)} + \text{poly}(nd)$ running time such that:
$$\|A - \hat{A}\|_p \leq (1 + \varepsilon) \cdot OPT +
\frac{\varepsilon}{\text{poly}(k)}\|A\|_p$$ where $OPT = \min_{A_k \text{ rank
}k} \|A - A_k\|_p$. Using this algorithm, in the same running time we give an
algorithm which obtains error at most $(1 + \varepsilon) \cdot OPT$ and outputs
a matrix of rank at most $3k$ -- these algorithms significantly improve upon
all previous $(1 + \varepsilon)$- and $O(1)$-approximation algorithms for the
$\ell_p$ low rank approximation problem, which required at least
$n^{\text{poly}(k/\varepsilon)}$ or $n^{\text{poly}(k)}$ running time, and
either required strong bit complexity assumptions (our algorithms do not) or
had bicriteria rank $3k$. Finally, we show hardness results which nearly match
our $2^{\text{poly}(k)} + \text{poly}(nd)$ running time and the above additive
error guarantee.
