Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky

Understand

Randomly pivoted Cholesky (RPCholesky) is an algorithm for constructing a low-rank approximation of a positive-semidefinite matrix using a small number of columns.

• This paper develops an accelerated version of RPCholesky that employs block matrix computations and rejection sampling to efficiently simulate the execution of the original algorithm.
• For the task of approximating a kernel matrix, the accelerated algorithm can run over $40\times$ faster.
• The paper contains implementation details, theoretical guarantees, experiments on benchmark data sets, and an application to computational chemistry.