Computing Lewis Weights to High Precision by Fixed-Point Iteration

Abstract

The ${\ell }_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\ge 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 $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ partitioned into row blocks ${\mathbf{A}}_{[1]},\dots ,{\mathbf{A}}_{[k]}$, we compute, for $p>2$, coordinatewise $\epsilon$-approximate ${\ell }_p$ block Lewis weights in $O\left(p\log \frac{p\sqrt{{\sum }_{i=1}^k\mathrm{rank}({\mathbf{A}}_{[i]})}}{\epsilon }\right)$ rounds of exact leverage-score-vector computations. For ordinary Lewis weights, this becomes $O\left(p\log \frac{p\sqrt{m}}{\epsilon }\right)$, improving the $O\left(p^2\log (m/\epsilon )\right)$ bound of Gribling, Sidford, and Zhang [GSZ26] for $p\ge 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-\frac{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.

arXiv comment25 pages, 8 figures; v2 primarily adds Theorem 1.5, concurrent work citation, and code for experiments