ℓ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 boldsymbolmathitA, we find with high probability and in input sparsity time an boldsymbolmathitA' consisting of about d logd rescaled rows of boldsymbolmathitA such that | boldsymbolmathitA boldsymbolmathitx |1 is close to | boldsymbolmathitA' boldsymbolmathitx |1 for all vectors boldsymbolmathitx. We also show similar results for all ℓ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 ℓ1.