Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.00258 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918088701640704 |
|---|---|
| author | Battaglia, Emeric Ma, Anna |
| author_facet | Battaglia, Emeric Ma, Anna |
| contents | In solving linear systems of equations of the form $Ax=b$, corruptions present in $b$ affect stochastic iterative algorithms' ability to reach the true solution $x^\ast$ to the uncorrupted linear system. The randomized Kaczmarz method converges in expectation to $x^\ast$ up to an error horizon dependent on the conditioning of $A$ and the supremum norm of the corruption in $b$. To avoid this error horizon in the sparse corruption setting, previous works have proposed quantile-based adaptations that make iterative methods robust. Our work first establishes a new convergence rate for the quantile-based random Kaczmarz (qRK) and double quantile-based random Kaczmarz (dqRK) methods, which, under certain conditions, improves upon known bounds. We further consider the more practical setting in which the vector $b$ includes both non-sparse ``noise" and sparse ``corruption". Error horizon bounds for qRK and dqRK are derived and shown to produce a smaller error horizon compared to their non-quantile-based counterparts, further demonstrating the advantages of quantile-based methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_00258 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantile-RK and Double Quantile-RK Error Horizon Analysis Battaglia, Emeric Ma, Anna Numerical Analysis 65F10, 65F20 In solving linear systems of equations of the form $Ax=b$, corruptions present in $b$ affect stochastic iterative algorithms' ability to reach the true solution $x^\ast$ to the uncorrupted linear system. The randomized Kaczmarz method converges in expectation to $x^\ast$ up to an error horizon dependent on the conditioning of $A$ and the supremum norm of the corruption in $b$. To avoid this error horizon in the sparse corruption setting, previous works have proposed quantile-based adaptations that make iterative methods robust. Our work first establishes a new convergence rate for the quantile-based random Kaczmarz (qRK) and double quantile-based random Kaczmarz (dqRK) methods, which, under certain conditions, improves upon known bounds. We further consider the more practical setting in which the vector $b$ includes both non-sparse ``noise" and sparse ``corruption". Error horizon bounds for qRK and dqRK are derived and shown to produce a smaller error horizon compared to their non-quantile-based counterparts, further demonstrating the advantages of quantile-based methods. |
| title | Quantile-RK and Double Quantile-RK Error Horizon Analysis |
| topic | Numerical Analysis 65F10, 65F20 |
| url | https://arxiv.org/abs/2505.00258 |