On the Subsample Size of Quantile-Based Randomized Kaczmarz

Abstract. Quantile-based randomized Kaczmarz (QRK) was recently introduced to efficiently solve sparsely corrupted linear systems [Formula: see text] [Chan, SIAM J. Matrix Anal. Appl., 43, pp. 605–637], where [Formula: see text] and [Formula: see text] is an arbitrary [Formula: see text]-sparse corruption. However, all existing theoretical guarantees for QRK require quantiles to be computed using all [Formula: see text] 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 [Formula: see text] uniformly chosen samples at each iteration. Under some standard scaling assumptions on the coefficient matrix, we show that QRK with subsample size [Formula: see text] linearly converges over the first [Formula: see text] iterations with high probability, where [Formula: see text] is some absolute constant. This subsample size is a substantial reduction from [Formula: see text] in prior results. For instance, it translates into [Formula: see text] even if an approximation error of [Formula: see text] is desired. Intriguingly, our subsample size is also tight up to a multiplicative constant: if [Formula: see text] for some constant [Formula: see text], the error of the [Formula: see text]th iterate could be arbitrarily large with high probability. Numerical results are provided to corroborate our theory.