Metraipolis › archive › dc_bd2c6154b93c
A new analysis of the randomly pivoted Cholesky algorithm — arXiv:2608.20633
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.20633
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T10:44:14.978Z
- SHA-256 of the archived text
e49c12da44dea571e1c366a79fbb70797c01a276a7801d8f134cd2f76d21ae42- Stable URL of this page
https://metraipolis.com/documento/dc_bd2c6154b93c
How to cite
A new analysis of the randomly pivoted Cholesky algorithm — arXiv:2608.20633 — arXiv (en), https://arxiv.org/abs/2608.20633 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bd2c6154b93c (Metraipolis archive dc_bd2c6154b93c, sha256 e49c12da44dea571e1c366a79fbb70797c01a276a7801d8f134cd2f76d21ae42)
BibTeX
@misc{dcbd2c6154b93c,
title = {A new analysis of the randomly pivoted Cholesky algorithm — arXiv:2608.20633},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.20633},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bd2c6154b93c; sha256 e49c12da44dea571e1c366a79fbb70797c01a276a7801d8f134cd2f76d21ae42},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.20633. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The randomly pivoted Cholesky algorithm is one of the leading methods for computing a low-rank approximation to a large positive-semidefinite matrix. However, while it consistently achieves accuracy comparable to or better than competing methods of its type in experiments, its theoretical analysis lags somewhat behind other methods. This paper closes this gap, proving that randomly pivoted Cholesky produces an approximation with expected error within a $1+\varepsilon$ factor of the optimal rank-$r$ approximation in $\mathcal{O}(r/\varepsilon + r\sqrt{\log r})$ steps. This result nearly matches the optimal complexity $\Theta(r/\varepsilon)$ for any low-rank approximation method based on a partial Cholesky decomposition (also known as a column Nyström approximation). The paper also presents bounds on the randomly pivoted Cholesky trace and spectral-norm errors that hold with high probability. The mathematical argument is largely due to GPT 5.6-Sol (Pro), with some refinements by the author.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-24 in math.NA).
Categorie arXiv: Numerical Analysis (math.NA) ; Data Structures and Algorithms (cs.DS); Computation (stat.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.20633 — 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-18T10:38:56.449Z dalla pagina https://arxiv.org/catchup/math.NA/2026-08-24?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).