Numerical analysis Iterative methods for linear systems Theorem

Kaczmarz method

Builds on System of linear equations Inner product Orthogonal projection Rank of a matrix Condition number Iterative method

Statement

Let $A$ be a real $m \times n$ matrix with nonzero rows $a_1^T, \dots, a_m^T$ , and let $b \in \R^m$ be such that the linear system $A x = b$ has a solution. For an index $i$ , the Kaczmarz step maps $x \in \R^n$ to $x + \frac{b_i - \ip{a_i}{x}}{\norm{a_i}^2} \, a_i,$ the orthogonal projection of $x$ onto the hyperplane $\set{y : \ip{a_i}{y} = b_i}$ . Start from any $x_0 \in \R^n$ .

(Cyclic version) Let $x_{k+1}$ be the Kaczmarz step from $x_k$ with $i = (k \bmod m) + 1$ . Then $x_k$ converges to a solution of $A x = b$ . If $x_0 = 0$ , the limit is the solution of least Euclidean norm.
(Randomized version, Strohmer and Vershynin) Suppose $A$ has rank $n$ , and let $x^*$ be the solution. Let $x_{k+1}$ be the Kaczmarz step from $x_k$ with $i$ drawn independently, equal to $j$ with probability $\norm{a_j}^2 / \norm{A}_F^2$ . Then $\mathbb{E} \norm{x_k - x^*}^2 \le \left( 1 - \kappa^{-2} \right)^k \norm{x_0 - x^*}^2$ , where $\kappa = \norm{A}_F \norm{A^{+}}_2$ .

Here $\norm{\cdot}$ is the Euclidean norm, $\norm{A}_F$ is the Frobenius norm and $A^{+}$ is the pseudoinverse.

Remarks

Each step is a projection onto a convex set that contains every solution. So for every solution $z$ , the distance $\norm{x_k - z}$ never increases, which drives the convergence proof. Each step adds a multiple of a row $a_i$ , so $x_k - x_0$ stays in the row space of $A$ . The solution of least norm is the only solution in the row space, which gives the claim for $x_0 = 0$ . Example: for the system $x_1 = 1$ , $x_2 = 1$ in $\R^2$ , two cyclic steps from $0$ give $(1, 0)$ and then the solution $(1, 1)$ . For orthogonal rows the method finishes after one sweep; for nearly parallel rows it zigzags and is slow. The number $\kappa$ is a scaled condition number, and it measures this effect in the randomized bound.

Going deeper

For a student

The Kaczmarz method touches one row at a time, so it suits huge systems whose rows are generated on the fly. It is a row-action iterative method, related to the Gauss–Seidel method applied to $A A^T y = b$ with $x = A^T y$ . Choosing rows at random with probability proportional to their squared norms gives a clean linear rate in expectation. This randomized version links the method to stochastic gradient descent for least squares.

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`CSETD54YDT`
URI	`m2://CSETD54YDT`
Kind	statement, theorem
Writing	W0 stub
MSC	65F10, 65F20
Status	This copy of the site has no build data. Run `m2 status CSETD54YDT`.
About	Iterative method
Uses	System of linear equations, Inner product, Orthogonal projection, Rank of a matrix, Condition number, Iterative method
Same as	Wikidata Q288600 Wikipedia Kaczmarz method

Markdown · JSON · Edit on GitHub

What this page needs for W1

an inventory row: the row of the inventory that the node accounts for (0 of 1)
a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.