Randomized block-Krylov subspace methods for low-rank approximation of matrix functions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914172064759808 |
|---|---|
| author | Persson, David Chen, Tyler Musco, Christopher |
| author_facet | Persson, David Chen, Tyler Musco, Christopher |
| contents | The randomized SVD is a method to compute an inexpensive, yet accurate, low-rank approximation of a matrix. The algorithm assumes access to the matrix through matrix-vector products (matvecs). Therefore, when we would like to apply the randomized SVD to a matrix function, $f(A)$, one needs to approximate matvecs with $f(A)$ using some other algorithm, which is typically treated as a black-box. Chen and Hallman (SIMAX 2023) argued that, in the common setting where matvecs with $f(A)$ are approximated using Krylov subspace methods (KSMs), a more efficient low-rank approximation is possible if we open this black-box. They present an alternative approach that significantly outperforms the naive combination of KSMs with the randomized SVD, although the method lacked theoretical justification. In this work, we take a closer look at the method, and provide strong and intuitive error bounds that justify its excellent performance for low-rank approximation of matrix functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_01888 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Randomized block-Krylov subspace methods for low-rank approximation of matrix functions Persson, David Chen, Tyler Musco, Christopher Numerical Analysis 65F55, 65F60, 68W20 The randomized SVD is a method to compute an inexpensive, yet accurate, low-rank approximation of a matrix. The algorithm assumes access to the matrix through matrix-vector products (matvecs). Therefore, when we would like to apply the randomized SVD to a matrix function, $f(A)$, one needs to approximate matvecs with $f(A)$ using some other algorithm, which is typically treated as a black-box. Chen and Hallman (SIMAX 2023) argued that, in the common setting where matvecs with $f(A)$ are approximated using Krylov subspace methods (KSMs), a more efficient low-rank approximation is possible if we open this black-box. They present an alternative approach that significantly outperforms the naive combination of KSMs with the randomized SVD, although the method lacked theoretical justification. In this work, we take a closer look at the method, and provide strong and intuitive error bounds that justify its excellent performance for low-rank approximation of matrix functions. |
| title | Randomized block-Krylov subspace methods for low-rank approximation of matrix functions |
| topic | Numerical Analysis 65F55, 65F60, 68W20 |
| url | https://arxiv.org/abs/2502.01888 |