Where Have All the Kaczmarz Iterates Gone?
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_ | 1866909833383378944 |
|---|---|
| author | Bergou, El Houcine Boucherouite, Soumia Dutta, Aritra Li, Xin Ma, Anna |
| author_facet | Bergou, El Houcine Boucherouite, Soumia Dutta, Aritra Li, Xin Ma, Anna |
| contents | The randomized Kaczmarz (RK) algorithm is one of the most computationally and memory-efficient iterative algorithms for solving large-scale linear systems. However, practical applications often involve noisy and potentially inconsistent systems. While the convergence of RK is well understood for consistent systems, the study of RK on noisy, inconsistent linear systems is limited. This paper investigates the asymptotic behavior of RK iterates in expectation when solving noisy and inconsistent systems, addressing the locations of their limit points. We explore the roles of singular vectors of the (noisy) coefficient matrix and derive bounds on the convergence horizon, which depend on the noise levels and system characteristics. Finally, we provide extensive numerical experiments that validate our theoretical findings, offering practical insights into the algorithm's performance under realistic conditions. These results establish a deeper understanding of the RK algorithm's limitations and robustness in noisy environments, paving the way for optimized applications in real-world scientific and engineering problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_08563 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Where Have All the Kaczmarz Iterates Gone? Bergou, El Houcine Boucherouite, Soumia Dutta, Aritra Li, Xin Ma, Anna Numerical Analysis Machine Learning Optimization and Control 15A06, 15A09, 15A10, 15A18, 65F10, 65Y20, 68Q25, 68W20, 68W40 The randomized Kaczmarz (RK) algorithm is one of the most computationally and memory-efficient iterative algorithms for solving large-scale linear systems. However, practical applications often involve noisy and potentially inconsistent systems. While the convergence of RK is well understood for consistent systems, the study of RK on noisy, inconsistent linear systems is limited. This paper investigates the asymptotic behavior of RK iterates in expectation when solving noisy and inconsistent systems, addressing the locations of their limit points. We explore the roles of singular vectors of the (noisy) coefficient matrix and derive bounds on the convergence horizon, which depend on the noise levels and system characteristics. Finally, we provide extensive numerical experiments that validate our theoretical findings, offering practical insights into the algorithm's performance under realistic conditions. These results establish a deeper understanding of the RK algorithm's limitations and robustness in noisy environments, paving the way for optimized applications in real-world scientific and engineering problems. |
| title | Where Have All the Kaczmarz Iterates Gone? |
| topic | Numerical Analysis Machine Learning Optimization and Control 15A06, 15A09, 15A10, 15A18, 65F10, 65Y20, 68Q25, 68W20, 68W40 |
| url | https://arxiv.org/abs/2510.08563 |