Computing Lewis Weights to High Precision by Fixed-Point Iteration
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.04338
curl -X POST /api/v1/records/arxiv/2609.04338/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.04338/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'