Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929552364666880 |
|---|---|
| author | Chen, Yifan Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. |
| author_facet | Chen, Yifan Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. |
| contents | The randomly pivoted partial Cholesky algorithm (RPCholesky) computes a factorized rank-k approximation of an N x N positive-semidefinite (psd) matrix. RPCholesky requires only (k + 1) N entry evaluations and O(k^2 N) additional arithmetic operations, and it can be implemented with just a few lines of code. The method is particularly useful for approximating a kernel matrix.
This paper offers a thorough new investigation of the empirical and theoretical behavior of this fundamental algorithm. For matrix approximation problems that arise in scientific machine learning, experiments show that RPCholesky matches or beats the performance of alternative algorithms. Moreover, RPCholesky provably returns low-rank approximations that are nearly optimal. The simplicity, effectiveness, and robustness of RPCholesky strongly support its use in scientific computing and machine learning applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_06503 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations Chen, Yifan Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. Numerical Analysis Machine Learning 65F55, 65C99, 68T05 The randomly pivoted partial Cholesky algorithm (RPCholesky) computes a factorized rank-k approximation of an N x N positive-semidefinite (psd) matrix. RPCholesky requires only (k + 1) N entry evaluations and O(k^2 N) additional arithmetic operations, and it can be implemented with just a few lines of code. The method is particularly useful for approximating a kernel matrix. This paper offers a thorough new investigation of the empirical and theoretical behavior of this fundamental algorithm. For matrix approximation problems that arise in scientific machine learning, experiments show that RPCholesky matches or beats the performance of alternative algorithms. Moreover, RPCholesky provably returns low-rank approximations that are nearly optimal. The simplicity, effectiveness, and robustness of RPCholesky strongly support its use in scientific computing and machine learning applications. |
| title | Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations |
| topic | Numerical Analysis Machine Learning 65F55, 65C99, 68T05 |
| url | https://arxiv.org/abs/2207.06503 |