ABSTRACT:

We give an algorithm that efficiently samples the rows of a matrix while preserving the L_1-norm of its product with vectors. Given an n-by-d matrix A, we find with high probability and in input sparsity time A' consisting of about dlogd rescaled rows of A such that |Ax|_1
is close to |A’x|_1 for all vectors x. We also show similar results giving nearly optimal sample bounds for all L_p-norms.

Our results are based on sampling by ``Lewis weights'', which can be viewed as generalizations of statistical leverage scores to non-linear settings. We also give an elementary proof of an L_1 matrix concentration bound that governs the convergence of this sampling
process.
Joint work with Michael Cohen