Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.18717 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912883307184128 |
|---|---|
| author | Chen, Tyler Huber, Caroline Lin, Ethan Zaid, Hajar |
| author_facet | Chen, Tyler Huber, Caroline Lin, Ethan Zaid, Hajar |
| contents | We describe a randomized variant of the block conjugate gradient method for solving a single positive-definite linear system of equations. Our method provably outperforms preconditioned conjugate gradient with a broad-class of Nyström-based preconditioners, without ever explicitly constructing a preconditioner. In analyzing our algorithm, we derive theoretical guarantees for new variants of Nyström preconditioned conjugate gradient which may be of separate interest. We also describe how our approach yields state-of-the-art algorithms for key data-science tasks such as computing the entire ridge regression regularization path and generating multiple independent samples from a high-dimensional Gaussian distribution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_18717 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Preconditioning without a preconditioner: faster ridge-regression and Gaussian sampling with randomized block Krylov subspace methods Chen, Tyler Huber, Caroline Lin, Ethan Zaid, Hajar Numerical Analysis We describe a randomized variant of the block conjugate gradient method for solving a single positive-definite linear system of equations. Our method provably outperforms preconditioned conjugate gradient with a broad-class of Nyström-based preconditioners, without ever explicitly constructing a preconditioner. In analyzing our algorithm, we derive theoretical guarantees for new variants of Nyström preconditioned conjugate gradient which may be of separate interest. We also describe how our approach yields state-of-the-art algorithms for key data-science tasks such as computing the entire ridge regression regularization path and generating multiple independent samples from a high-dimensional Gaussian distribution. |
| title | Preconditioning without a preconditioner: faster ridge-regression and Gaussian sampling with randomized block Krylov subspace methods |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2501.18717 |