2021/08/04 by Benjamin Jarman, Jarman, Benjamin, Deanna Needell +1 · 1 citation
Computer Science · Engineering · Mathematics · #65F10 #68W20 #Advanced Optimization Algorithms Research #FOS: Mathematics #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2108.02304
openalex publication_date 2021/08/04 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Measurement data in linear systems arising from real-world applications often suffers from both large, sparse corruptions, and widespread small-scale noise. This can render many popular solvers ineffective, as the least squares solution is far from the desired solution, and the underlying consistent system becomes harder to identify and solve. QuantileRK is a member of the Kaczmarz family of iterative projective methods that has been shown to converge exponentially for systems with arbitrarily large sparse corruptions. In this paper, we extend the analysis to the case where there are not only corruptions present, but also noise that may affect every data point, and prove that QuantileRK converges with the same rate up to an error threshold. We give both theoretical and experimental results demonstrating QuantileRK's strength.