Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations
From MaRDI portal
Publication:6404918
arXiv2207.06503MaRDI QIDQ6404918FDOQ6404918
Authors: Yifan Chen, Ethan N. Epperly, Joel A. Tropp, Robert J. Webber 
Publication date: 13 July 2022
Abstract: Randomly pivoted Cholesky (RPCholesky) is a natural algorithm for computing a rank-k approximation of an N x N positive semidefinite (psd) matrix. RPCholesky 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. This paper offers the first serious investigation of its experimental and theoretical behavior. Empirically, RPCholesky matches or improves on the performance of alternative algorithms for low-rank psd approximation. Furthermore, RPCholesky provably achieves near-optimal approximation guarantees. The simplicity, effectiveness, and robustness of this algorithm strongly support its use in scientific computing and machine learning applications.
Has companion code repository: https://github.com/eepperly/randomly-pivoted-cholesky
Probabilistic methods, stochastic differential equations (65C99) Learning and adaptive systems in artificial intelligence (68T05) Numerical methods for low-rank matrix approximation; matrix compression (65F55)
This page was built for publication: Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404918)
