Kaczmarz method

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. x k + 1 = x k + b i − ⟨ a i , x k ⟩ ‖ a i ‖ 2 a i ¯ {displaystyle x^{k+1}=x^{k}+{frac {b_{i}-langle a_{i},x^{k} angle }{|a_{i}|^{2}}}{overline {a_{i}}}}     (1) ∀ z ∈ C n : ∑ j = 1 m | ⟨ z , a j ⟩ | 2 ≥ ‖ z ‖ 2 ‖ A − 1 ‖ 2 {displaystyle forall zin mathbb {C} ^{n}:quad sum _{j=1}^{m}|langle z,a_{j} angle |^{2}geq {frac {|z|^{2}}{|A^{-1}|^{2}}}}     (2) ∀ z ∈ C n : ∑ j = 1 m ‖ a j ‖ 2 ‖ A ‖ 2 | ⟨ z , a j ‖ a j ‖ ⟩ | 2 ≥ κ ( A ) − 2 ‖ z ‖ 2 {displaystyle forall zin mathbb {C} ^{n}:quad sum _{j=1}^{m}{frac {|a_{j}|^{2}}{|A|^{2}}}left|leftlangle z,{frac {a_{j}}{|a_{j}|}} ight angle ight|^{2}geq kappa (A)^{-2}{|z|^{2}}}     (3) ∀ z ∈ C n : E | ⟨ z , Z ⟩ | 2 ≥ κ ( A ) − 2 ‖ z ‖ 2 {displaystyle forall zin mathbb {C} ^{n}:quad mathbb {E} |langle z,Z angle |^{2}geq kappa (A)^{-2}{|z|^{2}}}     (4) 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). Let A x = b {displaystyle Ax=b} be a system of linear equations, let m {displaystyle m} the number of rows of A, a i {displaystyle a_{i}} be the i {displaystyle i} th row of complex-valued matrix A {displaystyle A} , and let x 0 {displaystyle x^{0}} be arbitrary complex-valued initial approximation to the solution of A x = b {displaystyle Ax=b} . For k = 0 , 1 , … {displaystyle k=0,1,ldots } compute: where i = k mod m , i = 1 , 2 , … m {displaystyle i=k{mod {m}},i=1,2,ldots m} and a i ¯ {displaystyle {overline {a_{i}}}} denotes complex conjugation of a i {displaystyle a_{i}} . If the system is consistent, x k {displaystyle 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 λ k {displaystyle 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. Recently, 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}.}