Randomly Pivoted Partial Cholesky: Random How?
<|reference_start|>Randomly Pivoted Partial Cholesky: Random How?: We consider the problem of finding good low rank approximations of symmetric, positive-definite $A \in \mathbb{R}^{n \times 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 $A_{ii}$ 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 $A_{ii}^2$ 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.<|reference_end|>
@article{steinerberger2024randomly,
    title={Randomly Pivoted Partial Cholesky: Random How?},
    author={Stefan Steinerberger},
    journal={arXiv preprint arXiv:2404.11487},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.11487},
    primaryClass={math.NA cs.NA stat.ML}
}