${\mathrm{\ell }}_p$ Row Sampling by Lewis Weights

We give a simple algorithm to efficiently sample the rows of a matrix while preserving the p-norms of its product with vectors. Given an $n$-by-$d$ matrix $A$, we find with high probability and in input sparsity time an $A^{\mathrm{\prime }}$ consisting of about $d\log d$ rescaled rows of $A$ such that $| \boldsymbol{$A$} \boldsymbol{$x$} |_1$iscloseto$| \boldsymbol{$A$}’ \boldsymbol{$x$} |_1$forallvectors$\boldsymbol{$x$}$. We also show similar results for all ${\mathrm{\ell }}_p$ that give nearly optimal sample bounds in input sparsity time. Our results are based on sampling by “Lewis weights”, which can be viewed as statistical leverage scores of a reweighted matrix. We also give an elementary proof of the guarantees of this sampling process for ${\mathrm{\ell }}_1$.