This seminar surveys two recent developments in quantile-based randomized Kaczmarz (QRK) for corrupted linear systems. We begin with the QRK framework of [SIAM J. Matrix Anal. Appl., 43(2), 605–637], which efficiently solves systems of the form A x* + ε = b when the corruption vector ε is (βm)-sparse. A central question in this line of work is how many samples are actually needed to estimate the quantile used in each QRK update. The first part of the talk presents the subsampling theory in [SIAM J. Matrix Anal. Appl., 2025, to appear]: instead of using all m residuals, one may compute the quantile from only D uniformly sampled entries, and linear convergence over the first T iterations still holds with high probability provided

  D ≥ (C log T) / log(1/β).

Moreover, this order is sharp up to constants, since if D ≤ (c log T) / log(1/β), then the T-th iterate can remain arbitrarily inaccurate with high probability.

The second part of the seminar discusses a follow-up direction motivated by this result. While the subsampling theorem identifies the optimal order D = O( (log T) / log(1/β) ) when β = O(1), it leaves open how to make the constants explicit, how large the admissible corruption level β can be, and how small the subsample size D can be while still retaining guarantees. We therefore turn to streaming linear systems with Massart noise, where QRK is implemented using an optimal O(log T) batch size per update. The goal is to understand how the finite-subsample perspective extends to the online setting and how it leads to more explicit quantitative guarantees for robust streaming regression.