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

For a bounded linear operator $K:U\to V$ between Hilbert spaces, the Moore–Penrose inverse of an operator assigns to each admissible datum its unique minimum-norm least-squares solution. Its domain isWrite $f=Ku+h$, where $u\in (\ker K{)}^{\perp }$ and $h\in (\mathrm{ran}K{)}^{\perp }=\ker K^{\ast }$. Then $K^{†}f=u$. Restricting to $(\ker K{)}^{\perp }$ removes the ambiguity among solutions differing by an element of the kernel. The orthogonal decomposition also shows that $K{K}^{†}f$ is the orthogonal projection of $f$ onto $\overline{\mathrm{ran}K}$, and $K^{†}Ku$ is the orthogonal projection of $u$ onto $(\ker K{)}^{\perp }$. The inverse is defined on a dense domain and need not be a bounded linear operator when the range is not closed.

The given map is the unilateral shift operator. Its adjoint operator is the left shift operator, sinceThe shift is an isometry with trivial kernel and closed range $\{f:f_1=0\}$. Its range has orthogonal complement $\mathrm{span}\{e_1\}$, so every square-summable datum is admissible. Consequently,Indeed $K^{†}K=I$, while $K{K}^{†}f=f-f_1{e}_1$ is the required orthogonal projection. The discarded first component is the residual of the least-squares solution, not an obstruction to the existence of the Moore–Penrose inverse of an operator.

Choose a singular system of a compact operator with $K{v}_j={\sigma }_j{u}_j$, $K^{\ast }{u}_j={\sigma }_j{v}_j$ and ${\sigma }_j>0$. The Picard criterion, together with range orthogonality, givesFor necessity, expand a solution's component in $(\ker K{)}^{\perp }$ in the orthonormal vectors $v_j$; its coefficients must be $⟨f,u_j⟩/{\sigma }_j$. Their square sum is finite by Bessel's inequality. Conversely, the displayed square sum defines a convergent Hilbert space seriesApplying the bounded linear operator $K$ to the partial sums yields the expansion of $f$ in $\overline{\mathrm{ran}K}=(\ker K^{\ast }{)}^{\perp }$. Thus its limit solves $Ku=f$. The perpendicularity condition is essential here: the Picard criterion alone characterizes the domain of the generalized inverse, which also includes components in $\ker K^{\ast }$.

A linear regularization is a family of bounded linear operators $R_{\alpha }:V\to U$, $\alpha >0$, for which $R_{\alpha }f\to K^{†}f$ for every $f\in \mathcal{D}(K^{†})$ as $\alpha \downarrow 0$. To obtain a convergent regularization of an inverse problem for noisy data, choose a regularization parameter so that the exact-data approximation error and the amplified noise both vanish.

An example is Tikhonov regularization:The positive quadratic term makes $K^{\ast }K+\alpha I$ invertible. The Tikhonov filter norm bound follows from the filter $s/(s^2+\alpha )$, whose maximum for $s\ge 0$ is $1/(2\sqrt{\alpha })$. Therefore $\Vert R_{\alpha }\Vert \le 1/(2\sqrt{\alpha })$. The spectral factors $s^2/(s^2+\alpha )$ tend to one on the positive spectrum; dominated convergence theorem gives consistency on $\mathcal{D}(K^{†})$. The noise-bias decomposition for linear regularization then proves convergence whenever $\alpha (\delta )\to 0$ and $\delta /\sqrt{\alpha (\delta )}\to 0$, for example $\alpha (\delta )=\delta$ for sufficiently small positive noise levels.

The Volterra integration operator is injective and has dense range. Its range of the Volterra integration operator is $\{f\in H^1(0,1):f(0)=0\}$, and its Moore–Penrose inverse of an operator is differentiation on this domain. Thus the error estimate for $K^{†}f$ implicitly requires $f(0)=0$, in addition to the printed $H^2$ assumption. For an arbitrary $H^2$ function the same calculation bounds error against $f^{\prime }$, but that function need not be in $\mathcal{D}(K^{†})$.

Put $a=(1-\alpha )/2$, $b=(1+\alpha )/2$ and $h=\alpha /2$. The three stencils are forward, central finite differences, and backward on $[0,a)$, $[a,b)$ and $[b,1]$, respectively. All shifted evaluation points lie in $[0,1]$. For $g\in L^2(0,1)$, apply $|A-B{|}^2\le 2(|A{|}^2+|B{|}^2)$ and change variables in each of the six evaluation terms. The resulting integration intervals arePair $[0,a]$ with $[a,1-\alpha ]$, $[\alpha ,b]$ with $[b,1]$, and the two middle intervals. Each pair has disjoint interiors, so almost every point is counted at most three times. This overlap multiplicity bound for piecewise difference operators provesFor the bias on the middle interval, write the central finite difference as an average of $f^{\prime }$. The fundamental theorem of calculus giveswhere $\Vert k_{\alpha }{\Vert }_1=\alpha /4$. Extend $f^{\prime \prime }$ by zero to the real line. Young's convolution inequality bounds the middle-interval $L^2$ error by $\alpha c/4$. Combining its squared error with the supplied outer-interval estimate gives the central-difference noise-bias boundThe triangle inequality and the operator norm estimate now giveFor $c>0$, balancing noise and approximation bias minimizes this upper bound atfor sufficiently small $\delta$ that $\alpha <1/2$. Capping the parameter at $1/4$ supplies an admissible rule for all positive noise levels. More generally, $\alpha \to 0$ and $\delta /\alpha \to 0$ suffice; $\alpha =\sqrt{\delta }$ avoids needing $c$ or dividing by $c=0$.

To prove convergence for every admissible datum, not just $H^2$ data, let $f=Ku$ with $u\in L^2(0,1)$ and extend $u$ by zero. Each stencil is a forward, centred or backward average of $u$. Translation continuity in Lp makes each averaged difference from $u$ tend to zero in $L^2(\mathbb{R})$. Restricting those three bounds to their respective intervals proves $R_{\alpha }Ku\to u$. The noise-bias decomposition for linear regularization, with $\delta /\alpha \to 0$, finishes the convergent regularization of an inverse problem.

For a proper convex function $E$ on a real Hilbert space, its subdifferential at $y$ isIn a Banach space, interpret the pairing with an element of the dual space. For a chosen subgradient $p\in \partial E(y)$, the Bregman distance isIf also $q\in \partial E(x)$, its symmetric Bregman distance isThe subgradient inequality proves nonnegativity. These quantities depend on the chosen subgradients and generally are not metrics: they need not distinguish different points or obey the triangle inequality.

For the maximum-entropy regularization functional, differentiation of the scalar integrand gives $(s\log s-s{)}^{\prime }=\log s$. Thus the Fréchet derivative at a positive reference function $y$ is $E^{\prime }(y)=\log y$, and the stated differentiability result gives $\partial E(y)=\{\log y\}$. Consequently,This is the generalized Kullback–Leibler divergence. When both functions integrate to the same mass, the last two terms cancel after integration; for probability density functions it becomes the usual Kullback-Leibler divergence. For two positive functions, adding the reverse distance givesA sufficient setting for the differentiability argument is $L^{\infty }(\Omega )$ with $y$ bounded away from zero. For nonnegative $x$, use $0\log (0/y)=0$ wherever appropriate. Positivity alone in $L^2$ does not automatically provide an open domain on which the Fréchet derivative exists.

For $E(x)=|x|$, the subdifferential at zero is $[-1,1]$. Choose the allowed interior subgradient $p=0$. Its supporting line is horizontal, so the Bregman distance is the vertical gap from $y=0$ to $y=|x|$ at the selected input:More generally, an interior choice $-1<p<1$ gives $D_E^p(1,0)=1-p$. The sketch shows the particular choice $p=0$.

Interpret the normal-operator source condition as the displayed intersection condition: there is $v\in U$ with $w=K^{\ast }Kv\in \partial J(u^{†})$. Fix any $\alpha >0$ and put $\bar{u}=u^{†}+\alpha v$. The subgradient optimality condition for the artificial-data objective isIt holds because its first term equals $-\alpha K^{\ast }Kv=-\alpha w$. By convexity, this is sufficient for global minimality, proving the forward implication. Conversely, if $u^{†}$ minimizes that objective, the same optimality condition givesTaking $v=(\bar{u}-u^{†})/\alpha$ proves the intersection condition. Thus the two conditions are equivalent when the source vector is allowed to be zero.

The printed additional requirement $v\ne 0$ is not equivalent in general. For $K=I$ and $J\equiv 0$, the displayed source condition holds, and choosing $\bar{u}=u^{†}$ makes $u^{†}$ the minimizer, but $\partial J(u^{†})=\{0\}$ forces $v=0$. A nonzero-source version needs an additional hypothesis, such as requiring $w\ne 0$; it cannot be inferred from the printed intersection alone.

Let $w=K^{\ast }Kv\in \partial J(u^{†})$ from the normal-operator source condition, and set $e=u-u^{†}$. Since $u^{†}$ is a least-squares solution, the normal equation for a linear inverse problem gives $K^{\ast }(K{u}^{†}-f)=0$. Expand the objective difference and use the Bregman distance definition:The cross term with the residual of the least-squares solution vanishes by the normal equation; exact data are not required. Compare the minimizing $u_{\alpha }$ with $z=u^{†}-\alpha v$. At $z$, the completed square is zero. Dividing the resulting inequality by $\alpha$ proves the stronger shifted-comparator Bregman boundDropping the nonnegative squared term gives the requested estimate. If the comparator lies outside the effective domain of $J$, its distance is infinite and the inequality is valid but gives no finite error bound.

The relevant nonlinear generalized singular vector relation, without imposing unit-data normalization, isThis is a generalized eigenfunction in the forward-operator metric, rather than a distributional generalized eigenfunction of a linear operator. It supplies the normal-operator source condition with $v=\lambda u^{†}$. For a convex positively one-homogeneous functional, the subgradient inequality applied at zero and at $2u^{†}$ gives $⟨p,u^{†}⟩=J(u^{†})$. If $K{u}^{†}\ne 0$, thenAssume the usual positive eigenvalue $\lambda >0$ and $0<\alpha \lambda \le 1$. By positive homogeneity,The shifted-comparator Bregman bound therefore yieldsThe vector $(1-\alpha \lambda )u^{†}$ is itself a minimizer: $p$ remains a subgradient along the nonnegative ray, and substitution satisfies the subgradient optimality condition. If $K$ is injective, this also proves $u_{\alpha }=(1-\alpha \lambda )u^{†}$. Otherwise distinct minimizers can differ in the kernel while sharing the same predicted data.

For a nonnegative convex positively one-homogeneous functional, the branch continues as $(1-\alpha \lambda {)}_{+}{u}^{†}$ above the threshold, since $p/(\alpha \lambda )\in \partial J(0)$ there. Nonnegativity is needed for that clipping argument; bare positive homogeneity allows signed linear functionals.

Zero Bregman distance does not imply exact recovery. For $K=I$, $J(s)=|s|$, $u^{†}=a>0$ and $0<\alpha <a$, the minimizer is $u_{\alpha }=a-\alpha \ne a$, but $D_J^1(a-\alpha ,a)=0$. Both points touch the same supporting line, as described by zero Bregman distance and supporting faces.

For a proper convex function $E$ that is lower semicontinuous on a Hilbert space, its proximal operator at scale $\gamma >0$ isThe minimizer is unique because the objective is strongly convex; existence follows from the closed proper convex functional and the coercive quadratic, using an affine lower bound. The subgradient optimality condition is $0\in x-z+\gamma \partial E(x)$, which is exactly the displayed resolvent of a monotone operator relation. Setting $\gamma =1$ gives the unscaled proximity or resolvent operator requested here. This is a nonlinear resolvent of the subdifferential, distinct from the spectral resolvent of a linear operator.

Let $s=Kx$ and assume $s>0$. The scalar Poisson data fidelity integrand has derivative $1-y/s$. Applying the permitted interchange of differentiation and integration in a direction $z$ givesThus the ambient-space Fréchet derivative, or its Hilbert space gradient when the pairing is an inner product, isThe quotient is pointwise, and the adjoint operator transports it back from the data domain to the source domain. The chosen spaces must ensure the integrals and derivative pairing are finite; an output bounded away from zero is a useful sufficient condition.

The printed set of probability density functions and positive cone are not vector spaces, so the notation for a bounded linear map between them is understood as a positive bounded linear operator on ambient function spaces, restricted to admissible inputs. If unit mass is a constraint, admissible directions satisfy ${\int }_{\Omega }z=0$. The displayed gradient is then a representative modulo an additive constant; optimization with that constraint additionally includes its normal cone.

Use the scaled proximal operator ${\mathrm{prox}}_{\gamma E}$; take $\gamma =1$ for each unscaled resolvent.

For the quadratic case, write $D^{T}D=\mathrm{diag}(d_1,\dots ,d_n)$ and $\xi =Qx$. Since $Q$ is an orthogonal matrix, the quadratic proximal term becomes $\Vert \xi -Qz{\Vert }^2/2$. The subgradient optimality condition givesAll $d_j\ge 0$, so each diagonal entry is positive, including when $d_j=0$. Multiplying by the inverse diagonal matrix givesThe proximal operator of Poisson data fidelity separates pointwise. At each $t$, the scalar optimality equation on $x>0$ isSince $y>0$, the two roots have opposite signs. Only the positive root is admissible in the logarithm:The negative root is outside the effective domain. The second derivative $1+\gamma y/x^2$ of the proximal objective is positive, establishing the unique pointwise minimizer. The integral formula is understood on the function spaces where these quantities are admissible.

Finally, for $E(x)=|x|$, positive and negative minimizers obey $x-z+\gamma =0$ and $x-z-\gamma =0$, respectively. At zero the subdifferential condition is $z\in [-\gamma ,\gamma ]$. Combining these cases yields soft thresholding:Thus $\gamma =1$ supplies all three requested closed forms.

For the convex conjugate, use a dual scalar $q$ to avoid confusing it with the fixed centre $z$. Differentiating $qx-\lambda (x-z{)}^2/2$ gives $q-\lambda (x-z)=0$, so the unique maximizing point is $x=z+q/\lambda$. Substitution yieldsThe positivity of $\lambda$ makes the maximized quadratic strictly concave and the convex conjugate finite for every real $q$.

Take $F=(F^{\ast }{)}^{\ast }$ with the usual proper closed convex assumptions, so the Fenchel-Moreau theorem identifies its conjugate with the supplied $F^{\ast }$. Put $z^k=u^k-\tau D^T{v}^k$. The first update is $w^{k+1}={\mathrm{prox}}_{F^{\ast }/\tau }(z^k/\tau )$. By Moreau decomposition, the second update isAlso $\tau (D^T{v}^k+w^{k+1})=u^k-u^{k+1}$, so the argument in the final update contains $u^{k+1}-\tau (D^T{v}^k+w^{k+1})=2u^{k+1}-u^k$. Eliminating the auxiliary variable givesThis is the primal-dual hybrid gradient method with extrapolation parameter one and the primal update performed first. Its saddle point function is $F(u)+⟨Du,v⟩-G(v)$, corresponding to the primal objective $F(u)+G^{\ast }(Du)$.

For proper lower semicontinuous convex functions and a nonempty saddle-point set in these finite-dimensional spaces, the standard convergence of primal-dual hybrid gradient theorem gives the sufficient parameter conditionHere $\Vert D{\Vert }_2$ is the operator norm, or largest singular value. For $D\ne 0$, one possible choice is $\tau =\sigma =\eta /\Vert D{\Vert }_2$ with $0<\eta <1$; for $D=0$ any positive steps satisfy the condition. The existence assumption is necessary: step sizes alone cannot guarantee convergence to a saddle point that does not exist.