Randomly Pivoted Partial Cholesky: Random How?

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.