Quantile Randomized Kaczmarz for Streaming Linear Systems with Massart Noise
Abstract
Quantile randomized Kaczmarz (QRK) has proven to be an efficient solver for corrupted linear systems and has received much attention. It was recently shown by Cai et al. (SIAM J. Matrix Anal. Appl. 47(2):802-823, 2026) that using O(log T/log(1/β)) samples for computing the quantile is necessary and sufficient for QRK to converge linearly over T iterations when solving linear systems with a β-fraction of arbitrary corruptions, as long as β is small enough. However, it remains unclear how large the corruption level β can be, and how to compute the required subsample size D explicitly, without hidden constants. This paper studies streaming linear systems with Massart noise via QRK using an order-optimal batch size D=O(log T) in each update. The independence of samples from previous iterations in the streaming setting enables a sharper analysis, yielding explicit, computable bounds on both the tolerable corruption level and the required subsample size. In particular, we establish linear convergence for corruption levels of up to approximately 7%. We also discuss how the constants improve under oblivious noise.
Related
- On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems
- Weighted Randomized Kaczmarz for Sparsely Corrupted Linear Systems
- Efficient variance reduction for randomized Kaczmarz methods via residual-tracking control variates
- A greedy double-block nonlinear Bregman-Kaczmarz method for nonlinear equations
- AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs
BibTeX
@misc{battaglia2026quantile,
title = {{Quantile Randomized Kaczmarz for Streaming Linear Systems with Massart Noise}},
author = {Emeric Battaglia and Jian-Feng Cai and Junren Chen and Anna Ma and Deanna Needell and Tong Wu},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.27968},
eprint = {2608.27968},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27968},
}
RIS
TY - UNPB
TI - Quantile Randomized Kaczmarz for Streaming Linear Systems with Massart Noise
AU - Emeric Battaglia
AU - Jian-Feng Cai
AU - Junren Chen
AU - Anna Ma
AU - Deanna Needell
AU - Tong Wu
PY - 2026
DA - 2026/08/28
PB - arXiv
DO - 10.48550/arxiv.2608.27968
UR - https://arxiv.org/abs/2608.27968
AB - Quantile randomized Kaczmarz (QRK) has proven to be an efficient solver for corrupted linear systems and has received much attention. It was recently shown by Cai et al. (SIAM J. Matrix Anal. Appl. 47(2):802-823, 2026) that using O(log T/log(1/β)) samples for computing the quantile is necessary and sufficient for QRK to converge linearly over T iterations when solving linear systems with a β-fraction of arbitrary corruptions, as long as β is small enough. However, it remains unclear how large the corruption level β can be, and how to compute the required subsample size D explicitly, without hidden constants. This paper studies streaming linear systems with Massart noise via QRK using an order-optimal batch size D=O(log T) in each update. The independence of samples from previous iterations in the streaming setting enables a sharper analysis, yielding explicit, computable bounds on both the tolerable corruption level and the required subsample size. In particular, we establish linear convergence for corruption levels of up to approximately 7%. We also discuss how the constants improve under oblivious noise.
ER -