{
  "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\\geq4$, 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]},\\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 $O\\left(p^2\\log(m/\\varepsilon)\\right)$ bound of Gribling, Sidford, and Zhang [GSZ26] for $p\\geq4$. 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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.04338",
  "author_total": 1,
  "authors": [
    {
      "name": "Swati Padmanabhan"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/0294742a65f0s.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.04338",
  "fulltext_url": null,
  "id": "0294742a65f0s",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.04338",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "cs.NA"
    ],
    [
      "arxiv",
      "math.NA"
    ],
    [
      "openalex",
      "1703|Matrix Theory and Algorithms"
    ]
  ],
  "openalex": "W7211888907",
  "pdf_url": "https://arxiv.org/pdf/2609.04338",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-20",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/0294742a65f0s.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:34:08Z",
      "native_id": "2609.04338",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.04338"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.NA",
      "subfield": "numerical-analysis"
    }
  ],
  "title": "Computing Lewis Weights to High Precision by Fixed-Point Iteration",
  "title_text": "Computing Lewis Weights to High Precision by Fixed-Point Iteration",
  "type": "preprint",
  "updated_at": "2026-10-30T12:34:08Z",
  "url": "https://research.draconitic.com/paper/0294742a65f0s",
  "venue": "arXiv",
  "versions": []
}