# Computing Lewis Weights to High Precision

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2021.

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

- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [Near-optimal Active Regression of Single-Index Models](https://mlsanity.com/paper/2502.18213/) (2025)
- [Sharper Bounds for ℓp Sensitivity Sampling](https://mlsanity.com/paper/2306.00732/) (2023)
- [Computing Approximate ℓp Sensitivities](https://mlsanity.com/paper/2311.04158/) (2023)
- [Deterministic Coreset for Lp Subspace](https://mlsanity.com/paper/2601.00361/) (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 present an algorithm for computing approximate ℓp Lewis weights to high precision. Given a full-rank A ∈ ℝm × n with m ≥ n and a scalar p>2, our algorithm computes ε-approximate ℓp Lewis weights of A in widetildeOp(log(1/ε)) iterations; the cost of each iteration is linear in the input size plus the cost of computing the leverage scores of DA for diagonal D ∈ ℝm × m. Prior to our work, such a computational complexity was known only for p ∈ (0, 4) [CohenPeng2015], and combined with this result, our work yields the first polylogarithmic-depth polynomial-work algorithm for the problem of computing ℓp Lewis weights to high precision for all constant p > 0. An important consequence of this result is also the first polylogarithmic-depth polynomial-work algorithm for computing a nearly optimal self-concordant barrier for a polytope.