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

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.