Quantile-Based Random Kaczmarz for corrupted linear systems of equations

Abstract

We consider linear systems $Ax=b$ where $A\in {\mathbb{R}}^{m\times n}$ consists of normalized rows, $\Vert a_i{\Vert }_{{\ell }^2}=1$, and where up to $\beta m$ entries of $b$ have been corrupted (possibly by arbitrarily large numbers). Haddock, Needell, Rebrova and Swartworth propose a quantile-based Random Kaczmarz method and show that for certain random matrices $A$ it converges with high likelihood to the true solution. We prove a deterministic version by constructing, for any matrix $A$, a number ${\beta }_A$ such that there is convergence for all perturbations with $\beta <{\beta }_A$. Assuming a random matrix heuristic, this proves convergence for tall Gaussian matrices with up to $\sim 0.5\%$ corruption (a number that can likely be improved).