The Kaczmarz method or Kaczmarz's algorithm is an iterative algorithm for solving linear equation systems A x = b {\displaystyle Ax=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
The original Kaczmarz algorithm solves a complex-valued system of linear equations A x = b {\displaystyle Ax=b} . Let a i {\displaystyle a_{i}} be the conjugate transpose of the i {\displaystyle i} -th row of A {\displaystyle A} . Initialize x 0 {\displaystyle x_{0}} to be an arbitrary complex-valued initial approximation. (e.g. x 0 = 0 {\displaystyle x_{0}=0} .) For k = 0 , 1 , … {\displaystyle k=0,1,\ldots } compute:
where i 0 , i 1 , i 2 , … {\displaystyle i_{0},i_{1},i_{2},\dots } iterates over the rows of A {\displaystyle A} in any order, deterministic or random. It is only necessary that each row is iterated infinitely often. When we are in the space of real vectors, the Kaczmarz iteration has a clear geometric meaning. It means projecting x k {\textstyle x_{k}} orthogonally to the hyperplane defined by { x : ⟨ a i , x ⟩ = b i } {\textstyle \{x:\langle a_{i},x\rangle =b_{i}\}} . In this interpretation, it is clear that if the Kaczmarz iteration converges, then it must converge to one of the solutions to A x = b {\textstyle Ax=b} . A more general algorithm can be defined using a relaxation parameter λ k {\displaystyle \lambda ^{k}}
x k + 1 = x k + λ k b i k − ⟨ a i k , x k ⟩ ‖ a i k ‖ 2 a i k {\displaystyle x_{k+1}=x_{k}+\lambda _{k}{\frac {b_{i_{k}}-\langle a_{i_{k}},x_{k}\rangle }{\|a_{i_{k}}\|^{2}}}a_{i_{k}}}
If the system has a solution, x k {\displaystyle x_{k}} converges to the minimum-norm solution, provided that the iterations start with the zero vector. If the rows are iterated in order, and λ k = 1 {\displaystyle \lambda _{k}=1} , then convergence is exponential.
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 . {\displaystyle \|a_{i}\|^{2}.}
… excerpt ends here. Continue reading the full article.
