2024/10/17 by Emeric Battaglia, Battaglia, Emeric, Anna Ma +1 · 1 citation
Computer Science · #FOS: Mathematics #Neural Networks and Applications #Numerical Analysis (math.NA)
paper · pdf · doi:10.48550/arxiv.2410.13395
openalex publication_date 2024/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
When solving linear systems Ax=b, A and b are given, but the measurements b often contain corruptions. Inspired by recent work on the quantile-randomized Kaczmarz method, we propose an acceleration of the randomized Kaczmarz method using quantile information. We show that the proposed acceleration converges faster than the randomized Kaczmarz algorithm. In addition, we show that our proposed approach can be used in conjunction with the quantile-randomized Kaczamrz algorithm, without adding additional computational complexity, to produce both a fast and robust iterative method for solving large, sparsely corrupted linear systems. Our extensive experimental results support the use of the revised algorithm.