A Note on Randomized Kaczmarz Algorithm for Solving Doubly-Noisy Linear
  Systems
El Houcine Bergou Soumia Boucherouite Aritra Dutta Xin Li Anna Ma
Large-scale linear systems, $Ax=b$, frequently arise in practice and demand
effective iterative solvers. Often, these systems are noisy due to operational
errors or faulty data-collection processes. In the past decade, the randomized
Kaczmarz (RK) algorithm has been studied extensively as an efficient iterative
solver for such systems. However, the convergence study of RK in the noisy
regime is limited and considers measurement noise in the right-hand side
vector, $b$. Unfortunately, in practice, that is not always the case; the
coefficient matrix $A$ can also be noisy. In this paper, we analyze the
convergence of RK for noisy linear systems when the coefficient matrix, $A$, is
corrupted with both additive and multiplicative noise, along with the noisy
vector, $b$. In our analyses, the quantity $\tilde R=\| \tilde A^{\dagger}
\|_2^2 \|\tilde A \|_F^2$ influences the convergence of RK, where $\tilde A$
represents a noisy version of $A$. We claim that our analysis is robust and
realistically applicable, as we do not require information about the noiseless
coefficient matrix, $A$, and considering different conditions on noise, we can
control the convergence of RK. We substantiate our theoretical findings by
performing comprehensive numerical experiments.