Fast and forward stable randomized algorithms for linear least-squares problems
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910406984859648 |
|---|---|
| author | Epperly, Ethan N. |
| author_facet | Epperly, Ethan N. |
| contents | Iterative sketching and sketch-and-precondition are randomized algorithms used for solving overdetermined linear least-squares problems. When implemented in exact arithmetic, these algorithms produce high-accuracy solutions to least-squares problems faster than standard direct methods based on QR factorization. Recently, Meier, Nakatsukasa, Townsend, and Webb demonstrated numerical instabilities in a version of sketch-and-precondition in floating point arithmetic (arXiv:2302.07202). The work of Meier et al. raises the question: Is there a randomized least-squares solver that is both fast and stable? This paper resolves this question in the affirmative by proving that iterative sketching, appropriately implemented, is forward stable. Numerical experiments confirm the theoretical findings, demonstrating that iterative sketching is stable and faster than QR-based solvers for large problem instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_04362 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fast and forward stable randomized algorithms for linear least-squares problems Epperly, Ethan N. Numerical Analysis 65F10, 65F20, 65G50, 65K10, 68W20 Iterative sketching and sketch-and-precondition are randomized algorithms used for solving overdetermined linear least-squares problems. When implemented in exact arithmetic, these algorithms produce high-accuracy solutions to least-squares problems faster than standard direct methods based on QR factorization. Recently, Meier, Nakatsukasa, Townsend, and Webb demonstrated numerical instabilities in a version of sketch-and-precondition in floating point arithmetic (arXiv:2302.07202). The work of Meier et al. raises the question: Is there a randomized least-squares solver that is both fast and stable? This paper resolves this question in the affirmative by proving that iterative sketching, appropriately implemented, is forward stable. Numerical experiments confirm the theoretical findings, demonstrating that iterative sketching is stable and faster than QR-based solvers for large problem instances. |
| title | Fast and forward stable randomized algorithms for linear least-squares problems |
| topic | Numerical Analysis 65F10, 65F20, 65G50, 65K10, 68W20 |
| url | https://arxiv.org/abs/2311.04362 |