{"id":"arxiv/2608.20633","url":"https://arxiv.org/abs/2608.20633","tags":["math.NA","cs.DS","stat.CO"],"score":0,"title":"A new analysis of the randomly pivoted Cholesky algorithm","domain":"math.NA","source":"arxiv","authors":["Ethan N. W. Epperly"],"reviews":0,"subject":"math.NA","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-21","reactions":{}}