On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems

Abstract

In this paper, we consider the convergence of some popular Kaczmarz-type methods, including the randomized Kaczmarz (RK) method, the randomized extended Kaczmarz (REK) method, the randomized block Kaczmarz (RBK) method, and the randomized double block Kaczmarz (RDBK) method for doubly noisy linear system. To the best of our knowledge, this is the first work that considers and compares the convergence of the Kaczmarz-type methods for consistent linear systems, as well as that for inconsistent linear systems to solve double noisy linear system. We prove that these methods converge to a neighborhood of the smallest norm least squares solution of the underlying noiseless system. Specifically, RK and RBK that are designed for consistent linear systems, often outperform REK and RDBK that are designed for inconsistent linear systems, respectively, in terms of the convergence rate or the convergence horizon. Moreover, we establish the convergence of the more general sketch-and-project framework for the doubly noisy linear system. The analysis provides more comprehensive results without imposing any additional restrictions. Numerical experiments are performed to validate our theoretical results.