Metraipolis › archive › dc_e65d0658574d

Convergence rates of randomly pivoted methods for low-rank approximation — arXiv:2609.06287

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.06287
License (as archived)
CC0-1.0
Archived
2026-10-16T14:47:55.648Z
SHA-256 of the archived text
3ff6691f5d5c295fcd86665505bd600316101a236e95429e3bbde93106a987cb
Stable URL of this page
https://metraipolis.com/documento/dc_e65d0658574d

How to cite

Convergence rates of randomly pivoted methods for low-rank approximation — arXiv:2609.06287 — arXiv (en), https://arxiv.org/abs/2609.06287 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e65d0658574d (Metraipolis archive dc_e65d0658574d, sha256 3ff6691f5d5c295fcd86665505bd600316101a236e95429e3bbde93106a987cb)
BibTeX
@misc{dce65d0658574d,
  title = {Convergence rates of randomly pivoted methods for low-rank approximation — arXiv:2609.06287},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.06287},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e65d0658574d; sha256 3ff6691f5d5c295fcd86665505bd600316101a236e95429e3bbde93106a987cb},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06287. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Randomly pivoted Cholesky, QR, and LU are iterative algorithms that form structured low-rank approximations of a matrix by sampling columns, or rows and columns, from the residual. We give convergence rates for these methods that depend on the decay of the singular values of the original matrix. The rates hold, up to a constant, when pivots are drawn from an approximation to the exact distribution. This extra degree of freedom can be used to trade exact sampling for cheaper approximations. We use it to establish rates for variants of randomly pivoted LU, including one that picks pivots using a sketch of the input matrix.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.NA).
Categorie arXiv: Numerical Analysis (math.NA).
Pagina del lavoro: https://arxiv.org/abs/2609.06287 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T14:30:08.694Z dalla pagina https://arxiv.org/catchup/math.NA/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).