View in EDS

Quantile-RK and double quantile-RK error horizon analysis.

Saved in:
Bibliographic Details
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
Description
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]
ISSN:00243795
DOI:10.1016/j.laa.2026.01.032