Normal equation for a linear inverse problem ($A^{\ast }Au=A^{\ast }f$)

The normal equation for $Au=f$ is $A^{\ast }Au=A^{\ast }f$. Its solutions minimize $\Vert Au-f\Vert$; when they exist, the unique solution orthogonal to $\ker A$ is the Moore--Penrose solution $A^{†}f$.

A least-squares solution minimizes $\Vert Ku-f\Vert$ over the source Hilbert space. It exists exactly when $f\in \mathcal{R}(K)\oplus \mathcal{R}(K{)}^{\perp }$, and then the solutions form a closed affine subspace with direction $\mathcal{N}(K)$.

For a bounded linear operator $K:U\to V$ between Hilbert spaces, a least-squares solution for $f$ exists exactly when $P_{\overline{\mathcal{R}(K)}}f\in \mathcal{R}(K)$, equivalently $f\in \mathcal{R}(K)\oplus \mathcal{R}(K{)}^{\perp }$. Indeed the orthogonal projection onto the closure uniquely minimizes distance to that closed space, and it can be realized by $Ku$ exactly under this condition. Thus all data admit least-squares solutions exactly when the range is closed.

The orthogonal projection of a prescribed point $u_0$ onto the affine subspace of least-squares solutions is unique. It retains $u_0$'s null space component and chooses the determined component from the Moore–Penrose inverse of an operator.

For a compact operator $A:X\to Y$ between Hilbert spaces, a singular system consists of positive singular values and orthonormal families withThe $v_j$ form a basis of $(\ker A{)}^{\perp }$, and the $u_j$ form a basis of the closure of its operator range. The family is finite when $A$ has finite rank. For infinite rank, the singular values can be ordered with ${\sigma }_j\downarrow 0$.

The expansion $Ax={\sum }_j{\sigma }_j⟨x,v_j⟩u_j$ separates channels with different data sensitivity. Inverting a channel divides by ${\sigma }_j$, explaining why an infinite-rank compact operator generally has an unbounded inverse on its range. Spectral regularization methods replace those inverse coefficients by bounded filters.

For the diagonal operator on sequence space $A(x_1,x_2,\dots )=(x_1,x_2/2,x_3/3,\dots )$ on L2 space, the standard coordinate vectors give ${\sigma }_j=1/j$. A small error in a late output coordinate can correspond to a much larger change in the unknown. No infinite sequence tending to zero is required for a finite-rank operator.

The displayed singular value system applies when the Fourier multipliers $c_n$ are nonzero. The phase in the left singular vector is necessary for complex kernels. If a multiplier vanishes, its mode instead belongs to the corresponding null spaces and is excluded from the positive singular system.

For a compact operator with singular system $({\sigma }_j,u_j,v_j)$, the datum $f$ lies in the domain of $A^{†}$ exactly when its component in $\overline{\mathrm{ran}A}$ satisfies

For a bounded linear operator $A$ between Hilbert spaces, Landweber iteration applies gradient descent to the squared residual:For nonzero $A$, the standard uniform step range is $0<\tau <2/\Vert A{\Vert }^2$. Starting at zero givesThe iteration introduces no component in $\ker A$. On data admitting a least-squares solution, it converges to the minimum-norm least-squares solution in this step range.

A singular value $\sigma$ has error multiplier $1-\tau {\sigma }^2$. Small singular values converge slowly, so a finite iteration admits well-determined components before aggressively fitting poorly determined ones. Continuing indefinitely on noisy data can amplify precisely those late components. Early stopping of Landweber iteration therefore acts as regularization; residual decrease alone is not a guarantee of reconstruction accuracy. The Landweber spectral filter makes this progression explicit.

For nonzero compact operator $A$, step $0<\tau <2/\Vert A{\Vert }^2$, and data admitting a minimum-norm least-squares solution $x^{†}$, zero-initialized Landweber iteration satisfiesThe Picard criterion makes the majorant summable, so the dominated convergence theorem proves this limit. No mesh-independent or singular-value-independent strict contraction factor is required. At $\tau =2/\Vert A{\Vert }^2$, the top singular mode has multiplier $-1$ and may not converge. Without solvable projected data, the iterates need not have a limit in the solution Hilbert space, even when their residuals approach the least-squares infimum.

Initialize Landweber iteration by Tikhonov regularization, then use step $1/\alpha$. Writing $B=A^{\ast }A$ and $R=I-B/\alpha$, the iterate is $x_n=R^n(B+\alpha I{)}^{-1}{A}^{\ast }y+{\alpha }^{-1}{\sum }_{j=0}^{n-1}{R}^j{A}^{\ast }y$. For nonzero $A$, the sufficient convergence condition is $\alpha >\Vert A{\Vert }^2/2$. This explicit method differs from Iterated Tikhonov regularization, whose update is $(B+\alpha I)x_{n+1}=\alpha x_n+A^{\ast }y$.

In a singular system of a compact operator, Landweber iteration with a Tikhonov initial value has coefficients $g_{\alpha ,n}({\sigma }_i)(y,u_i)$. Summing the finite geometric series gives the displayed filter. For fixed $n$, $g_{\alpha ,n}(\sigma )=(n+1)\sigma /\alpha +O({\sigma }^3)$ at zero, so each finite iterate is bounded. Under $\alpha >\Vert A{\Vert }^2/2$ the filter approaches $1/\sigma$ on every positive singular mode; noisy data require early stopping of Landweber iteration.

The positive parameter $\tau$ is the step in Landweber iteration. For a nonzero bounded linear operator $A$, a standard data-independent condition guaranteeing convergence from zero on data admitting a least-squares solution isIt makes $|1-\tau {\sigma }^2|<1$ on every nonzero singular mode. Thus $\Vert A\Vert <2$ permits $\tau =1/2$, while a unit step is guaranteed by $\Vert A\Vert <\sqrt{2}$.

This is a uniform sufficient range, not a necessary condition for every particular datum. A datum with no component in an unstable mode can still converge for a larger step. At the endpoint $\tau =2/\Vert A{\Vert }^2$, an attained top mode has multiplier $-1$ and can oscillate indefinitely. The strong convergence of relaxed Landweber iteration states the exact-data result without assuming a singular-value-independent contraction rate.

Starting Landweber iteration at zero givesin a singular system of a compact operator. The dimensionless damping filter is $f_n(\sigma )=1-(1-\tau {\sigma }^2{)}^n$. If the full inverse coefficient is called the filter instead, it is $f_n(\sigma )/\sigma$; these conventions describe the same operator.

Starting Landweber iteration at zero with fixed step $\tau$, the full data-to-solution coefficient on a singular value $\sigma >0$ isThis follows by summing the scalar geometric series in a singular system of a compact operator. For fixed $n$, $g_n(\sigma )=n\tau \sigma +O({\sigma }^3)$ near zero and extends with $g_n(0)=0$. Its dimensionless damping factor is $\sigma g_n(\sigma )$, so the two common filter conventions must not be confused. Writing $\alpha =1/n$ uses a discrete parameter sequence; if negative multipliers occur, noninteger real powers are not a definition of the same iteration.

For $\tau =1$ and $\Vert A\Vert \le 1$, $0\le 1-(1-{\sigma }^2{)}^n\le \min (n{\sigma }^2,1)$ givesThus a data error of norm at most $\delta$ produces an iterate error at most $\sqrt{n}\delta$.

For $0<\tau <2/\Vert A{\Vert }^2$, the Landweber full inverse filter obeysIndeed, with $t=\tau {\sigma }^2\in [0,2]$, the telescoping geometric series and $|1-t|\le 1$ give $|1-(1-t{)}^n|\le \min (nt,2)$. Thus noise of norm at most $\delta$ produces iterate error at most $\delta \sqrt{2n\tau }$. If $\tau \Vert A{\Vert }^2\le 1$, replace 2 by 1 to obtain $\delta \sqrt{n\tau }$. Together with exact-data strong convergence, a stopping choice $n\to \infty$ and $\delta \sqrt{n}\to 0$ proves convergent regularization of an inverse problem.

The Landweber spectral filter progressively admits smaller singular-value components. Its approximation bias tends to zero on exact admissible data, but its noise amplification grows. With $\Vert A\Vert \le 1$, a sufficient a priori regularization parameter choice is $n(\delta )\to \infty$ and $\sqrt{n(\delta )}\delta \to 0$. Taking regularization parameter $\alpha =1/n$ expresses this as $\alpha \to 0$ and $\delta /\sqrt{\alpha }\to 0$; the noise-bias decomposition for linear regularization proves convergence.

For a bounded operator $A:X\to Y$ between Hilbert spaces, the Moore–Penrose inverse maps admissible data to the unique minimum-norm least-squares solution. If $({\sigma }_j,u_j,v_j)$ is a singular system of a compact operator, thenon the data for which this series converges.

More precisely, its domain is $\mathrm{ran}A\oplus (\mathrm{ran}A{)}^{\perp }$. It vanishes on $(\mathrm{ran}A{)}^{\perp }$ and takes values in $(\ker A{)}^{\perp }$. An infinite-rank compact operator on infinite-dimensional spaces has singular values approaching zero, so its inverse on its range is generally unbounded; Picard criterion specifies admissible data.

A minimum-norm least-squares solution minimizes $\Vert Ax-y\Vert$ and, among all such minimizers, minimizes $\Vert x\Vert$. It lies in $(\ker A{)}^{\perp }$ and equals $A^{†}y$ when the Moore–Penrose inverse of an operator is defined at $y$.