Abstract
We give a simple algorithm to efficiently sample the rows of a matrix while preserving the L_1 norm of its product with vectors. Given an n * d matrix A, we find with high probability and in input sparsity time an A' consisting of about d log d 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 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 L_1.
Joint work with Michael Cohen.