Randomly pivoted Cholesky: Simple, effective positive semidefinite low-rank approximation

Ethan Epperly, Caltech
9/6, 2023 at 4:10PM-5PM in 939 Evans (for in-person talks) and https://berkeley.zoom.us/j/98667278310

Low-rank approximation of positive semidefinite matrices is a basic problem in computational mathematics, with many applications to machine learning and scientific computing. Existing approaches for this problem largely fall into two categories: simple, fast, but sometimes inaccurate methods and sophisticated, slower methods with accuracy guarantees. To achieve the best of both worlds, this talk introduces randomly pivoted Cholesky, an algorithm for positive semidefinite low-rank approximation that is simple, fast, and accurate. We demonstrate the effectiveness of randomly pivoted Cholesky for spectral clustering of molecular dynamics data, achieving an order of magnitude lower clustering error than previous methods. We then go on to discuss theoretical guarantees for randomly pivoted Cholesky. Using a matrix concavity argument, we show that randomly pivoted Cholesky has nearly optimal low-rank approximation properties. We conclude by discussing extensions and future prospects for this simple, yet effective, algorithm.