Row-aware Randomized SVD with applications
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911085065404416 |
|---|---|
| author | Palitta, Davide Portaro, Sascha |
| author_facet | Palitta, Davide Portaro, Sascha |
| contents | The randomized singular value decomposition proposed in [27] has certainly become one of the most well-established randomization-based algorithms in numerical linear algebra. The key ingredient of the entire procedure is the computation of a subspace which is close to the column space of the target matrix $\mathbf{A}$ up to a certain probabilistic confidence. In this paper we employ a modification to the standard randomized SVD procedure which leads, in general, to better approximations to $\text{Range}(\mathbf{A})$ at the same computational cost. To this end, we explicitly construct information from the row space of $\mathbf{A}$ enhancing the quality of the approximation. We derive novel error bounds which improve over existing results for $\mathbf{A}$ having important gaps in its singular values. We also observe that very few pieces of information from $\text{Range}(\mathbf{A}^T)$ may be necessary. We thus design a variant of this algorithm equipped with a subsampling step which largely increases the efficiency of the procedure while often attaining competitive accuracy records. Our findings are supported by both theoretical analysis and numerical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04503 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Row-aware Randomized SVD with applications Palitta, Davide Portaro, Sascha Numerical Analysis 65F55, 68W20 The randomized singular value decomposition proposed in [27] has certainly become one of the most well-established randomization-based algorithms in numerical linear algebra. The key ingredient of the entire procedure is the computation of a subspace which is close to the column space of the target matrix $\mathbf{A}$ up to a certain probabilistic confidence. In this paper we employ a modification to the standard randomized SVD procedure which leads, in general, to better approximations to $\text{Range}(\mathbf{A})$ at the same computational cost. To this end, we explicitly construct information from the row space of $\mathbf{A}$ enhancing the quality of the approximation. We derive novel error bounds which improve over existing results for $\mathbf{A}$ having important gaps in its singular values. We also observe that very few pieces of information from $\text{Range}(\mathbf{A}^T)$ may be necessary. We thus design a variant of this algorithm equipped with a subsampling step which largely increases the efficiency of the procedure while often attaining competitive accuracy records. Our findings are supported by both theoretical analysis and numerical results. |
| title | Row-aware Randomized SVD with applications |
| topic | Numerical Analysis 65F55, 68W20 |
| url | https://arxiv.org/abs/2408.04503 |