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.

A singular system $({\sigma }_j,u_j,v_j)$ for a compact operator $A:X\to Y$ has positive singular values ${\sigma }_j\to 0$ and orthonormal vectors satisfying $A{v}_j={\sigma }_j{u}_j$ and $A^{\ast }{u}_j={\sigma }_j{v}_j$. It diagonalizes spectral regularization methods.

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

Landweber iteration applies $u_{n+1}=u_n+\tau A^{\ast }(f-A{u}_n)$. Starting at zero,and early stopping regularizes the inverse problem.

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 relaxation parameter $\tau$ controls the step in Landweber iteration. Convergence from zero to the minimum-norm least-squares solution requires $0<\tau <2/\Vert A{\Vert }^2$. Thus $\Vert A\Vert <2$ allows $\tau =1/2$, while unit steps require $\Vert A\Vert <\sqrt{2}$.

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$.