On Subsample Size of Quantile-Based Randomized Kaczmarz

Jian-Feng Cai, Jian-Feng Cai 0001, Junren Chen, Anna Ma, Tong WuarXiv 2025 · DOI · arXiv

Abstract

The Randomized Kaczmarz (RK) method is a cornerstone algorithm for solving large-scale linear systems, yet it remains highly sensitive to corrupted data. While Quantile-Based Randomized Kaczmarz (QRK) was developed to mitigate this vulnerability by filtering outliers, its original formulation required a computationally expensive "full-sample" quantile check at every iteration. This paper investigates the theoretical and practical implications of Subsampled QRK. We demonstrate that a logarithmic-sized subsample is sufficient to maintain linear convergence, effectively removing the primary computational bottleneck of the robust algorithm.

Introduction

The Kaczmarz method is an iterative solver that finds the solution to a linear system $Ax = b$ by sequentially projecting the current estimate onto the solution space of individual rows. Its efficiency and low memory footprint make it ideal for high-dimensional problems in fields such as medical imaging and signal processing. However, the standard RK algorithm possesses a significant "glass jaw": even a small fraction of corrupted entries in the vector $b$—whether due to sensor failure or adversarial interference—can cause the estimate to diverge significantly from the true solution.

To address this, the Quantile-Based Randomized Kaczmarz (QRK) algorithm was introduced. QRK operates on a simple principle: an update is only performed if the residual of a selected row is smaller than a specific quantile of all residuals. This mechanism effectively filters out corrupted rows. However, the computational cost of calculating the quantile across all $m$ rows at every step often negates the speed advantages of the Kaczmarz approach, particularly in massive datasets.

Methods and Theoretical Framework

This research analyzes a Subsampled QRK variant. Rather than calculating the quantile across the entire dataset of $m$ rows, the algorithm selects a small, random subset of size $D$ and derives the quantile from this sample. The core challenge addressed is determining the minimum size of $D$ required to ensure the algorithm remains robust against corruption while maintaining linear convergence.

The authors employ a rigorous theoretical framework to establish these bounds:

  • Tight Chernoff Bounds: These are used to prove that a small sample $D$ can accurately represent the global distribution of residuals, ensuring the quantile estimate is reliable.
  • Stochastic Process Theory: By utilizing stopping times, the authors prove that the algorithm converges linearly over $T$ iterations with high probability.
  • Lower Bound Analysis: The study demonstrates that the proposed subsample size is not merely sufficient but necessary for stability.

Key Insights: The Logarithmic Leap

The most significant finding of this work is that the required subsample size $D$ does not need to scale with the total number of rows $m$. Instead, it scales with the number of iterations $T$ and the corruption fraction $eta$. Specifically, the relationship is defined as:

$$D \approx \frac{\log(T)}{\log(1/\beta)}$$

This "logarithmic leap" implies that for a system with millions of rows, a subsample of only a few dozen rows may be sufficient to identify outliers. This makes the robust version of the algorithm nearly as fast as the standard, non-robust Kaczmarz method.

Furthermore, the authors identify a distinct phase transition. If $D$ falls below the theoretical threshold, the algorithm undergoes a catastrophic failure, as it eventually and inevitably "accepts" a corrupted row that pulls the estimate away from the solution. This highlights the importance of the logarithmic bound in practical implementations.

Numerical Results and Validation

The theoretical claims were verified using synthetic datasets where the coefficient matrix $A$ consisted of $m=50,000$ rows and $n=100$ columns, with rows sampled from the unit sphere. Corruption was introduced as sparse vectors with a fraction $eta$ (ranging from 0.01 to 0.11) of large, arbitrary values.

Performance and Speed

In simulations, using a subsample size of $D=40$ for a system of $50,000$ rows yielded a convergence rate nearly identical to the full-sample version ($D=50,000$). However, the computational efficiency was improved by orders of magnitude. While the full-sample version required hundreds of seconds to converge, the subsampled version achieved the same result in mere seconds.

Robustness

The algorithm demonstrated a remarkable ability to ignore "jumps" in error caused by corrupted entries. As long as the subsample size satisfied the logarithmic requirement, the path to convergence remained stable despite the presence of significant outliers.

Conclusion and Future Work

By proving that a small, logarithmic subsample is sufficient for the Quantile-Based Randomized Kaczmarz method, this paper removes the primary barrier to using QRK in large-scale, real-world applications. The transition from $O(m)$ to $O(\log T)$ complexity for the quantile check represents a significant advancement in robust numerical linear algebra.

Future research may focus on explicitly calculating the absolute constants within the logarithmic bound, which currently remain as theoretical placeholders. Additionally, extending this subsampling analysis to more complex iterations, such as Block QRK or tensor-based systems, could further broaden the applicability of these robust solvers.

Summary updated

Abstract

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.
BibTeX
@misc{cai2025subsample,
  author = {Jian-Feng Cai and Jian-Feng Cai and Junren Chen and Anna Ma and Tong Wu},
  title = {{On Subsample Size of Quantile-Based Randomized Kaczmarz}},
  year = {2025},
  eprint = {2507.15185},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.15185},
}
Figure