A new analysis of the randomly pivoted Cholesky algorithm

Abstract

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+\epsilon$ factor of the optimal rank-$r$ approximation in $\mathcal{O}(r/\epsilon +r\sqrt{\log r})$ steps. This result nearly matches the optimal complexity $\Theta (r/\epsilon )$ 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.

12 pages, 1 figure