*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: L_p Row Sampling by Lewis Weights
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
