# ℓp Row Sampling by Lewis Weights

arXiv: https://arxiv.org/abs/1412.0588 · HTML: https://mlsanity.com/paper/1412.0588/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2014.

## Built on by (most cited first, 8 of 8)

- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Parameterized Hardness of Zonotope Containment and Neural Network Verification](https://mlsanity.com/paper/2509.22849/) (2025)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Efficient Online Inverse Optimization with O(d) Regret](https://mlsanity.com/paper/2609.13440/) (2026)
- [Distribution-Aware Feature Selection for SAEs](https://mlsanity.com/paper/2508.21324/) (2025)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)
- [Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model](https://mlsanity.com/paper/2606.20082/) (2026)

## Abstract (arXiv)

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 boldsymbolmathitA, we find with high probability and in input sparsity time an boldsymbolmathitA' consisting of about d logd rescaled rows of boldsymbolmathitA such that | boldsymbolmathitA boldsymbolmathitx |1 is close to | boldsymbolmathitA' boldsymbolmathitx |1 for all vectors boldsymbolmathitx. 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.