Randomized Kaczmarz solver for noisy linear systems (Q981677)

The method of \textit{S. Kaczmarz} [Bull. Int. Acad. Polon. Sci. A 1937, 355--357 (1937; Zbl 0017.31703)] is an iterative algorithm for solving systems of linear equations \(A x = b\). It is proved that in the noisy version \(A x \approx b+r,\) where \(r\) is an arbitrary error vector, the randomized method reaches an error threshold dependent on the matrix \(A\) with the same rate as in the error-free case. Examples are shown that the authors results are sharp in the general context.