The Kaczmarz method or Kaczmarz's algorithm is an iterative algorithm for solving linear equation systems A x = b. It was first discovered by the Polish mathematician Stefan Kaczmarz, 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). ART includes the positivity constraint, making it nonlinear. The Kaczmarz method is applicable to any linear system of equations, but its computational advantage relative to other methods depends on the system being sparse. It has been demonstrated to be superior, in some biomedical imaging applications, to other methods such as the filtered backprojection method. 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).

Algorithm 1: Kaczmarz algorithm

Let Ax = b be a system of linear equations, let m be the number of rows of A, a_{i} be the ith row of complex-valued matrix A, and let x^{0} be arbitrary complex-valued initial approximation to the solution of Ax=b. For compute: where and denotes complex conjugation of a_i. If the system is consistent, x^k converges to the minimum-norm solution, provided that the iterations start with the zero vector. A more general algorithm can be defined using a relaxation parameter \lambda^k There are versions of the method 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.

Algorithm 2: Randomized Kaczmarz algorithm

In 2009, a randomized version of the Kaczmarz method for overdetermined linear systems was introduced by Thomas Strohmer and Roman Vershynin in which the i-th equation is selected randomly with probability proportional to |a_i |^2. This method can be seen as a particular case of stochastic gradient descent. Under such circumstances x_{k} converges exponentially fast to the solution of Ax=b, and the rate of convergence depends only on the scaled condition number \kappa(A).

Proof

We have Using we can write as The main point of the proof is to view the left hand side in as an expectation of some random variable. Namely, recall that the solution space of the j-th equation of Ax=b is the hyperplane whose normal is Define a random vector Z whose values are the normals to all the equations of Ax=b, with probabilities as in our algorithm: Then says that The orthogonal projection P onto the solution space of a random equation of Ax=b is given by Now we are ready to analyze our algorithm. We want to show that the error reduces at each step in average (conditioned on the previous steps) by at least the factor of The next approximation x_k is computed from x_{k-1} as where are independent realizations of the random projection P. The vector x_{k-1}-x_k is in the kernel of P_k. It is orthogonal to the solution space of the equation onto which P_k projects, which contains the vector x_k-x (recall that x is the solution to all equations). The orthogonality of these two vectors then yields To complete the proof, we have to bound from below. By the definition of x_k, we have where are independent realizations of the random vector Z. Thus Now we take the expectation of both sides conditional upon the choice of the random vectors (hence we fix the choice of the random projections and thus the random vectors and we average over the random vector Z_k). Then By 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 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 will perform in an inferior manner. The Kaczmarz iteration has a purely geometric interpretation: the algorithm successively projects the current iterate onto the hyperplane defined by the next equation. Hence, any scaling of the equations is irrelevant; it can also be seen from that any (nonzero) scaling of the equations cancels out. Thus, in RK, one can use | a_i | or any other weights that may be relevant. 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. For additional progress on this topic, see, and the references therein.

Algorithm 3: Gower-Richtarik algorithm

In 2015, Robert M. Gower and Peter Richtarik developed a versatile randomized iterative method for solving a consistent system of linear equations Ax = b which includes the randomized Kaczmarz algorithm as a special case. Other special cases include randomized coordinate descent, randomized Gaussian descent and randomized Newton method. Block versions and versions with importance sampling of all these methods also arise as special cases. 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. The Gower-Richtarik method is the first algorithm uncovering a "sibling" relationship between these methods, some of which were independently proposed before, while many of which were new.

Insights about Randomized Kaczmarz

Interesting new insights about the randomized Kaczmarz method that can be gained from the analysis of the method include:

Six Equivalent Formulations

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. The method depends on 2 parameters:

1. Sketch and Project

Given previous iterate x^k, the new point x^{k+1} is computed by drawing a random matrix S (in an iid fashion from some fixed distribution), and setting That is, x^{k+1} is obtained as the projection of x^k onto the randomly sketched system. The idea behind this method is to pick S in such a way that a projection onto the sketched system is substantially simpler than the solution of the original system Ax=b. Randomized Kaczmarz method is obtained by picking B to be the identity matrix, and S to be the i^{th} unit coordinate vector with probability Different choices of B and S lead to different variants of the method.

2. Constrain and Approximate

A seemingly different but entirely equivalent formulation of the method (obtained via Lagrangian duality) is where y is also allowed to vary, and where x^* is any solution of the system Ax=b. Hence, x^{k+1} is obtained by first constraining the update to the linear subspace spanned by the columns of the random matrix B^{-1}A^T S, i.e., to and then choosing the point x from this subspace which best approximates x^. This formulation may look surprising as it seems impossible to perform the approximation step due to the fact that x^ is not known (after all, this is what we are trying the compute!). However, it is still possible to do this, simply because x^{k+1} computed this way is the same as x^{k+1} computed via the sketch and project formulation and since x^* does not appear there.

5. Random Update

The update can also be written explicitly as where by M^\dagger we denote the Moore-Penrose pseudo-inverse of matrix M. Hence, the method can be written in the form, where h^k is a random update vector. Letting it can be shown that the system always has a solution y^k, and that for all such solutions the vector is the same. Hence, it does not matter which of these solutions is chosen, and the method can be also written as. The pseudo-inverse leads just to one particular solution. The role of the pseudo-inverse is twofold:

6. Random Fixed Point

If we subtract x^* from both sides of the random update formula, denote and use the fact that Ax^* = b, we arrive at the last formulation: where I is the identity matrix. The iteration matrix, I- B^{-1}Z, is random, whence the name of this formulation.

Convergence

By taking conditional expectations in the 6th formulation (conditional on x^k), we obtain By taking expectation again, and using the tower property of expectations, we obtain Gower and Richtarik show that where the matrix norm is defined by Moreover, without any assumptions on S one has By taking norms and unrolling the recurrence, we obtain

Theorem [Gower & Richtarik 2015]

Remark. A sufficient condition for the expected residuals to converge to 0 is \rho<1. This can be achieved if A has a full column rank and under very mild conditions on S. Convergence of the method can be established also without the full column rank assumption in a different way. It is also possible to show a stronger result:

Theorem [Gower & Richtarik 2015]

The expected squared norms (rather than norms of expectations) converge at the same rate: Remark. This second type of convergence is stronger due to the following identity which holds for any random vector x and any fixed vector x^*:

Convergence of Randomized Kaczmarz

We have seen that the randomized Kaczmarz method appears as a special case of the Gower-Richtarik method for B=I and S being the i^{th} unit coordinate vector with probability where a_i is the i^{th} row of A. It can be checked by direct calculation that

Further Special Cases

Algorithm 4: PLSS-Kaczmarz

Since the convergence of the (randomized) Kaczmarz method depends on a rate of convergence the method may make slow progress on some practical problems. To ensure finite termination of the method, Johannes Brust and Michael Saunders (academic) have developed a process that generalizes the (randomized) Kaczmarz iteration and terminates in at most m iterations to a solution for the consistent system Ax = b. The process is based on Dimensionality reduction, or projections onto lower dimensional spaces, which is how it derives its name PLSS (Projected Linear Systems Solver). An iteration of PLSS-Kaczmarz can be regarded as the generalization where A_{1:k,:} is the selection of rows 1 to k and all columns of A. A randomized version of the method uses k non repeated row indices at each iteration: where each i_j is in 1,2,...,m. The iteration converges to a solution when k =m. In particular, since it holds that and therefore x^{m+1} is a solution to the linear system. The computation of iterates in PLSS-Kaczmarz can be simplified and organized effectively. The resulting algorithm only requires matrix-vector products and has a direct form algorithm PLSS-Kaczmarz is input: matrix A right hand side b output: solution x such that Ax=b x := 0, P = [0] for k in 1,2,...,m do a := A(ik,:)' // Select an index ik in 1,...,m without resampling d := P' * a c1 := norm(a) c2 := norm(d) c3 := (bi k -x'a)/((c1-c2)(c1+c2)) p := c3*(a - P*(P'*a)) P := [ P, p/norm(p) ] // Append a normalized update'' x := x + p return x