- Joel Tropp , California Institute of Technology
- Randomly pivoted Cholesky: Addressing the challenges of large-scale kernel computations
- 05/24/2023
- 2:30 PM - 3:30 PM
- 1502 Engineering Building
(Virtual Meeting Link)
- Mark A Iwen ()
**Both in person (CMSE conference room 1502/1503) and on zoom (password the smallest prime > 100).**
Kernel methods are used for prediction and clustering in many data science and scientific computing applications, but applying kernel methods to a large number of data points N is expensive due to the high cost of manipulating the N x N kernel matrix. A basic approach for speeding up kernel computations is low-rank approximation, in which we replace the kernel matrix A with a factorized approximation that can be stored and manipulated more cheaply. When the kernel matrix A has rapidly decaying eigenvalues, mathematical existence proofs guarantee that A can be accurately approximated using a constant number of columns (without ever looking at the full matrix). Nevertheless, for a long time, designing a practical and provably justified algorithm to select the appropriate columns proved challenging.
This talk introduces Randomly Pivoted Cholesky (RPC), a natural algorithm for approximating an N x N positive-semidefinite matrix using k adaptively sampled columns. RPC can be implemented with just a few lines of code; it requires only (k+1)N entry evaluations and O(k^2 N) additional arithmetic operations. In experiments, RPC matches or improves on the performance of alternative algorithms for low-rank psd approximation. Moreover, RPC provably achieves near-optimal approximation guarantees. The simplicity, effectiveness, and robustness of this algorithm strongly support its use for large-scale kernel computations. This work offers an accessible example of the power of using randomized algorithms for linear algebra computations.
Joint work with Yifan Chen, Ethan Epperly, and Rob Webber. Available at arXiv:2207.06503.
