Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 326 / 2

A regularization of an inverse problem is a family of continuous maps $R_{\alpha }:V\to U$, $\alpha >0$, such that $R_{\alpha }f\to K^{†}f$ for each $f\in \mathcal{D}(K^{†})$ as $\alpha \downarrow 0$. A linear regularization requires each $R_{\alpha }$ to be a bounded linear operator.

A regularization parameter choice assigns $\alpha =\alpha (\delta ,f^{\delta })>0$ from the noise bound and possibly the measured data. A convergent regularization of an inverse problem satisfies, for every fixed admissible exact datum,In the usual definition the chosen parameter also tends to zero uniformly over this noise ball. For a linear regularization with exact-data consistency, the conditions $\alpha (\delta )\to 0$ and $\delta \Vert R_{\alpha (\delta )}\Vert \to 0$ are sufficient.

For example, Tikhonov regularization with identity penalty has $R_{\alpha }=(K^{\ast }K+\alpha I{)}^{-1}{K}^{\ast }$ and $\Vert R_{\alpha }\Vert \le 1/(2\sqrt{\alpha })$. Its spectral filter converges to the Moore–Penrose inverse of an operator on its domain. Taking $\alpha (\delta )=\delta$ for small positive noise levels gives both required limits.

For a linear regularization, add and subtract the exact-data reconstruction:The triangle inequality gives the noise-bias decomposition for linear regularization:The two summands are noise amplification and approximation bias. Increasing the strength of regularization typically decreases noise amplification and increases bias; reducing regularization has the opposite effect. These are qualitative tendencies and bounds, not a claim that each realized noise error is monotone for every noise vector.

For the one-sided differentiation example, the bounds are $\sqrt{6}\delta /h$ and $\Vert f^{\prime \prime }{\Vert }_{\infty }h/2$. Their sum has an interior balance point when the second-derivative bound is positive and the optimum lies in the permitted interval. The following original sketch plots these bounds against $h$:

For the Volterra operator, the identity $K^{†}f=f^{\prime }$ requires $f(0)=0$ in addition to the printed $C^2$ hypothesis. The constant function $f=1$ is a counterexample to the unrestricted domain assertion: it is not in $\mathcal{D}(K^{†})$. The estimate below is valid for derivatives of every $C^2$ function, and estimates the Moore–Penrose reconstruction when this missing boundary condition holds.

Let $e=f^{\delta }-f$. Apply $|a-b{|}^2\le 2|a{|}^2+2|b{|}^2$ separately to the two halves defining differentiation by one-sided difference quotients:The two translated intervals cover each point at most twice; this proves the factor six. The shifts act on almost-everywhere equivalence classes, so no undefined pointwise data sampling is involved.

For exact data, write the forward difference as $h^{-1}{\int }_0^h{f}^{\prime }(x+t)dt$ and the backward difference as $h^{-1}{\int }_0^h{f}^{\prime }(x-t)dt$. If $M=\Vert f^{\prime \prime }{\Vert }_{\infty }$, either differs from $f^{\prime }(x)$ by at most $h^{-1}{\int }_0^{h}Mtdt=Mh/2$. The interval has length one, so this also bounds the $L^2$ approximation error. The triangle inequality proves the error bound for one-sided differentiation:

For $\delta >0$ and $M=\Vert f^{\prime \prime }{\Vert }_{\infty }>0$, differentiate the bound $F(h)=\sqrt{6}\delta /h+Mh/2$. Its derivative vanishes at $h_{\ast }^2=2\sqrt{6}\delta /M$, and $F^{\prime \prime }(h)>0$. Consequently, when $h_{\ast }<1/2$,If $h_{\ast }\ge 1/2$, the infimum on the open allowed interval is approached as $h\uparrow 1/2$, rather than attained at an admissible endpoint. If $M=0$ and $\delta >0$, the bound decreases throughout the interval and has the same boundary behavior. At zero noise with $M>0$, its infimum is approached as $h\downarrow 0$.

A practical regularization parameter choice independent of $M$ isIt satisfies $h\to 0$ and $\delta /h\to 0$, hence gives a convergent regularization of an inverse problem on the domain of the Volterra operator inverse. This extends beyond $C^2$ exact data: if $f=Ku$ with $u\in L^2$, the differences are local averages of $u$. Extend $u$ by zero outside the interval; continuity of translations in $L^2$ makes these averages converge to $u$ on both halves. Together with $\Vert D_h(f^{\delta }-f){\Vert }_2\le \sqrt{6}\delta /h$ this proves convergence uniformly over the noise ball for every admissible exact datum.

Write $u^{†}=K^{†}f$, $e=R_{\alpha }f-u^{†}$, and $z={\beta }^{-2}{B}^{\ast }B{u}^{†}$, with $\beta >0$ as required by coercivity and by the printed inverse power. The Tikhonov regularization with a coercive penalty operator normal equation givesThis also holds for inconsistent data in $\mathcal{D}(K^{†})$, because $f-K{u}^{†}\perp \mathcal{R}(K)$ and therefore $K^{\ast }f=K^{\ast }K{u}^{†}$. Taking the inner product with $e$ givesFor any $w$ with $\Vert w\Vert \le r$, put $d=\Vert z-K^{\ast }w\Vert$ and use Cauchy-Schwarz inequality to bound the right-hand side by $\alpha {\beta }^2(d\Vert e\Vert +r\Vert Ke\Vert )$. Since $\Vert Be\Vert \ge \beta \Vert e\Vert$, completing the square in $\Vert Ke\Vert$ yieldsThe positive root of this quadratic inequality is at most $d+\sqrt{\alpha }\beta r/2$. Infimizing over $w$ proves the approximate source bound for coercive Tikhonov regularization, in fact slightly more strongly:Injectivity gives $\overline{\mathcal{R}(K^{\ast })}=\mathcal{N}(K{)}^{\perp }=U$. Given any positive tolerance, approximate $z$ by $K^{\ast }w$ for some finite-norm $w$; for all sufficiently large $r$ it is admissible in the infimum. ThusNo attainment of that infimum is needed.

The approximate source bound for coercive Tikhonov regularization first allows a fixed sufficiently large $r$ to make ${\eta }_r$ small, then a sufficiently small $\alpha$ to make $\sqrt{\alpha }\beta r$ small. This order of limits proves $R_{\alpha }f\to K^{†}f$ for every datum in its domain.

For the noise error let $v=R_{\alpha }g$. Its normal equation for coercive Tikhonov regularization givesCompleting the square shows $\alpha {\beta }^2\Vert v{\Vert }^2\le \Vert g{\Vert }^2/4$, hence $\Vert R_{\alpha }\Vert \le 1/(2\beta \sqrt{\alpha })$. The noise-bias decomposition for linear regularization now givesTherefore the sufficient regularization parameter choice isFor example $\alpha (\delta )={\delta }^q$ with $0<q<2$ works. Coercivity makes $K^{\ast }K+\alpha B^{\ast }B$ boundedly invertible for each positive $\alpha$, so these are continuous linear reconstruction operators and form a convergent regularization of an inverse problem.