# Quantile Randomized Kaczmarz Algorithm with Whitelist Trust Mechanism

arXiv: https://arxiv.org/abs/2602.12483 · HTML: https://mlsanity.com/paper/2602.12483/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2026.

## Built on by (most cited first, 1 of 1)

- [Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent](https://mlsanity.com/paper/2609.13040/) (2026)

## Abstract (arXiv)

Randomized Kaczmarz (RK) is a simple and fast solver for consistent overdetermined systems, but it is known to be fragile under noise. We study overdetermined m× n linear systems with a sparse set of corrupted equations,  bf Abf x^star = bf b, where only tildebf b = bf b + boldsymbolvarepsilon is observed with |boldsymbolvarepsilon|0 ≤ β m. The recently introduced QuantileRK (QRK) algorithm addresses this issue by testing residuals against a quantile threshold, but computing a per-iteration quantile across many rows is costly. In this work we (i) reanalyze QRK and show that its convergence rate improves monotonically as the corruption fraction β decreases; (ii) propose a simple online detector that flags and removes unreliable rows, which reduces the effective β and speeds up convergence; and (iii) make the method practical by estimating quantiles from a small random subsample of rows, preserving robustness while lowering the per-iteration cost. Simulations on imaging and synthetic data demonstrate the efficiency of the proposed method.