{"id":"arxiv/2609.04338","url":"https://arxiv.org/abs/2609.04338","tags":["cs.DS","math.NA"],"score":0,"title":"Computing Lewis Weights to High Precision by Fixed-Point Iteration","domain":"cs.DS","source":"arxiv","authors":["Swati Padmanabhan"],"reviews":0,"subject":"cs.DS","summary":"The $\\ell_p$-Lewis weights of a matrix are defined by a fixed-point equation. For $p 2$. For a matrix $\\mathbf{A}\\in\\mathbb{R}^{m\\times n}$ partitioned into row blocks $\\mathbf{A}_{[1]},\\ldots,\\mathbf{A}_{[k]}$, we compute, for $p>2$, coordinatewise $\\varepsilon$-approximate $\\ell_p$ block Lewis weights in $O\\left(p\\log\\frac{p\\sqrt{\\sum_{i=1}^k\\operatorname{rank}(\\mathbf{A}_{[i]})}}{\\varepsilon}\\right)$ rounds of exact leverage-score-vector computations. For ordinary Lewis weights, this becomes $O\\left(p\\log\\frac{p\\sqrt{m}}{\\varepsilon}\\right)$, improving the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-03","reactions":{}}