Quantile Randomized Kaczmarz Algorithm with Whitelist Trust Mechanism

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.