![Algorithmic Spectral Graph Theory_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Algorithmic%20Spectral%20Graph%20Theory_hi-res.jpg?h=bc58dfd7&itok=8NAdfoPF)
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.