Inertial randomized Kaczmarz algorithms for solving coherent linear systems (Q6992068)

This paper is about an alternated inertial randomized Kaczmarz (AIRK) algorithm, an iterative method for solving a consistent linear system \(Ax=b\) with \(A\in\mathbb{R}^{I\times J}\) and full row rank. The classical method has the form \(x^{k+1}=\Psi(x^k)\) where in the original algorithm [\textit{S. Kaczmarz}, Bull. Int. Acad. Polon. Sci. A 1937, 355--357 (1937; Zbl 0017.31703)] \(\Psi\) is a projection on the hyperplane \(H_{i_k}\) defined by a cyclically selected equation \(i_k\) of the system. In the randomized version, the selection of \(i_k\) is random. In the two-subspace Kaczmarz (TSK) method of [\textit{D. Needell} and \textit{R. Ward}, J. Fourier Anal. Appl. 19, No. 2, 256--269 (2013; Zbl 1306.65190)] two different rows \(i_k,j_k\) are randomly selected according to an optimal probability and orthogonalization is used in order to reduce correlation. In the inertial version, the update is based on 2 previous steps: \(x^{k+1}=\Psi(x^k+\alpha_k(x^k-x^{k-1}))\) for reasonable scalars \(\alpha_k\), that can be optimized to speed up convergence which results in a practical iteration formula. It is shown that the proposed AIRK is equivalent with the TSK method, but with a better error estimate under mild conditions. The two indices per iteration explain the `alternated' in its name. In a multistep version (MIRK), \(j_k\) is replaced by \(i_{k-1}\) and an optimal parameter is used to minimize the error for every choice of \(i_k\) (hence no alternation). Several numerical examples illustrate the performance for the different methods.\N\NThe paper is quite accessible introducing the successive complications step by step.