2025/07/21 by Cai, Jian-Feng, Chen, Junren, Ma, Anna +1
#60B20 #65F10 #68W20 #FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2507.15185
Quantile-based randomized Kaczmarz (QRK) was recently introduced to efficiently solve sparsely corrupted linear systems A x^*+\mathbfε = b [SIAM J. Matrix Anal. Appl., 43(2), 605-637], where A∈ ℝm× n and \mathbfε is an arbitrary (βm)-sparse corruption. However, all existing theoretical guarantees for QRK require quantiles to be computed using all m samples (or a subsample of the same order), thus negating the computational advantage of Kaczmarz-type methods. This paper overcomes the bottleneck. We analyze a subsampling QRK, which computes quantiles from D uniformly chosen samples at each iteration. Under some standard scaling assumptions on the coefficient matrix, we show that QRK with subsample size D≥(Clog (T))/(log(1/β)) linearly converges over the first T iterations with high probability, where C is some absolute constant. This subsample size is a substantial reduction from O(m) in prior results. For instance, it translates into O(log(n)) even if an approximation error of exp(-n2) is desired. Intriguingly, our subsample size is also tight up to a multiplicative constant: if D≤ (clog(T))/(log(1/β)) for some constant c, the error of the T-th iterate could be arbitrarily large with high probability. Numerical results are provided to corroborate our theory.