Introduction
In large-scale data processing, such as medical imaging or signal processing, solving massive linear systems of the form $Ax = b$ is a fundamental task. The Randomized Kaczmarz (RK) algorithm is a popular choice due to its memory efficiency, processing only one row of the matrix at a time. However, real-world datasets are often plagued by two distinct types of errors: sparse, large-magnitude "corruptions" (e.g., sensor failures) and dense, small-magnitude "noise" (e.g., thermal fluctuations). Standard RK methods struggle in the presence of corruptions, as even a single outlier can significantly derail the convergence path.
Methodology
QuantileRK is an iterative solver designed to handle both noise and corruption simultaneously. The algorithm introduces a quantile-based filtering mechanism to identify and skip suspicious data points. At each iteration:
- Sample: A small batch of rows is sampled to calculate a "sub-residual."
- Filter: The $q$-quantile of these residuals is computed.
- Threshold: A random row is selected for a potential update. If its residual exceeds the $q$-quantile, it is flagged as likely corrupted and the update is skipped.
This filtering mechanism ensures that the solver remains focused on "honest" data points, allowing for robust convergence.
Theoretical Guarantees and Insights
The primary contribution of this work is the theoretical proof that QuantileRK achieves exponential convergence down to a predictable "error horizon" determined by the background noise level. Specifically, the expected error decreases at a fixed exponential rate regardless of the corruption level, stalling only when it reaches the noise floor.
A particularly striking insight is the "counter-intuitive robustness" of the method. As shown in Figure 1, larger corruptions (higher $k$ values) actually facilitate faster initial convergence. This occurs because massive outliers are more easily distinguished from the noise by the quantile filter, allowing the algorithm to effectively ignore them from the start.
Experimental Results
The performance of QuantileRK is sensitive to the choice of the quantile parameter $q$. Experiments using synthetic Gaussian matrices ($2000 \times 100$) demonstrate that the optimal $q$ is closely related to the fraction of uncorrupted data ($1-\beta$).
As seen in Figure 2, there is a clear "sweet spot" for $q$. If $q$ is too small, the algorithm skips too many valid rows, slowing down progress. If $q$ is too large, it begins to accept corrupted rows, causing the error to spike. When tuned correctly, QuantileRK successfully reaches the noise floor even with significant corruption levels, a scenario where standard RK would fail.
Conclusion
QuantileRK provides a robust framework for solving large-scale linear systems under adverse data conditions. By leveraging quantile filtering, it achieves fast convergence and a predictable error floor. Future research directions include extending this approach to Block Kaczmarz methods and greedy selection strategies like Motzkin’s Method, as well as relaxing the assumptions on matrix structure.
Summary updated