Quantile-RK and double quantile-RK error horizon analysis.
Saved in:
| Title: | Quantile-RK and double quantile-RK error horizon analysis. |
|---|---|
| Authors: | Battaglia, Emeric1 (AUTHOR) ebattagl@uci.edu, Ma, Anna1 (AUTHOR) |
| Source: | Linear Algebra & its Applications. May2026, Vol. 736, p284-308. 25p. |
| Subjects: | Quantiles, Data corruption, Robust statistics, Iterative methods (Mathematics), Linear systems, Stochastic approximation |
| Abstract: | In solving linear systems of equations of the form A x = b , corruptions present in b affect stochastic iterative algorithms' ability to reach the true solution x ⁎ to the uncorrupted linear system. The randomized Kaczmarz method converges in expectation to x ⁎ 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Linear Algebra & its Applications is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 191841012 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Quantile-RK and double quantile-RK error horizon analysis. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Battaglia%2C+Emeric%22">Battaglia, Emeric</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> ebattagl@uci.edu</i><br /><searchLink fieldCode="AR" term="%22Ma%2C+Anna%22">Ma, Anna</searchLink><relatesTo>1</relatesTo> (AUTHOR) – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Linear+Algebra+%26+its+Applications%22">Linear Algebra & its Applications</searchLink>. May2026, Vol. 736, p284-308. 25p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Quantiles%22">Quantiles</searchLink><br /><searchLink fieldCode="DE" term="%22Data+corruption%22">Data corruption</searchLink><br /><searchLink fieldCode="DE" term="%22Robust+statistics%22">Robust statistics</searchLink><br /><searchLink fieldCode="DE" term="%22Iterative+methods+%28Mathematics%29%22">Iterative methods (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+systems%22">Linear systems</searchLink><br /><searchLink fieldCode="DE" term="%22Stochastic+approximation%22">Stochastic approximation</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: In solving linear systems of equations of the form A x = b , corruptions present in b affect stochastic iterative algorithms' ability to reach the true solution x ⁎ to the uncorrupted linear system. The randomized Kaczmarz method converges in expectation to x ⁎ 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. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Linear Algebra & its Applications is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=191841012 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.laa.2026.01.032 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 25 StartPage: 284 Subjects: – SubjectFull: Quantiles Type: general – SubjectFull: Data corruption Type: general – SubjectFull: Robust statistics Type: general – SubjectFull: Iterative methods (Mathematics) Type: general – SubjectFull: Linear systems Type: general – SubjectFull: Stochastic approximation Type: general Titles: – TitleFull: Quantile-RK and double quantile-RK error horizon analysis. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Battaglia, Emeric – PersonEntity: Name: NameFull: Ma, Anna IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 05 Text: May2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 00243795 Numbering: – Type: volume Value: 736 Titles: – TitleFull: Linear Algebra & its Applications Type: main |
| ResultId | 1 |
