${\ell }_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^{\prime }$ consisting of about $d\log d$ rescaled rows of $A$ such that $\Vert Ax{\Vert }_1$ is close to $\Vert A^{\prime }x{\Vert }_1$ for all vectors $x$. We also show similar results for all ${\ell }_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 ${\ell }_1$.

References in corpus (2)

• OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
• Path Finding I :Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves

Cited by in corpus (5)

• A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
• Efficient Inverse Maintenance and Faster Algorithms for Linear Programming
• Generalized Leverage Score Sampling for Neural Networks
• An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications
• A near-optimal algorithm for approximating the John Ellipsoid