Optimal pivot count for RPCholesky trace approximation
Let $A \in \mathbb{C}^{n \times n}$ be Hermitian positive semidefinite, with eigenvalues $\lambda_1(A) \ge \cdots \ge \lambda_n(A) \ge 0$, and let $\tau_r(A) = \sum_{j > r} \lambda_j(A)$. Randomly pivoted Cholesky (RPCholesky), in exact arithmetic, produces residuals $R_0 = A, R_1, R_2, \dots$: given $R_t \ne 0$, it picks an index $j$ with probability $(R_t)_{jj}/\operatorname{tr}(R_t)$ and sets $$R_{t+1} = R_t - \frac{R_t(:,j)\,R_t(j,:)}{(R_t)_{jj}},$$ and once a residual is zero all later ones are zero. Expectations are over the random pivots. Epperly proved $\mathbb{E}\operatorname{tr}(R_k) \le (1 + \varepsilon)\tau_r(A)$ for $0 < \varepsilon < 1$ and every $k \ge r/\varepsilon + 2r\sqrt{\log r} + r\log(1/\varepsilon) + 2.3r$, and noted that every method that builds its approximation by such partial Cholesky steps needs at least $r/\varepsilon$ steps on some inputs to achieve this guarantee.
Problem. Is there a constant $C \ge 1$ such that $$\mathbb{E}\operatorname{tr}(R_k) \le (1 + \varepsilon)\,\tau_r(A), \qquad k = \min\{n, \lceil Cr/\varepsilon \rceil\},$$ for every $n \ge 1$, every Hermitian positive semidefinite $A \in \mathbb{C}^{n \times n}$, every integer $1 \le r \le n$ and every $0 < \varepsilon < 1$?
Source: Epperly (2026), §1.2, the conjecture after (1.5) that O(r/ε) steps suffice; made precise by OpenProblemsInNLA (a constant C ≥ 1, k = min{n, ⌈Cr/ε⌉}, 0 < ε < 1).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- low-rank approximations, Nyström approximations, OpenProblemsInNLA, pivoted Cholesky factorizations
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@misc{epperly2026,
author = {Epperly, Ethan N. W.},
title = {A new analysis of the randomly pivoted {C}holesky algorithm},
year = {2026},
eprint = {2608.20633},
archivePrefix = {arXiv},
}
@article{chen2025,
author = {Chen, Yifan and Epperly, Ethan N. and Tropp, Joel A. and Webber, Robert J.},
title = {Randomly pivoted {C}holesky: Practical approximation of a kernel matrix with few entry evaluations},
journal = {Comm. Pure Appl. Math.},
volume = {78},
number = {5},
year = {2025},
pages = {995--1041},
doi = {10.1002/cpa.22234},
eprint = {2207.06503},
archivePrefix = {arXiv},
}
@phdthesis{epperly2025,
author = {Epperly, Ethan N.},
title = {Make the Most of What You Have: Resource-Efficient Randomized Algorithms for Matrix Computations},
school = {California Institute of Technology},
year = {2025},
doi = {10.7907/pef3-mg80},
eprint = {2512.15929},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ra01,
author = {Townsend, Alex},
title = {{RA-01}: Optimal pivot count for RPCholesky trace approximation},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/randomized-and-low-rank-approximation/RA-01/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Resolution claims
We establish the expected relative-error guarantee of randomly pivoted Cholesky at $\lceil Cr/\varepsilon\rceil$ pivots with the explicit constant $C=3$ when the eigenvalues after the target rank lie below a half-geometric envelope, and with $C=4$ under an inverse-square tail envelope. The leading eigenvalues may have arbitrarily large spread, and all eigenvectors are unrestricted. A further theorem gives a rank-independent constant for …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Tail-envelope guarantees and a clock obstruction v1 recorded from OpenProblemsInNLA @ eb7c9d6, holden-ra01-2026-09-13/report.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00169, "Optimal pivot count for RPCholesky trace approximation", clopen.solutions.