Kaczmarz method

The Kaczmarz method, based on the work of the Polish mathematican Stefan Kaczmarz , is a method for solving linear systems of equations $A x = b$. It was rediscovered in the field of image reconstruction from projections by Richard Gordon, Robert Bender, and Gabor Herman in 1970, where it is called the Algebraic Reconstruction Technique (ART) . It is applicable to any linear system of equations, but its computational advantage relative to other methods depends on the system being sparse. This method has been found efficacious in the area of image reconstruction from projections, especially when functions with small support are chosen as the basis functions^{[citation needed]}. It has been demonstrated to be superior, in some biomedical imaging applications, to other methods such as the filtered backprojection method .

The Kaczmarz method or ART is an iterative algorithm that has many applications ranging from computed tomography (CT) to signal processing. It can be obtained also by applying to the hyperplanes, described by the linear system, the method of successive projections onto convex sets (POCS) , .

Given a real or complex $m \times n$ matrix $A$ and a real or complex vector $b$, respectively, the method computes an approximation of the solution of the linear systems of equations as in the following formula,

$x^{k+1} = x^{k} + \lambda_k \frac{b_{i} - \langle a_{i}, x^{k} \rangle}{\lVert a_{i} \rVert^2} a_{i}$

where $i = k \, \bmod \, m + 1$, $a_i$ is the i-th row of the matrix $A$, $b_i$ is the i-th component of the vector $b$, and $\lambda_k$ is a relaxation parameter. The above formulae gives a simple iteration routine. There are various ways for choosing the i-th equation $\langle a_{i}, x_{k} \rangle = b_i$ and the relaxation parameter $\lambda_k$ at the k-th iteration. If the linear system is consistent, the ART converges to the minimum-norm solution, provided that the iterations start with the zero vector, for example. There are versions of the ART that converge to a regularized weighted least squares solution when applied to a system of inconsistent equations and, at least as far as initial behavior is concerned, at a lesser cost than other iterative methods, such as the conjugate gradient method. See and references therein.

Recently, a randomized version of the Kaczmarz method for overdetermined linear systems was introduced by Strohmer and Vershyin in which the i-th equation is selected with probability proportional to $\lVert a_{i} \rVert ^2$. The superiority of this selection was illustrated with the reconstruction of a bandlimited function from its nonuniformly spaced sampling values. However, it has been pointed out that the reported success by Strohmer and Vershyin depends on the specific choices that were made there in translating the underlying problem, whose geometrical nature is to find a common point of a set of hyperplanes, into a system of algebraic equations. There will always be legitimate algebraic representations of the underlying problem for which the selection method in will perform in an inferior manner .