Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 335 / 3

For admissible data, the Moore–Penrose inverse of an operator selects the minimum-norm least-squares solution:Its domain is $\mathrm{ran}A\oplus (\mathrm{ran}A{)}^{\perp }$. When the equation is consistent it is the solution of $Ax=y$ orthogonal to the kernel; for inconsistent admissible data it solves the normal equation for a linear inverse problem and projects away the component orthogonal to the range.

Take a singular system of a compact operator satisfying $A{v}_j={\sigma }_j{u}_j$, $A^{\ast }{u}_j={\sigma }_j{v}_j$. The generalized inverse isThe Picard criterion requires the squared coefficients to be summable. For an infinite-rank compact operator, ${\sigma }_j\to 0$, so $\Vert A^{†}{u}_j\Vert =1/{\sigma }_j\to \infty$ even though $\Vert u_j\Vert =1$. Hence $A^{†}$ is unbounded. Finite-rank compact operators do not have this obstruction. Data failing the Picard condition need not have a least-squares minimizer at all, even when the infimum residual is zero.

A regularization of an inverse problem replaces the unbounded generalized inverse by bounded operators $R_{\alpha }:Y\to X$ satisfying $R_{\alpha }y\to A^{†}y$ as $\alpha \downarrow 0$ on admissible exact data. A spectral regularization method can be writtenwhere $f_{\alpha }(\sigma )\to 1$ for fixed $\sigma >0$ while $f_{\alpha }(\sigma )/\sigma$ remains bounded for each fixed $\alpha$. A uniform bound on $f_{\alpha }$ supplies the usual dominated-convergence argument on exact data.

This defines $f_{\alpha }$ as the dimensionless damping factor. In the alternative convention calling the entire inverse coefficient the spectral filter, that filter is $f_{\alpha }(\sigma )/\sigma$. For data error bounded by $\delta$, a sufficient regularization parameter choice also requires $\delta \Vert R_{\alpha (\delta )}\Vert \to 0$; consistency alone does not control noise.

Minimize the data-misfit functional $J(x)=\frac{1}{2}\Vert Ax-y{\Vert }^2$. For a perturbation $h$, $DJ(x)[h]=\mathrm{Re}⟨A^{\ast }(Ax-y),h⟩$, so its gradient is $A^{\ast }(Ax-y)$. Gradient descent gives Landweber iteration:On a singular component, the iteration error is multiplied by $1-\tau {\sigma }_j^2$, whose modulus is less than one. Starting from zero preserves orthogonality to $\ker A$ and makes the exact-data iterates converge to $x^{†}$.

For the unit-step formulas and noise bound used below, rescale so that $\tau =1$ and $\Vert A\Vert \le 1$. Finite iteration count bounds amplification of small singular-value components; the stopping count provides the regularization parameter.

Use early stopping of Landweber iteration. For each finite $n$, the Landweber spectral filter gives a bounded reconstruction operator; as $n\to \infty$, it approaches the generalized inverse on exact admissible data. Taking $\alpha =1/n$, a sufficient rule for a convergent regularization of an inverse problem isor equivalently $\alpha (\delta )\to 0$ and $\delta /\sqrt{\alpha (\delta )}\to 0$. For example, $n(\delta )=\lfloor {\delta }^{-1}\rfloor$ satisfies both in the normalized problem. The first condition removes exact-data bias; the second prevents arbitrarily small measurement errors from being amplified by excessive iteration.

Add and subtract the exact-data iterate. The noise-bias decomposition for linear regularization givesso the supplied Landweber noise amplification bound yieldsWith unit step and zero initial iterate, the exact-data error is $x^{†}-x_n=(I-A^{\ast }A{)}^n{x}^{†}$. Its squared norm isby the dominated convergence theorem. Stopping with $n\to \infty$ but $n{\delta }^2\to 0$ therefore makes both errors vanish.

On each left singular vector $u_j$, use $A^{\ast }{u}_j={\sigma }_j{v}_j$ and $(I-A^{\ast }A)v_j=(1-{\sigma }_j^2)v_j$. The finite geometric series givesThus with $\alpha =1/n$, the dimensionless Landweber spectral filter isThe full inverse-coefficient convention instead uses $[1-(1-{\sigma }^2{)}^{1/\alpha }]/\sigma$. With general step $\tau$, replace ${\sigma }^2$ inside the power by $\tau {\sigma }^2$.

In the normalized problem, $0\le f_n(\sigma )\le \min (n{\sigma }^2,1)$, so the inverse coefficient is at most $\min (n\sigma ,1/\sigma )\le \sqrt{n}$. This verifies directly why finite iteration is stable and why admitting progressively smaller singular values eventually amplifies noise.