On the Subsample Size of Quantile-Based Randomized Kaczmarz

Quantile-based randomized Kaczmarz (QRK) was recently introduced to efficiently solve sparsely corrupted linear systems $\\mathbf{A} \\mathbf{x}^*+\\mathbfε = \\mathbf{b}$ [SIAM J. Matrix Anal. Appl., 43(2), 605-637], where $\\mathbf{A}\\in \\mathbb{R}^{m\\times 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\\ge\\frac{C\\log (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(-n^2)$ is desired. Intriguingly, our subsample size is also tight up to a multiplicative constant: if $D\\le \\frac{c\\log(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.