Landweber iteration

Remarks

Write $x^\dagger = A^\dagger y$; then $A^* y = A^* A x^\dagger$. The error satisfies $x_k(y) - x^\dagger = -(I - \omega A^* A)^k x^\dagger$. The self-adjoint operator $A^* A$ has spectrum in $[0, \norm{A}^2]$, and $\abs{1 - \omega t} < 1$ for $0 < t \le \norm{A}^2$. Since $x^\dagger$ is orthogonal to $\ker A$, the spectral theorem gives $(I - \omega A^* A)^k x^\dagger \to 0$, which is part 1. For part 2, $x_k(z) = \sum_{j < k} (I - \omega A^* A)^j \omega A^* z$, and a spectral bound on $\sqrt{\omega t} \sum_{j<k} (1 - \omega t)^j$ gives the factor $\sqrt{\omega k}$.

The iteration is gradient descent with fixed step $\omega$ for $\tfrac12 \norm{A x - z}^2$. When $\mathcal{R}(A)$ is not closed, $x_k(y^\delta)$ first approaches $x^\dagger$ and then diverges, a behavior called semi-convergence. So the iteration index plays the role of the regularization parameter, and one must stop early, for example by the discrepancy principle. Without the condition $\omega < 2/\norm{A}^2$, components along large singular values are amplified and the iteration diverges.

Going deeper

For a student

Landweber iteration is the simplest iterative regularization method, and it is the model for others such as conjugate gradients on the normal equations. Stopping after $k$ steps acts like a filter on the singular values: components with $\omega \sigma^2 k \gg 1$ are recovered and the others are damped. It converges slowly, but it extends directly to nonlinear operators and to constraints by adding a projection. It was introduced by Louis Landweber in 1951.