2025/05/01 by Battaglia, Emeric, Ma, Anna
#65F10 #65F20 #FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2505.00258
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^∗ 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.