2014/12/01 by Michael B. Cohen, Richard Peng, Cohen, Michael B. +1 · 3 citations
Computer Science · Engineering · Mathematics · #Blind Source Separation Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Probability (math.PR) #Sparse and Compressive Sensing Techniques #cs.DS #math.PR
paper · pdf · doi:10.48550/arxiv.1412.0588
arxiv created 2014/12/01 · openalex publication_date 2014/12/01 · arxiv updated 2014/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \boldsymbolA, we find with high probability and in input sparsity time an \boldsymbolA' consisting of about d logd rescaled rows of \boldsymbolA such that ‖ \boldsymbolA \boldsymbolx ‖1 is close to ‖ \boldsymbolA' \boldsymbolx ‖1 for all vectors \boldsymbolx. We also show similar results for all ℓ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 ℓ1.