A Note on the Randomized Kaczmarz Algorithm for Solving Doubly Noisy Linear Systems

Authors:
Publisher website
Google Scholar
Abstract
Large-scale linear systems, [Formula: see text], 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 algorithm (RK) 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, [Formula: see text]. Unfortunately, in practice, that is not always the case; the coefficient matrix [Formula: see text] can also be noisy. In this paper, we analyze the convergence of RK for doubly noisy linear systems, i.e., when the coefficient matrix, [Formula: see text], has additive or multiplicative noise, and [Formula: see text] is also noisy. In our analyses, the quantity [Formula: see text] influences the convergence of RK, where [Formula: see text] represents a noisy version of [Formula: see text]. We claim that our analysis is robust and realistically applicable, as we do not require information about the noiseless coefficient matrix, [Formula: see text], and by considering different conditions on noise, we can control the convergence of RK. We perform numerical experiments to substantiate our theoretical findings.

This publication has 41 references indexed in Scilit: