# Randomly Pivoted Partial Cholesky: Random How?

arXiv: https://arxiv.org/abs/2404.11487 · HTML: https://mlsanity.com/paper/2404.11487/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 7 references that are in the map.
- First posted on arXiv 17 Apr 2024.

## Builds on (most cited first, 2 of 2)

- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)

## Built on by (most cited first, 1 of 1)

- [Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2505.11638/) (2025)

## Abstract (arXiv)

We consider the problem of finding good low rank approximations of symmetric, positive-definite A ∈ ℝn × n. Chen-Epperly-Tropp-Webber showed, among many other things, that the randomly pivoted partial Cholesky algorithm that chooses the i-th row with probability proportional to the diagonal entry Aii leads to a universal contraction of the trace norm (the Schatten 1-norm) in expectation for each step. We show that if one chooses the i-th row with likelihood proportional to Aii2 one obtains the same result in the Frobenius norm (the Schatten 2-norm). Implications for the greedy pivoting rule and pivot selection strategies are discussed.