Michael Cohen: l_p Row Sampling by Lewis Weights

Abstract:  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' consisting of about d log d rescaled rows of A such that ||A x||_1 is close to ||A' x||_1 for all vectors x.  We also show similar results for all l_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 l_1.

Joint work with Richard Peng.