event
Statistics Seminar - Richard Peng
Primary tabs
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
Status
- Workflow Status:Published
- Created By:Anita Race
- Created:09/23/2015
- Modified By:Fletcher Moore
- Modified:04/13/2017
Categories
Keywords
- No keywords were submitted.
Target Audience