Kaczmarz method

The Kaczmarz method based on the work of the Polish mathematician Stefan Kaczmarz is used for the iterative solution of linear systems of equations of the form Ax = b, where A is a non-singular and u. U. over-defined matrix , b is the given solution and x is the solution vector sought. It is an iterative algorithm that has found its way into computed tomography and digital signal processing , among other things .

In contrast to most other iterative solution methods, such as the Gauß-Seidel method , the Kaczmarz algorithm only requires an invertible, but not positive- definite , matrix A. For this reason, the method can be used for practically all applications without any problems although procedures for specific problems can be much faster. However, a randomized variant of the Kaczmarz method shows significantly better convergence in the case of overdetermined systems of equations than other iterative solution methods.

The original algorithm

A real or complex m × n matrix A (m ≥ n) of full rank and a vector b are given. The following iteration formula improves the approximation to the solution x of the equation Ax = b with each iteration:

{\ displaystyle x_ {k + 1} = x_ {k} + {\ frac {b_ {i} - \ langle a_ {i}, x_ {k} \ rangle} {\ lVert a_ {i} \ rVert ^ {2 }}} a_ {i}}

,

in which

{\ displaystyle i = (k \, {\ bmod {\,}} m) +1}

It is with the matrix A transposed meant the i-th row. ${\ displaystyle a_ {i}}$

${\ displaystyle {\ lVert a_ {i} \ rVert ^ {2}}}$ is the squared Euclidean norm of , the sum of the squared entries of or the scalar product . ${\ displaystyle a_ {i}}$ ${\ displaystyle a_ {i}}$ ${\ displaystyle \ langle a_ {i}, a_ {i} \ rangle}$

The starting value can be chosen randomly, but should be chosen as close as possible to the solution if a simple estimate can be made with regard to the solution.

Randomized algorithm

As already mentioned above, there is a variant of the method which converges much faster in the case of overdetermined systems of equations. Better convergence is achieved not only for solving highly overdetermined systems of equations, but also, for example, for solving systems with 10% more equations than unknowns. For this purpose, the i in the above iteration equation does not have to be chosen as a function of k, but randomly (hence the name of the method). The probability for a certain i is here proportional to for each iteration. ${\ displaystyle \ lVert a_ {i} \ rVert ^ {2}}$

swell

S. Kaczmarz: Przyblizone rozwiazywanie ukladów równan liniowych. - Approximate resolution of systems of linear equations. Bulletin International de l'Académie Polonaise des Sciences et des Lettres. Class des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques, pp. 355–357, 1937. (Warning: this article is very widely cited with the wrong page reference 335–357.)
T. Strohmer, R. Vershynin: A randomized Kaczmarz algorithm with exponential convergence , J. Fourier Anal. Appl. 15 (1), 262-278, 2009
W. Hackbusch : Iterative solution of large sparse equation systems. Teubner Study Books, 1993, pp. 202-203

Individual proof

↑ Thomas Strohmer, Roman Vershynin: A randomized solver for linear systems with exponential convergence. (pdf)

[1] Thomas Strohmer, Roman Vershynin: A randomized solver for linear systems with exponential convergence. (pdf)