Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913779392970752 |
|---|---|
| author | Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. |
| author_facet | Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_03969 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. Numerical Analysis Computation Machine Learning 65F55, 65C99, 68T05 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. |
| title | Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky |
| topic | Numerical Analysis Computation Machine Learning 65F55, 65C99, 68T05 |
| url | https://arxiv.org/abs/2410.03969 |