Convergence rates of randomly pivoted methods for low-rank approximation

Ryan Divan, Marc Aurèle Gilles

Randomly pivoted Cholesky, QR, and LU are iterative algorithms that form structured low-rank approximations of a matrix by sampling columns, or rows and columns, from the residual.…