Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 340 / 5

The total variation seminorm on a domain isThe class is symmetric under negation, so no additional absolute value is needed around the integral. The bounded-variation space isEquivalently, the distributional derivative is a finite vector-valued Radon measure, and the displayed quantity is its total mass in variation. For $f\in W^{1,1}(\Omega )$, it equals ${\int }_{\Omega }|\nabla f{|}_{2}dx$. Thus jumps are allowed, with their interface contributions measured by variation.

Assume $g\in L^2(\Omega )$, as required for the finite-valued data fidelity; extend the total variation seminorm on a domain by $+\infty$ outside $BV(\Omega )$. The zero function is a finite-energy competitor. A minimizing sequence $f_n$ has bounded $\Vert f_n-g{\Vert }_2$ and bounded variation, hence bounded $L^2$ norm. Take a weakly convergent subsequence in $L^2$, with limit $f$. For each fixed test vector field $\zeta$, the pairing $\int f\mathrm{div}\zeta$ is weakly continuous because $\mathrm{div}\zeta \in L^2$. Its supremum has weak lower semicontinuity. The squared Hilbert space norm also has weak lower semicontinuity. Thus the direct method in the calculus of variations gives a minimizer in $BV\cap L^2$.

The variation term is convex, and the squared fidelity term is strictly convex. Their sum is strictly convex on its effective domain, so the minimizer is unique.

Let $T(t)=\min (b,\max (a,t))$. The bounded-variation contraction under clipping gives $|D(T\circ f)|(\Omega )\le |Df|(\Omega )$. If $g(x)\in [a,b]$, then $|T(f(x))-g(x)|\le |f(x)-g(x)|$, strictly whenever $f(x)\notin [a,b]$. A positive-measure set outside the interval would therefore strictly decrease the fidelity integral, while not increasing variation, contradicting minimality. HenceNo compactness theorem for the $BV$ embedding is required for this weak-$L^2$ argument.

For a differentiable convex function $F$ with $L$-Lipschitz gradient and a proper lower-semicontinuous convex function $H$, the proximal gradient method isThe proximal operator is ${\mathrm{prox}}_{\tau H}(v)=\arg {\min }_z\{H(z)+\Vert z-v{\Vert }^2/(2\tau )\}$. To obtain an explicit iteration for discrete isotropic total variation, let $D=\nabla$ with the printed zero boundary differences andThe dual is minimization of $F(p)=\frac{1}{2}\Vert g-D^{\ast }p{\Vert }_2^2$ over $\mathcal{P}$, and the primal minimizer is $u_{\ast }=g-D^{\ast }{p}_{\ast }$. Here $D^{\ast }=-\mathrm{div}$ must be the exact adjoint operator of these differences. For example,with the analogous formula in $j$ for $(D_y^{+}{)}^{\ast }$; for $N=1$ both operators are zero. Equivalently use $p_{0j}^1=p_{Nj}^1=p_{i0}^2=p_{iN}^2=0$ in the backward-difference expression, ignoring unused edge components.

The gradient of the dual objective is $D(D^{\ast }p-g)$, with Lipschitz constant $\Vert D{\Vert }^2\le 8$. Taking $H$ to be the indicator functional of a constraint set makes its proximal operator the Euclidean projection onto a convex set. Thus a valid explicit algorithm isThe bound follows by summing $(a-b{)}^2\le 2a^2+2b^2$ over grid differences. Finite-dimensional proximal gradient method convergence gives a dual minimizer and convergence of the recovered $u^k$ to the unique primal minimizer. Projection is pointwise in the dual; applying pointwise soft thresholding directly to $Du$ would not compute the primal TV proximal operator.

Take $F(x)=\frac{1}{2}\Vert Ax-y{\Vert }_2^2$, with $\nabla F(x)=A^T(Ax-y)$ and Lipschitz constant $L=\Vert A{\Vert }_{2\to 2}^2$, and $H(x)=\Vert x{\Vert }_1$. The proximal operator separates over coordinates. Solving the scalar subgradient optimality condition $0\in \partial |z|+(z-v)/\tau$ gives soft thresholding $S_{\tau }(v)=\mathrm{sgn}(v)(|v|-\tau {)}_{+}$. Therefore the iterative soft-thresholding algorithm isHere soft thresholding is applied coordinatewise. The objective is convex and coercive because of its ${\ell }^1$ term, so minimizers exist and the proximal gradient method converges to a minimizer. Uniqueness need not hold if $A$ has a nontrivial null space. If $A=0$, the unique minimizer is zero and any positive step size is admissible.