Computing Lewis Weights to High Precision by Fixed-Point Iteration
Abstract
The ℓp-Lewis weights of a matrix are defined by a fixed-point equation. For p<4, Cohen and Peng [CP15] showed that iterating an equivalent rearrangement of this equation computes Lewis weights to high precision; for p≥4, prior high-precision methods instead use optimization-based approaches. We show that the direct Lewis fixed-point iteration, appearing in the thesis of Lee [Lee16], computes Lewis weights to high precision for every p>2. For a matrix A∈ℝm× n partitioned into row blocks A[1],…,A[k], we compute, for p>2, coordinatewise ε-approximate ℓp block Lewis weights in O(plogp√(∑i=1krank(A[i]))/ε) rounds of exact leverage-score-vector computations. For ordinary Lewis weights, this becomes O(plogp√m/ε), improving the O(p2log(m/ε)) bound of Gribling, Sidford, and Zhang [GSZ26] for p≥4. Our guarantees also extend to approximate leverage-score computations. Our main observation is that each direct Lewis update contracts the KL divergence to the true weights by a factor of 1−2/p. We also give an alternate explanation of this contraction through volume sampling and entropic independence. Synthetic experiments closely match our predicted local contraction rates and iteration counts grow approximately linearly with p; real-data experiments illustrate the information-concentration tradeoff of finite-p block Lewis designs.
Related
- Convergence and acceleration of a nonlinear fixed-point iteration for computing the Fitness Centrality of general graphs
- Weights of circle actions on oriented manifolds with isolated fixed points
- Equal Hamming Weights at Fixed Root Order and Applications to Constacyclic MDS Codes
- AIR-LLM: Broadcasting AI Weights over Radio for Memory-Free Edge LLM Inference via RF Computing
- Component-wise accurate fixed point iterations for computing the square root of a singular M-matrix
BibTeX
@misc{padmanabhan2026computing,
title = {{Computing Lewis Weights to High Precision by Fixed-Point Iteration}},
author = {Swati Padmanabhan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.04338},
eprint = {2609.04338},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04338},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Computing Lewis Weights to High Precision by Fixed-Point Iteration
AU - Swati Padmanabhan
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2609.04338
UR - https://arxiv.org/abs/2609.04338
AB - The ℓ_p-Lewis weights of a matrix are defined by a fixed-point equation. For p<4, Cohen and Peng [CP15] showed that iterating an equivalent rearrangement of this equation computes Lewis weights to high precision; for p≥4, prior high-precision methods instead use optimization-based approaches. We show that the direct Lewis fixed-point iteration, appearing in the thesis of Lee [Lee16], computes Lewis weights to high precision for every p>2. For a matrix A∈ℝ^m× n partitioned into row blocks A_[1],…,A_[k], we compute, for p>2, coordinatewise ε-approximate ℓ_p block Lewis weights in O(plogp√(∑_i=1^krank(A_[i]))/ε) rounds of exact leverage-score-vector computations. For ordinary Lewis weights, this becomes O(plogp√m/ε), improving the O(p^2log(m/ε)) bound of Gribling, Sidford, and Zhang [GSZ26] for p≥4. Our guarantees also extend to approximate leverage-score computations. Our main observation is that each direct Lewis update contracts the KL divergence to the true weights by a factor of 1−2/p. We also give an alternate explanation of this contraction through volume sampling and entropic independence. Synthetic experiments closely match our predicted local contraction rates and iteration counts grow approximately linearly with p; real-data experiments illustrate the information-concentration tradeoff of finite-p block Lewis designs.
ER -