Kaczmarz Kac walk (Q6937307)

The Kaczmarz method, proposed by \textit{S. Kaczmarz} [Bull. intern. Acad. Polonaise Sci. Lett., Cl. Sci. math. nat. A. 1937, 355--357 (1937; JFM 63.0524.02)], is a row-based iterative method for solving linear systems of equations \(Ax=b\) with injective and square or overdetermined matrix. The solution is interpreted geometrically as the unique point in the intersection of hyperplanes \N\[\NH_i = \{w: (A_i,w) = b_i\},\N\]\Nwhere \(A_i\) is the \(i\)-th row of the system matrix. An approximate solution is iteratively projected onto these hyperplanes to get better and better approximations.\N\NThe author proposes an approach whose basic idea is to replace the original system by another system which has the same solution but a ``better'' system matrix. One could take two random hyperplanes with rows normalized to unit length, take a linear combination of the two and replace any of the two equations by this linear combination. A natural choice is to project the normal vector of one of the hyperplanes onto the orthogonal complement of the other and then renormalize. This approach only requires the computation of one single inner product and makes the rows ``more orthogonal''. The new linear system is better conditioned and easier to solve.\N\NThe procedure is beneficial insofar as it regularizes (in expectation) the matrix along degenerate subspaces where the singular values are less than one while keeping the Frobenius norm invariant. The author first discusses the case of square matrices and then more complicated overdetermined case.