Kaczmarz method

It was first discovered by the Polish mathematician Stefan Kaczmarz,[1] and 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).

[2] ART includes the positivity constraint, making it nonlinear.

[4] It 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).

[5][6] The original Kaczmarz algorithm solves a complex-valued system of linear equations

When we are in the space of real vectors, the Kaczmarz iteration has a clear geometric meaning.

converges to the minimum-norm solution, provided that the iterations start with the zero vector.

[7] In 2009, a randomized version of the Kaczmarz method for overdetermined linear systems was introduced by Thomas Strohmer and Roman Vershynin[8] in which the i-th equation is selected randomly with probability proportional to

We have Using we can write (2) as The main point of the proof is to view the left hand side in (3) as an expectation of some random variable.

The orthogonality of these two vectors then yields To complete the proof, we have to bound

Thus Now we take the expectation of both sides conditional upon the choice of the random vectors

Then By (4) and the independence, Taking the full expectation of both sides, we conclude that 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[10] that the reported success by Strohmer and Vershynin 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[8] will perform in an inferior manner.

Specifically, in the above-mentioned reconstruction example, the equations were chosen with probability proportional to the average distance of each sample point from its two nearest neighbors — a concept introduced by Feichtinger and Gröchenig.

In 2015, Robert M. Gower and Peter Richtarik[14] developed a versatile randomized iterative method for solving a consistent system of linear equations

which includes the randomized Kaczmarz algorithm as a special case.

The method is shown to enjoy exponential rate decay (in expectation) - also known as linear convergence, under very mild conditions on the way randomness enters the algorithm.

Interesting new insights about the randomized Kaczmarz method that can be gained from the analysis of the method include: The Gower-Richtarik method enjoys six seemingly different but equivalent formulations, shedding additional light on how to interpret it (and, as a consequence, how to interpret its many variants, including randomized Kaczmarz): We now describe some of these viewpoints.

A seemingly different but entirely equivalent formulation of the method (obtained via Lagrangian duality) is where

is obtained by first constraining the update to the linear subspace spanned by the columns of the random matrix

This formulation may look surprising as it seems impossible to perform the approximation step due to the fact that

from both sides of the random update formula, denote and use the fact that

By taking norms and unrolling the recurrence, we obtain Remark.

has a full column rank and under very mild conditions on

Convergence of the method can be established also without the full column rank assumption in a different way.

This second type of convergence is stronger due to the following identity[14] which holds for any random vector

It can be checked by direct calculation that Since the convergence of the (randomized) Kaczmarz method depends on a rate of convergence the method may make slow progress on some practical problems.

[10] To ensure finite termination of the method, Johannes Brust and Michael Saunders (academic) [16] have developed a process that generalizes the (randomized) Kaczmarz iteration and terminates in at most

The resulting algorithm only requires matrix-vector products and has a direct form