Kaczmarz Method

The Kaczmarz method, based on the work of the Polish mathematician Stefan Kaczmarz, is a method for solving linear systems of equations . 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. 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 matrix and a real or complex vector, 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, is the i-th row of the matrix, is the i-th component of the vector, and is a relaxation parameter. The above formulae gives a simple iteration routine. There are various ways for choosing the i-th equation and the relaxation parameter 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 . 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.

Famous quotes containing the word method:

    “In child rearing it would unquestionably be easier if a child were to do something because we say so. The authoritarian method does expedite things, but it does not produce independent functioning. If a child has not mastered the underlying principles of human interactions and merely conforms out of coercion or conditioning, he has no tools to use, no resources to apply in the next situation that confronts him.”
    —Elaine Heffner (20th century)