Quantile Randomized Kaczmarz Algorithm with Whitelist Trust Mechanism

arXiv:2602.12483v1 Announce Type: new
Abstract: 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 $mtimes n$ linear systems with a sparse set of corrupted equations, $ {bf A}{bf x}^star = {bf b}, $where only $tilde{bf b} = {bf b} + boldsymbol{varepsilon}$ is observed with $|boldsymbol{varepsilon}|_0 le beta 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 $beta$ decreases; (ii) propose a simple online detector that flags and removes unreliable rows, which reduces the effective $beta$ 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.