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

For a convex functional $J:U\to \mathbb{R}\cup \{+\infty \}$ on a real Banach space, its subdifferential at $v$ is empty unless $J(v)$ is finite; otherwiseGiven $p_v\in \partial J(v)$, the Bregman distance isIt can be infinite if $J(u)$ is infinite. If $J$ is differentiable at $v$, the choice is its derivative; otherwise the base subgradient must be specified. Given also $p_u\in \partial J(u)$, add both directional distances to obtain the symmetric Bregman distanceThe symmetric version here is the sum, not half the sum. These nonnegative quantities are not generally metrics and can vanish at distinct points.

Assume the displayed variational minimizer exists and $K:U\to V$ is bounded and linear. The smooth data-fidelity term and the subdifferential sum rule giveUse the supplied source condition in variational regularization $p^{†}=K^{\ast }w\in \partial J(u^{†})$. Put $e=f^{\delta }-f$ and $q=K(u_{\alpha }-u^{†})$, so $\Vert e\Vert \le \delta$. By the symmetric Bregman distance identity,Dropping the last square and using $\Vert e-\alpha w{\Vert }^2\le 2\Vert e{\Vert }^2+2{\alpha }^2\Vert w{\Vert }^2$ proves the source-condition estimate for symmetric Bregman distance:The source condition also makes $u^{†}$ a $J$-minimizing exact solution: for $Ku=f$, its subgradient inequality has zero pairing with $u-u^{†}$. Existence of $u_{\alpha }$ is not implied by properness and lower semicontinuity alone; it is a hypothesis when no coercivity/compactness condition is provided.

Because $w_k\ge c>0$, a finite sum ${\sum }_k{w}_k|u_k|$ implies $u\in {\ell }^1$. Thus the printed weighted one-norm on l2 equals the extended nonnegative sum on every $u\in {\ell }^2$. Unbounded weights may make that sum infinite for some $u\in {\ell }^1$; membership in ${\ell }^1$ alone is not a finiteness assertion.

For each $N$, $J_N(u)={\sum }_{k=1}^N{w}_k|u_k|$ is continuous in the l2 sequence space, and $J={\sup }_N{J}_N$. If $u^{(n)}\to u$ in norm, then for every $N$,Taking the supremum over $N$ provesIt is also weakly lower semicontinuous by the same finite-coordinate argument, and convex and proper because zero and finite sequences have finite penalty.

At a finite-penalty base point $v$, coordinate variations give the subdifferential of a weighted one-norm on l2:These conditions are sufficient by summing the coordinate supporting inequalities. Since $w_k\ge c$, an infinitely supported $v$ would require infinitely many $|p_k|\ge c$, contradicting $p\in {\ell }^2$. Thus a finite-penalty point can have empty subdifferential; a Bregman base with an actual subgradient must be finitely supported.

For any such $p$, $⟨p,v⟩=J(v)$ and the Bregman distance simplifies toEach summand is nonnegative; the sum may be infinite. The pairing converges by Cauchy-Schwarz inequality. This definition does not silently assume a subgradient exists at every $v\in {\ell }^1$.

Use the standard inverse-problem setting of a bounded linear $K:{\ell }^2\to {\ell }^2$ and exact data having a finite-penalty solution. Let $u^{†}$ denote the unique $J$-minimizing exact solution for $J(u)=\Vert u{\Vert }_1+\beta \Vert u{\Vert }_2^2$, $\beta >0$. This is the limiting target of elastic net regularization in Hilbert sequence space; it need not be the Moore–Penrose minimum-norm solution unless additional hypotheses identify them, for example injectivity of $K$.

For each $\alpha >0$, the reconstruction objective is weakly lower semicontinuous, coercive by $\alpha \beta \Vert u{\Vert }_2^2$, and strictly convex. The direct method on the reflexive l2 sequence space gives existence, and strict convexity gives uniqueness. For two data sets, monotonicity of the one-norm subgradients and the quadratic penalty give, with $d=u_1-u_2$ and $g=f_1-f_2$,Completing the square yields $\Vert d\Vert \le \Vert g\Vert /(2\sqrt{2\alpha \beta })$, so each reconstruction map is continuous.

Minimality against $u^{†}$ givesChoose $\alpha \to 0$ and ${\delta }^2/\alpha \to 0$, for example $\alpha =\delta$. This bounds the Hilbert norms, drives the data residual to zero and gives $\mathrm{limsup}J(u_{\alpha }^{\delta })\le J(u^{†})$. Every weakly convergent subsequence has an exact solution as its limit, by boundedness of $K$; weak lower semicontinuity and uniqueness of the penalty minimizer identify that limit with $u^{†}$. Separately applying weak lower semicontinuity to the one-norm givesWeak convergence and convergence of Hilbert norms imply strong convergence by the Radon-Riesz theorem. This proves norm convergence of elastic net regularization:The argument applies to every sequence of noise levels and admissible data, hence gives the usual uniform noise-ball convergence for a fixed admissible exact datum.

For nonlinearity of elastic net reconstruction, zero is the minimizer exactly when $\Vert K^{\ast }{f}^{\delta }{\Vert }_{\infty }\le \alpha$. This includes a neighborhood of zero. If $K\ne 0$, choose $e_j$ with $K{e}_j\ne 0$ and $f^{\delta }=tK{e}_j$ for $t\Vert K{e}_j{\Vert }^2>\alpha$; zero then fails its optimality condition. A linear map vanishing on a neighborhood would vanish everywhere, so the elastic-net reconstruction is nonlinear whenever $K\ne 0$. For $K=I$ the explicit formula is $[R_{\alpha }f{]}_j=\mathrm{sign}(f_j)(|f_j|-\alpha {)}_{+}/(1+2\alpha \beta )$, exhibiting soft thresholding.

A concrete distinction from Moore–Penrose convergence is $K(u)=u_1+2u_2$ (embedded in the first output coordinate of ${\ell }^2$), exact datum one, and $\beta =1$. Its minimum-norm solution is $(1/5,2/5,0,\dots )$, with penalty $4/5$, while the unique penalty-minimizing exact solution is $(0,1/2,0,\dots )$, with penalty $3/4$. For $0<\alpha <2$ the exact-data elastic-net reconstruction is $(0,(2-\alpha )/(4+2\alpha ),0,\dots )$, converging to the latter. Thus it is not a Moore–Penrose-consistent regularization for every noninjective operator under the earlier definition.

The PDF supplies neither a nonzero assumption on $K$ nor a target/domain qualification here. Its unconditional nonlinearity claim is false for $K=0$, whose reconstruction is the zero linear map. The convergence proof above states the finite-penalty exact-solution hypotheses explicitly; it establishes convergence to the penalty-minimizing solution, not an automatically identical minimum-norm least-squares solution.

Use the standard bounded linear operator setting for $K:U\to V$, so the adjoint operator $K^{\ast }:V\to U^{\ast }$ in the updates is defined on every datum. Put $q=K^{\ast }K{u}_{\lambda }$. The generalized singular vector relation is $\lambda q\in \partial J(u_{\lambda })$ with $\Vert K{u}_{\lambda }\Vert =1$ and $\lambda =J(u_{\lambda })\ge 0$. For an absolutely one-homogeneous functional, a subgradient $p$ at $u$ is characterized by $⟨p,u⟩=J(u)$ and $⟨p,v⟩\le J(v)$ for all $v$. Consequently $\lambda q$ is also a subgradient at every positive multiple of $u_{\lambda }$, and $bq\in \partial J(0)$ for every $0\le b\le \lambda$.

Use the initialization $u^0=p^0=0$ and start the first update at $k=0$; the PDF lists $k=1,2,\dots$ despite specifying only index-zero initial data. Suppose $p^k=b_{k}q$ with $0\le b_k\le \lambda$. DefineIf it is positive, $u^{k+1}=c_{k+1}{u}_{\lambda }$ and $p^{k+1}=\lambda q$ satisfy the optimality equation and the dual update. If it is zero, take $u^{k+1}=0$ and $p^{k+1}=(b_k+\gamma /\alpha )q\in \partial J(0)$. Thus this compatible branch hasInduction proves the finite termination of Bregman iteration on a singular vector formulasOnce the dual coefficient reaches $\lambda$, the next reconstruction is $\gamma u_{\lambda }$. Therefore a guaranteed stopping index for this branch isThe formulas also cover $\lambda =0$, where exact reconstruction occurs at the first update. The subgradient conditions are sufficient for global minimization because each objective is convex.

There is a genuine uniqueness issue in the printed claim about arbitrary iterates. Strict convexity of data fidelity in $Ku$ ensures that any two minimizers at a given step have the same image under $K$. Induction therefore makes every minimizer branch have the same dual variables and attain exact data at the stated finite index. It does not make their states equal to the specified $\gamma u_{\lambda }$ if $K$ has a null space.

For a counterexample take $U={\mathbb{R}}^2$, $V=\mathbb{R}$, $K(x,y)=x$, $J(x,y)=|x|$, $u_{\lambda }=(1,0)$, and $\lambda =1$. Every step leaves $y$ completely unconstrained. Choosing the minimizing state's second coordinate to be $k$ gives valid updates and subgradients but never reaches $(\gamma ,0)$ and does not converge as a state sequence. Thus finite exact-data recovery holds for all minimizer branches; exact recovery of the stated vector needs uniqueness or the aligned branch. If $K$ is injective, equal reconstructed data identify the state, and the literal vector conclusion follows.