On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems
Abstract
The randomized Kaczmarz (RK) method is an efficient iterative projection algorithm with low computational complexity for solving consistent linear systems. However, noise is inevitable in real-world applications, and both the coefficient matrix and the right-hand side vector may be contaminated by noise. The convergence analysis of RK-type methods for doubly noisy linear systems, where both the system matrix and the measurement vector are perturbed, remains relatively limited. In this paper, we investigate the limiting behavior of the RK algorithm for solving doubly noisy inconsistent linear systems without imposing any additional initial assumptions. Furthermore, to the best of our knowledge, this work provides the first convergence analysis of the randomized extended Kaczmarz (REK), randomized block Kaczmarz (RBK), and randomized double block Kaczmarz (RDBK) algorithms for doubly noisy linear systems. We prove that these algorithms converge to a neighborhood of the least-squares solution of the underlying noiseless system. Compared with existing theoretical estimates, the proposed bounds effectively characterize the convergence behavior of these algorithms when applied to doubly noisy linear systems. Finally, numerical experiments are conducted to validate the theoretical results.