Computing Lewis Weights to High Precision by Fixed-Point Iteration

DOI10.48550/arXiv.2609.04338MaRDI QIDQ7285230arXivFDO

Authors Swati Padmanabhan

Publication date 3 September 2026

Published in arXiv

Tldr We show that a direct fixed-point iteration computes high-precision $\ell_p$-Lewis weights, improving for $p\geq4$ over prior optimization-based methods. We analyze this method and achieve a near-optimal number of iterations.

Full work available at URL https://doi.org/10.48550/arXiv.2609.04338

arXiv classification

cs.DSmath.NA

Cites work

• _p row sampling by Lewis weights
• A unified framework for approximating and clustering data
• Active linear regression for _p norms and beyond
• Determinantal point processes in randomized numerical linear algebra
• Fast rectangular matrix multiplication and applications
• Finite dimensional subspaces of $L_{p}$
• Matrix Analysis
• Minimum-volume ellipsoids. Theory and algorithms
• On the sensitivity of shape fitting problems
• Sampling with Barriers: Faster Mixing via Lewis Weights
• Solving Linear Programs with Sqrt(rank) Linear System Solves
• Sparsified Cholesky and multigrid solvers for connection Laplacians
• Sparsifying sums of norms
• Strong self-concordance and sampling
• Sub-sampled Newton Methods with Non-uniform Sampling

This page was built for publication: Computing Lewis Weights to High Precision by Fixed-Point Iteration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7285230)