Global Asymptotic Rates Under Randomization: Gauss-Seidel and Kaczmarz
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914406454001664 |
|---|---|
| author | Entezari, Alireza Banerjee, Arunava |
| author_facet | Entezari, Alireza Banerjee, Arunava |
| contents | Current performance bounds for randomized iterative methods are often considered tight under per-iteration analyses, yet they are notoriously loose in practice. We derive asymptotic performance bounds that narrow this theory-practice gap, leveraging a new technique for bounding the spectral radii of operators arising in randomized iterations and a connection we establish to Perron-Frobenius theory for noncommutative algebras. The asymptotic analysis also uncovers and quantifies the previously unexplained role of relaxation in improving performance, thereby resolving an open problem posed by Strohmer and Vershynin in 2007. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_09469 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Global Asymptotic Rates Under Randomization: Gauss-Seidel and Kaczmarz Entezari, Alireza Banerjee, Arunava Numerical Analysis Current performance bounds for randomized iterative methods are often considered tight under per-iteration analyses, yet they are notoriously loose in practice. We derive asymptotic performance bounds that narrow this theory-practice gap, leveraging a new technique for bounding the spectral radii of operators arising in randomized iterations and a connection we establish to Perron-Frobenius theory for noncommutative algebras. The asymptotic analysis also uncovers and quantifies the previously unexplained role of relaxation in improving performance, thereby resolving an open problem posed by Strohmer and Vershynin in 2007. |
| title | Global Asymptotic Rates Under Randomization: Gauss-Seidel and Kaczmarz |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2503.09469 |