Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 326 (Inverse Problems)

Use the Hilbert space interpretation of a linear inverse problem, with a bounded linear operator $K:\mathcal{U}\to \mathcal{V}$. A least-squares solution minimizes $\Vert Ku-f{\Vert }_{\mathcal{V}}$ over $u\in \mathcal{U}$. A minimum-norm least-squares solution additionally has the smallest $\mathcal{U}$-norm among all least-squares solutions. When the equation is consistent this is the smallest-norm exact solution.

The least-squares solutions form a nonempty closed affine subspace precisely whenThe closest point theorem in a Hilbert space then gives a unique nearest point to zero, hence a unique minimum-norm least-squares solution. Equivalently, it is the unique least-squares solution in $\mathcal{N}(K{)}^{\perp }$. If $\mathcal{R}(K)$ is closed, this exists for every datum; a nonclosed operator range can leave some data without any least-squares solution.

For example, on the l2 sequence space, take $(Ku{)}_n=u_n/n$ and $f_n=1/n$. The equation would require $u_n=1$ for every $n$, which is not square summable. However, setting the first $N$ coordinates of $u$ to one and the rest to zero givesThus the least-squares infimum is zero but is not attained, and no minimum-norm least-squares solution exists for these data.

The map $K^{\ast }K$ is a bounded linear operator, so the inverse image of the closed singleton $\{K^{\ast }f\}$ is closed. That inverse image is also a convex set: if $K^{\ast }Ku=K^{\ast }Kv=K^{\ast }f$, every convex combination has the same image.

The identity $\mathcal{N}(K^{\ast })=\mathcal{R}(K{)}^{\perp }$ givesConsequently such a $u$ exists exactly when $f$ is the sum of an element of $\mathcal{R}(K)$ and one of its orthogonal complement. ThusThese are precisely the least-squares solutions. Indeed, if $r=Ku-f$ and $K^{\ast }r=0$, then for every $h$ the Pythagorean identity givesConversely, differentiating the squared residual along any real direction $h$ forces $\mathrm{Re}⟨K^{\ast }r,h⟩=0$, hence the normal equation for a linear inverse problem. For any $u_{\ast }\in \mathbb{L}$, the difference of two solutions of the normal equation for a linear inverse problem lies in $\mathcal{N}(K)$, since $⟨K^{\ast }Kh,h⟩=\Vert Kh{\Vert }^2$. Thereforea closed affine subspace; the empty case is closed and convex as well.

The Moore–Penrose inverse of an operator is the linear mapthat assigns each admissible datum its minimum-norm least-squares solution. If $f=y+z$ with $y\in \mathcal{R}(K)$ and $z\in \mathcal{R}(K{)}^{\perp }$, then $K^{†}f$ is the unique $u\in \mathcal{N}(K{)}^{\perp }$ satisfying $Ku=y$. In particular it vanishes on $\mathcal{R}(K{)}^{\perp }$, andThe continuity criterion, with the inherited data norm on its domain, isFor a closed operator range, the restriction of $K$ from $\mathcal{N}(K{)}^{\perp }$ to $\mathcal{R}(K)$ is a bounded bijection between Banach spaces, so its inverse is bounded by the bounded inverse theorem. Conversely, if $K^{†}$ is bounded and $K{u}_n\to y$, replace each $u_n$ by $P_{\mathcal{N}(K{)}^{\perp }}{u}_n=K^{†}K{u}_n$. This is a Cauchy sequence, hence converges to $u$, and $Ku=y$. Thus every limit of range elements remains in the operator range.

Write $u^{†}=K^{†}f$. Every least-squares solution is $u^{†}+w$ for some $w\in \mathcal{N}(K)$, while $u^{†}\in \mathcal{N}(K{)}^{\perp }$. Decompose $u_0=P_{\mathcal{N}(K)}{u}_0+P_{\mathcal{N}(K{)}^{\perp }}{u}_0$ using orthogonal projections. Then the Pythagorean identity givesThe first term is independent of $w$, and the second vanishes at exactly one point. Hence the unique nearest least-squares solution isGeometrically this is the orthogonal projection of $u_0$ onto the closed affine subspace of least-squares solutions.

A finite-valued global minimizer of the functional $E$ is an element $\bar{u}\in \mathrm{dom}E$ satisfyingHere $\mathrm{dom}E$ is its effective domain. The finite-value convention avoids treating an infeasible problem as solved.

The functional is a proper extended-real function if its effective domain is nonempty; the specified codomain already excludes $-\infty$. It has coercivity if $\Vert u_n\Vert \to \infty$ always implies $E(u_n)\to +\infty$, equivalently every finite sublevel set is bounded. It is $\tau$-sequentially lower semicontinuous ifThe topology in this definition matters: norm sequential lower semicontinuity and weak sequential lower semicontinuity need not coincide for a nonconvex functional.

On $\mathcal{U}=\mathbb{R}$ with its usual topology, the following examples isolate the three failures.

A nonproper functional is $E(x)=+\infty$ for every $x$. Its effective domain is empty, so it has no finite-valued global minimizer. It nevertheless has coercivity and is sequentially lower semicontinuous. If a minimizer is instead defined only by $E(x)=\inf E$ without requiring finiteness, every point formally minimizes this function; under that convention the requested nonproper counterexample is impossible with the given codomain.

A noncoercive functional is $E(x)=e^x$. It is a proper extended-real function and is continuous, but its infimum zero is approached as $x\to -\infty$ and is never attained. Hence it has no global minimizer.

A failure of sequential lower semicontinuity isIt is a proper extended-real function with coercivity, but $E(1/n)\to 0<E(0)$. Its infimum is zero, while every function value is positive. Thus it has no global minimizer.

The epigraph isAssume $E$ is $\tau$-sequentially lower semicontinuous. If $(u_n,t_n)$ lies in the epigraph and converges to $(u,t)$ in the product topology, thenThe limit remains in the epigraph, so it is a sequentially closed set.

Conversely, suppose the epigraph is a sequentially closed set and sequential lower semicontinuity fails along $u_n\stackrel{\tau }{\to }u$. Choose a finite real number $a$ with $\mathrm{liminf}E(u_n)<a<E(u)$. There is a subsequence along which $E(u_{n_j})\le a$. Thus $(u_{n_j},a)$ lies in the epigraph and converges to $(u,a)$, which does not lie there. This contradiction provesThis is a sequential statement; identifying it with ordinary closedness requires an appropriate assumption on the topology.

The direct method in the calculus of variations gives the following existence theorem. Suppose bounded sequences in the Banach space $\mathcal{U}$ have $\tau$-convergent subsequences, and $E$ is a proper extended-real function with coercivity and is $\tau$-sequentially lower semicontinuous. Then $E$ has a finite-valued global minimizer.

To prove this, properness makes $m=\inf E<+\infty$. First rule out $m=-\infty$: a sequence with $E(u_n)\to -\infty$ eventually lies in a fixed sublevel set, which is bounded by coercivity. A $\tau$-convergent subsequence would then have a limit $u$ with $E(u)\le -\infty$, contradicting the codomain. Hence $m$ is finite.

Choose a minimizing sequence with $E(u_n)\to m$. It eventually belongs to the bounded sublevel set $\{E\le m+1\}$. Extract $u_{n_j}\stackrel{\tau }{\to }\bar{u}$. By sequential lower semicontinuity,Thus $E(\bar{u})=m$. In particular, a reflexive Banach space with the weak topology supplies the required subsequence property by weak sequential compactness of bounded sequences in a reflexive Banach space. A strictly convex function has at most one minimizer; this is an additional property, not part of the existence theorem.

Take the weak topology on the reflexive Banach space $\mathcal{U}$. A bounded linear operator is weak-to-weak continuous: $u_n\rightharpoonup u$ implies $⟨K{u}_n,v⟩\to ⟨Ku,v⟩$ for every $v\in \mathcal{V}$, by its adjoint operator. The weak lower semicontinuity of the Hilbert norm therefore makes $D(u)=\Vert Ku-f\Vert$ weakly sequentially lower semicontinuous.

This functional is finite everywhere and nonnegative. If it has coercivity, the direct method in the calculus of variations supplies a global minimizer $\bar{u}$. Squaring the residual does not change its global minimizers. Here the adjoint operator has codomain ${\mathcal{U}}^{\ast }$, since the source is a Banach space. Differentiating the squared residual along every real direction $h\in \mathcal{U}$ gives $\mathrm{Re}⟨K^{\ast }(K\bar{u}-f),h⟩=0$ in the dual pairing, hence the normal equation for a linear inverse problem $K^{\ast }(K\bar{u}-f)=0$. HenceThe converse fails. For $K:{\mathbb{R}}^2\to \mathbb{R}$, $K(x,y)=x$, and $f=1$, the datum is in the operator range, but $D(1,n)=0$ while $\Vert (1,n)\Vert \to \infty$. Thus admissible data do not imply coercivity of the residual; an unpenalized null space already prevents it.

Fix a singular system of a compact operator, with $K{v}_j={\sigma }_j{w}_j$ and $K^{\ast }{w}_j={\sigma }_j{v}_j$, ${\sigma }_j>0$. A spectral regularization method has the formIt annihilates $\mathcal{R}(K{)}^{\perp }$. Standard sufficient spectral filter conditions are boundedness of ${\sup }_{0<\sigma \le \Vert K\Vert }|\sigma g_{\alpha }({\sigma }^2)|$ for each $\alpha$, pointwise $\lambda g_{\alpha }(\lambda )\to 1$ as $\alpha \downarrow 0$ for $\lambda >0$, and a uniform bound on $|\lambda g_{\alpha }(\lambda )|$. These give bounded linear operators and convergence on the domain of the Moore–Penrose inverse of an operator by the Picard criterion and dominated convergence theorem.

For Tikhonov regularization,This can be computed by solving the Tikhonov normal equation, without knowing the singular value decomposition.

For spectral cutoff regularization, takewith value zero at $\lambda =0$. Only singular values ${\sigma }_j\ge \sqrt{\alpha }$ are inverted. Here $g_{\alpha }$ multiplies $\sigma$; conventions calling the full coefficient $\sigma g_{\alpha }({\sigma }^2)$ the spectral filter are equivalent.

Suppose each $R_{\alpha }:\mathcal{V}\to \mathcal{U}$ is a bounded linear operator and $R_{\alpha }f\to K^{†}f$ for every $f\in \mathcal{D}(K^{†})$ as $\alpha \downarrow 0$. A standard sufficient a priori regularization parameter choice satisfiesFor every datum with $\Vert f^{\delta }-f\Vert \le \delta$, the noise-bias decomposition for linear regularization givesThus the parameter rule gives a convergent regularization of an inverse problem, uniformly over data in the prescribed noise ball for each fixed admissible exact datum. For Tikhonov regularization, $\Vert R_{\alpha }\Vert \le 1/(2\sqrt{\alpha })$, so $\alpha \to 0$ and $\delta /\sqrt{\alpha }\to 0$ suffice. The same sufficient noise scaling holds for spectral cutoff regularization.

Starting from zero, the Landweber iteration isFor $K\ne 0$, take the step size $0<\tau <2/\Vert K{\Vert }^2$. Iterating the linear update givesand its Landweber spectral filter in a singular system of a compact operator isThe strict upper step size bound makes $|1-\tau {\sigma }_j^2|<1$ for every positive singular value. A common more restrictive choice is $0<\tau \le \Vert K{\Vert }^{-2}$, giving nonnegative damping factors. Each finite iterate is bounded and linear; early stopping of Landweber iteration controls the amplification of noise as smaller singular values are progressively inverted. If $K=0$, every iterate is zero for any positive step size.

For Iterated Tikhonov regularization, set $A=K^{\ast }K$ and $B=(I+\tau A{)}^{-1}$. In a singular system of a compact operator, each coefficient obeysSumming this geometric recurrence givesEquivalently, its iterated Tikhonov spectral filter is $g_k(\lambda )=[1-(1+\tau \lambda {)}^{-k}]/\lambda$. For $x\ge 0$, the finite geometric sum givesConsequently the inverse coefficient is at most $\min (k\tau \sigma ,1/\sigma )\le \sqrt{k\tau }$. Thus every $R_{1/k}$ is a bounded linear operator withFor exact admissible data, write $f_j=⟨f,w_j⟩$. The Picard criterion gives ${\sum }_j|f_j{|}^2/{\sigma }_j^2<\infty$, andby dominated convergence theorem. Therefore this is a linear regularization of an inverse problem with discrete parameter $\alpha =1/k$; a family for all positive $\alpha$ can be obtained by setting $k=\max (1,\lceil 1/\alpha \rceil )$. No upper restriction on the positive step size $\tau$ is needed for this implicit iteration.

Let $\eta =f^{\delta }-f$, so $\Vert \eta \Vert \le \delta$. By linearity, $u_{\delta }^{(k)}-u^{(k)}=R_{1/k}\eta$. The preceding operator norm estimate givesMoreover, $K{R}_{1/k}$ has factors $1-(1+\tau {\sigma }_j^2{)}^{-k}$ on the data singular vectors, and is zero on $\mathcal{R}(K{)}^{\perp }$. Every factor is in $[0,1]$, henceThus, for any fixed $k$, one can take $C=\sqrt{k\tau }$ and $\gamma =1$.

The first constant cannot generally be chosen independently of the iteration count. On the l2 sequence space, take $(Ku{)}_n=u_n/n$, $\tau =1$, and noise $\eta =\delta e_n$. At $k=n^2$ the solution perturbation has normThis disproves a uniform-in-$k$ interpretation of the stated first estimate. For a closed operator range, boundedness of the Moore–Penrose inverse of an operator instead supplies the uniform constant $\Vert K^{†}\Vert$.

With exact data $f=K{u}^{†}$, the iteration error obeysThe source condition for quadratic regularization $u^{†}=K^{\ast }v$ excludes any null space component. Using its singular system of a compact operator coefficients,By Bernoulli's inequality, $(1+\tau {\sigma }^2{)}^k\ge 1+k\tau {\sigma }^2$. Also $1+k\tau {\sigma }^2\ge 2\sqrt{k\tau }\sigma$. ThereforeSumming the squared coefficients and using Bessel inequality yieldsThis is an a priori error rate from the source condition for quadratic regularization, with constant independent of $k$.

Write the residual of an inverse problem as $r_k=K{u}_{\delta }^{(k)}-f^{\delta }$. The iteration can be rearranged asApplying $K$ gives $(I+\tau K{K}^{\ast })r_{k+1}=r_k$. Since $K{K}^{\ast }$ is a positive operator, its resolvent operator $(I+\tau K{K}^{\ast }{)}^{-1}$ has operator norm at most one. HenceMore explicitly, taking the inner product of the residual equation with $r_{k+1}$ givesThis directly proves the same monotonicity by the Cauchy-Schwarz inequality, including the case $r_{k+1}=0$. An unresolvable data component in $\mathcal{R}(K{)}^{\perp }$ remains unchanged.

Assume $K{u}^{†}=f$, as in the exact-solution setting used for the preceding source condition for quadratic regularization. Let $r=r_{k+1}$, $\eta =f^{\delta }-f$, and $s=u_{\delta }^{(k+1)}-u_{\delta }^{(k)}=-\tau K^{\ast }r$. Then $K(u_{\delta }^{(k+1)}-u^{†})=r+\eta$, and expanding the two squared errors givesThe Cauchy-Schwarz inequality supplies the last line. Thus while the residual remains at least the noise bound,Compatibility of the exact data is essential. If only $f\in \mathcal{D}(K^{†})$ is retained, let $Kx=(x,0)$, $f=(0,1)$, $f^{\delta }=(1/2,1)$, $\delta =1/2$ and $\tau =1$. The minimum-norm least-squares solution is zero, but the first iterate is $1/4$ and its residual norm is $\sqrt{17}/4>\delta$. Its error has increased from zero. Thus the original assertion uses the implicit exact-data assumption from part (c), and is false without it.

The Iterated Tikhonov regularization update is the proximal operator stepThe objective has coercivity and is weakly sequentially lower semicontinuous and strongly convex, so the direct method in the calculus of variations and uniqueness of a minimizer of a strictly convex function give existence and uniqueness. Its gradient equation iswhich is exactly $(I+\tau K^{\ast }K)u=u_{\delta }^{(k)}+\tau K^{\ast }{f}^{\delta }$. The second term penalizes the change from the previous iterate, rather than the norm of $u$ relative to zero.

First interpret the stated well-definedness as including uniqueness of the global minimizer for each positive parameter. Under that assumption, the parameter continuity of variational regularization follows from the direct method in the calculus of variations argument below.

Let $M=D(0)=\Vert f{\Vert }^2/2$. For large $n$, ${\alpha }_n\ge \beta :=\alpha /2$. Comparison with zero, using $J(0)=0$, givesCoercivity of ${\Phi }_{\beta ,f}$ therefore bounds the sequence. Take a $\tau$-convergent subsequence with limit $\bar{u}$. For any $v\in \mathrm{dom}J$, optimality givesThe last two terms vanish. Sequential lower semicontinuity at the fixed parameter $\alpha$ implies ${\Phi }_{\alpha ,f}(\bar{u})\le {\Phi }_{\alpha ,f}(v)$. Thus every cluster point is a global minimizer at $\alpha$. Uniqueness makes it $u_{\alpha }$, and the subsequence property provesIndeed, a subsequence staying outside a neighborhood of $u_{\alpha }$ would have a further convergent subsequence, whose limit must be $u_{\alpha }$, a contradiction.

The listed existence hypotheses alone do not imply uniqueness or convergence of an arbitrary selection. For example, on ${\mathbb{R}}^2$, set $K(x,y)=x$, $f=1$, andThis is nonnegative, convex, continuous and has $J(0)=0$; every ${\Phi }_{\alpha ,f}$ has coercivity. Its minimizers are $(1/(1+2\alpha ),y)$ for all $|y|\le 1$. Along ${\alpha }_n=\alpha +1/n$, selecting $y_n=(-1{)}^n$ prevents convergence. Without uniqueness, the valid conclusion is that every cluster point minimizes the limiting objective.

Use the value function of variational regularization in its selection-independent formBecause $J\ge 0$, each objective is non-decreasing with $\alpha$, hence so is its infimum. For $0\le t\le 1$, the affine function of the parameter at each fixed $u$ givesThus $\Psi$ is concave.

For continuity, on any interval $0<a\le \alpha <\beta \le b$, comparison using $u_{\alpha }$ givesIt follows that $\Psi$ is a locally Lipschitz function, hence continuous, on $(0,\infty )$. Therefore the value function of variational regularization is non-decreasing, concave and continuous. No uniqueness of minimizers is needed for these conclusions.

For $0<\alpha <\beta$, abbreviate $D_{\alpha }=D(u_{\alpha })$ and $J_{\alpha }=J(u_{\alpha })$. Optimality of the two variational regularization solutions givesAdding shows $(\beta -\alpha )(J_{\beta }-J_{\alpha })\le 0$, so $J_{\beta }\le J_{\alpha }$. Rearranging each comparison then gives the monotonicity of data fidelity and regularization penaltyHence the regulariser value is non-increasing and the data misfit is non-decreasing with the parameter. These inequalities hold for any choices of minimizers at the two distinct parameters, including when uniqueness fails.

Comparison with zero and nonnegativity of the two terms givesThereforeFor a concrete variational regularization example, take a Hilbert space and $J(u)=\Vert u{\Vert }^2$. The bound forces $u_{\alpha }\to 0$ in norm. Since $K$ is a bounded linear operator, $K{u}_{\alpha }\to 0$, and continuity of the squared norm givesThe same conclusion is not forced by $J(u_{\alpha })\to 0$ for a regulariser with a nontrivial zero set.

The small-parameter limit depends on data compatibility with the regularizer domain. SetFor every such $v$, optimality givesTaking the upper limit as $\alpha \downarrow 0$ and then the infimum over $v$ proves ${\Phi }_{\alpha ,f}(u_{\alpha })\to m$. Its two nonnegative contributions above $m$ must vanish, yielding the general resultIn particular, the requested zero-misfit limit holds when $f\in \overline{K(\mathrm{dom}J)}$. A sufficient condition is an exact solution $v$ with $Kv=f$ and $J(v)<\infty$; thenMembership of $f$ in $\mathcal{R}(K)$ alone is insufficient. Take $\mathcal{U}=\mathcal{V}=\mathbb{R}$, $K=I$, $f=1$, and $J$ the indicator functional of a constraint set $\{0\}$. All positive-parameter objectives are proper extended-real functions with coercivity and sequential lower semicontinuity, with the unique minimizer $u_{\alpha }=0$, yet $D(u_{\alpha })=1/2$ for every $\alpha$. Thus the first printed limit needs compatibility with the regulariser's effective domain; the second limit remains true under the given assumptions.

For a functional $E$ on a real Banach space, its convex conjugate is defined on the dual space byHere $⟨p,u⟩$ is the dual pairing. For complex spaces, use its real part, equivalently regard the space as real for convex analysis. The convex conjugate is a convex function, being the supremum of affine functions of $p$, even when $E$ itself is not convex.

Let $G=E\square F$. To prove convexity, take $u_1,u_2$ with finite $G$ values, $0<t<1$, and $\epsilon >0$. By the definition of infimum, choose $v_i$ withPut $u_t=t{u}_1+(1-t)u_2$ and $v_t=t{v}_1+(1-t)v_2$. Convexity of $E$ and $F$ givesLet $\epsilon \downarrow 0$. If either endpoint value is infinite, the convexity inequality is automatic, and $t=0,1$ gives equality. Thus the infimal convolution of two convex functions is convex under the stated properness assumption. The proof uses approximate minimizing splits, so no attainment of the inner infimum is assumed.

For $p\in {\mathcal{U}}^{\ast }$, the definition of the convex conjugate giveswhere the substitution $w=u-v$ is a bijection of the independent pairs. ThereforeThis infimal convolution identity does not need convexity of $E,F$ or attainment of the inner infimum. The assumptions ensure that both functions have nonempty effective domains; their conjugates never take $-\infty$, so the separated sum is well defined, allowing $+\infty$.

Write ${\iota }_C$ for the indicator functional of a constraint set $C$ and $q(u)=\Vert u{\Vert }^2/2$. ThenBoth terms are convex, hence their infimal convolution is the convex squared distance to a convex set. The closest point theorem in a Hilbert space supplies the unique metric projection onto a closed convex set $P_{C}u$ and gives $d_C(u)=\Vert u-P_{C}u{\Vert }^2/2$.

Identify the Hilbert space with its dual space using the Riesz representation theorem. Completing the square yields $q^{\ast }(p)=\Vert p{\Vert }^2/2$, while ${\iota }_C^{\ast }(p)={\sup }_{v\in C}⟨p,v⟩={\sigma }_C(p)$ is the support function. The conjugate of the squared distance to a convex set is thereforeFor the closed unit ball, the metric projection onto a closed convex set is $P_{C}u=u$ if $\Vert u\Vert \le 1$, and $P_{C}u=u/\Vert u\Vert$ otherwise. ThereforeThe last equality uses the Cauchy-Schwarz inequality to compute the unit ball's support function, attained in the direction of $p$ when $p\ne 0$.