Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.19877 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909573154078720 |
|---|---|
| author | Epperly, Ethan N. Goldshlager, Gil Webber, Robert J. |
| author_facet | Epperly, Ethan N. Goldshlager, Gil Webber, Robert J. |
| contents | The randomized Kaczmarz (RK) method is a well-known approach for solving linear least-squares problems with a large number of rows. RK accesses and processes just one row at a time, leading to exponentially fast convergence for consistent linear systems. However, RK fails to converge to the least-squares solution for inconsistent systems. This work presents a simple fix: average the RK iterates produced in the tail part of the algorithm. The proposed tail-averaged randomized Kaczmarz (TARK) converges for both consistent and inconsistent least-squares problems at a polynomial rate, which is known to be optimal for any row-access method. An extension of TARK also leads to efficient solutions for ridge-regularized least-squares problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19877 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Randomized Kaczmarz with tail averaging Epperly, Ethan N. Goldshlager, Gil Webber, Robert J. Numerical Analysis The randomized Kaczmarz (RK) method is a well-known approach for solving linear least-squares problems with a large number of rows. RK accesses and processes just one row at a time, leading to exponentially fast convergence for consistent linear systems. However, RK fails to converge to the least-squares solution for inconsistent systems. This work presents a simple fix: average the RK iterates produced in the tail part of the algorithm. The proposed tail-averaged randomized Kaczmarz (TARK) converges for both consistent and inconsistent least-squares problems at a polynomial rate, which is known to be optimal for any row-access method. An extension of TARK also leads to efficient solutions for ridge-regularized least-squares problems. |
| title | Randomized Kaczmarz with tail averaging |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2411.19877 |