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

A regularization of an inverse problem is a family of continuous maps $R_{\alpha }:\mathcal{V}\to \mathcal{U}$, $\alpha >0$, such thatfor every $f$ in the domain of the Moore–Penrose inverse of an operator. A linear regularization has each $R_{\alpha }$ bounded and linear. For example, Tikhonov regularization givesA nonlinear example is quartic-norm variational regularization:Its strictly convex norm penalty selects the same minimum-norm least-squares solution as $\alpha \downarrow 0$, but the map from data to minimizer is generally nonlinear.

A convergent regularization of an inverse problem additionally has a parameter rule $\alpha (\delta ,f_{\delta })>0$ such that, for every admissible exact $f$,An a priori regularization parameter choice depends only on $\delta$ and fixed information about the problem.

Let $u^{†}=A^{†}f$. Linearity and the triangle inequality give the noise-bias decomposition for linear regularizationThe first term tends to zero by the assumed noise-amplification bound. The second tends to zero because $\alpha (\delta )\to 0$ and $R_{\alpha }$ is a regularization of an inverse problem. The right side is independent of the particular noisy datum within its allowed ball. Its convergence therefore proves the uniform noisy-data convergence required of a convergent regularization of an inverse problem.

Use the singular system of a compact operator convention $A{x}_j={\sigma }_j{y}_j$ and $A^{\ast }{y}_j={\sigma }_j{x}_j$. Starting from zero gives no component in $\ker A$. Write $x(t)={\sum }_j{c}_j(t)x_j$. The coefficient equations areSolving these scalar linear ordinary differential equations givesConsequently asymptotic regularization has the spectral regularization method representationThe component of $f$ orthogonal to the closure of the range of $A$ is annihilated by $A^{\ast }$ and contributes nothing. The scalar filter satisfies $(1-e^{-{\sigma }^2/\alpha })/\sigma \le \min (\sigma /\alpha ,1/\sigma )\le {\alpha }^{-1/2}$, so every fixed-$\alpha$ reconstruction is a bounded linear operator. Its long-time limit is the Moore–Penrose inverse of an operator on admissible data.

For a Banach space $X$, weak convergence $u_k\rightharpoonup u$ meansFor its continuous dual space $X^{\ast }$, convergence in the weak-star topology meansWeak convergence on $X^{\ast }$ tests against all of $X^{\ast \ast }$, whereas weak-star convergence tests only against the canonical image of $X$. Thus weak convergence always implies weak-star convergence. If $X$ is a reflexive Banach space, that image is all of $X^{\ast \ast }$, so the weak and weak-star topologies on $X^{\ast }$ coincide. Weak-star topology is defined relative to a chosen predual; it is not an extra intrinsic topology on an arbitrary Banach space without such an identification.

The Radon-Riesz property of a norm is the implicationIn a Hilbert space, expand the square using its inner product:Weak convergence gives $⟨u_k,u⟩\to \Vert u{\Vert }^2$, and convergence of norms gives $\Vert u_k{\Vert }^2\to \Vert u{\Vert }^2$. Hence the right side tends to zero. This proves the Hilbert-space Radon-Riesz theorem.

The assumptions prove convergence to the set of J-minimizing solutions, and subsequential convergence to a member of that set. Convergence to a single fixed member requires uniqueness or a suitable selection rule.

Let $u^{†}$ be any J-minimizing solution, whose existence is granted. It is feasible for every noisy-data constraint because $A{u}^{†}=f$ and $\Vert f-f_{\delta }\Vert \le \delta$. Minimality therefore gives $J(u_{\delta })\le J(u^{†})$. All reconstructions lie in this strongly sequentially compact space sublevel set. For any sequence ${\delta }_k\downarrow 0$, pass to a subsequence with $u_{{\delta }_k}\to u_{\ast }$. Boundedness of $A$ and the triangle inequality implyso $A{u}_{\ast }=f$. By sequential lower semicontinuity,Thus $u_{\ast }$ is a J-minimizing solution. The same compactness argument shows the distance to a set of exact minimizers tends to zero: otherwise a subsequence at a fixed positive distance would converge to an exact minimizer, a contradiction. If that minimizer is unique, every convergent subsequence has the same limit, giving the asserted full strong convergence.

For a counterexample to full convergence under the printed hypotheses alone, take $\mathcal{U}=\mathcal{V}=\mathbb{R}$, $A=0$, $f=f_{\delta }=0$, and $J(u)=\max \{|u|-1,0\}$. This is nonnegative and continuous, with compact sublevel sets $[-1-C,1+C]$ for $C\ge 0$. Every point of $[-1,1]$ is both an exact and a residual-method minimizer. Choosing $u_{1/k}=(-1{)}^k$ gives a valid sequence of minimizers that does not converge. The reusable corrected statement is compact-sublevel convergence of the residual method.

For $u\in L^1(\Omega )$, the total variation seminorm on a domain isUsing $C_c^1$ instead gives the same definition. The zero test field shows nonnegativity, and $\mathrm{TV}(0)=0$, so this is a proper extended-real function. Each test field defines a linear functional of $u$; taking their supremum proves convexity, equivalentlyIt is not strictly convex: two distinct constant functions both have zero total variation, as does every convex combination of them.

The function of bounded variation on a domain space isTotal variation is not coercive on $BV(\Omega )$: for $u_k\equiv k$ on a domain of positive measure, $\Vert u_k{\Vert }_{BV}=k|\Omega |\to \infty$, whereas $\mathrm{TV}(u_k)=0$. This is noncoercivity of total variation on constants; a mean-zero constraint can remove the constant obstruction.

An absolutely one-homogeneous functional satisfieswith $J(0)=0$. The printed strictly positive codomain cannot hold at zero; the standard interpretation is a nonnegative, possibly extended-real functional.

For $p\in \partial J(u)$, apply the subgradient inequality at $v=0$:so $⟨p,u⟩\ge J(u)$. Apply it at $v=2u$ and use one-homogeneity:which gives the reverse inequality. ThereforeThis is the Euler identity for a convex one-homogeneous functional; differentiability is unnecessary.

Use the interior-domain definition of total variation seminorm on a domain, so there is no boundary-extension term at $\pm 1$. For any admissible scalar test function $\phi$,Thus $\mathrm{TV}(u_R)\le 2$.

Choose $0<\epsilon <\min \{R,1-R\}$. From the supplied smooth bump function, defineThe two supports are disjoint and inside $(-1,1)$. Each bump has maximum $e^{-1}$, so $\Vert \phi {\Vert }_{\infty }\le 1$, while $\phi (R)=1$ and $\phi (-R)=-1$. This attains the upper bound, provingEquivalently, its distributional derivative is $D{u}_R={\delta }_{-R}-{\delta }_R$, with total variation two. This is total variation of an interval indicator.

For a convex functional $J$ and $p\in \partial J(v)$, the generalized Bregman distance isThe inequality is exactly the subgradient inequality.

Suppose $J$ is strictly convex and $u\ne v$, with both values finite. If the distance vanished, the supporting affine function at $v$ would also meet $J$ at $u$. At $w=(1-t)v+tu$, $0<t<1$, the subgradient inequality would givecontradicting strict convexity. Hence zero distance implies $u=v$.

Without strict convexity, take $J(s)=|s|$, $v=1$, and $p=1\in \partial J(1)$. For every $u\ge 0$,including $u=2\ne 1$. Thus zero Bregman distance need not identify a point. It identifies points on the same supporting face, as explained by zero Bregman distance and supporting faces.

The source condition in variational regularization at an exact solution $u^{†}$ is the existence of a source element ${\mu }^{†}\in {\mathcal{V}}^{\ast }$ such thatFor a Hilbert data space one identifies ${\mathcal{V}}^{\ast }$ with $\mathcal{V}$. If $u$ satisfies $Au=f$ and $A^{\ast }\mu \in \partial J(u)$, then every other exact solution $v$ obeys the subgradient inequalityHence $u$ is a J-minimizing solution. This is source-condition certification of a penalty-minimizing solution.

Let $u^{†}=u_J^{†}$, $p^{†}=A^{\ast }{\mu }^{†}\in \partial J(u^{†})$, and $r_{\alpha }=A{u}_{\alpha }-f$. The subgradient inequality, the dual pairing bound, and $A{u}^{†}=f$ giveMinimality of $u_{\alpha }$ in the exact penalty method givesCombining them yieldsThe coefficient is strictly positive, soNow minimality gives $J(u_{\alpha })\le J(u^{†})$, and exact feasibility plus the defining minimality of $u^{†}$ gives the reverse inequality. Thus $u_{\alpha }$ is a J-minimizing solution. Finally,This exact-penalty threshold from a source condition does not require one-homogeneity; convexity and the source subgradient suffice. If ${\mu }^{†}=0$, the same argument works for every $\alpha >0$, interpreting the upper threshold as infinite.