= Solution
Computing $P_Cg$ is equivalent to minimizing $F(p)=\tfrac12\|g-D^*p\|_2^2$ over $P_\lambda$, since $D^*p$ ranges over precisely $C$. Differentiating with the <adjoint operator> gives $\nabla F(p)=D(D^*p-g)$, whose <Lipschitz constant> is $L=\|DD^*\|=\|D\|^2$. Starting with any $p^0\in P_\lambda$, for example zero, the <projected-gradient dual total variation algorithm> is
$$
\boxed{r^k=p^k+\tau D(g-D^*p^k),\qquad p^{k+1}_{i,j}=\frac{r^k_{i,j}}{\max(1,|r^k_{i,j}|_2/\lambda)},\qquad u^k=g-D^*p^k.}
$$
The block formula is the <Euclidean projection onto a convex set> $P_\lambda$, since it clips each two-dimensional block to a Euclidean ball of radius $\lambda$. Both components must be clipped together for the isotropic <block mixed norm>.
For the unscaled forward differences, $\|D_x^+u\|_2^2\le4\|u\|_2^2$ and likewise in the other direction, so $L\le8$. More exactly, for $N>1$ the one-dimensional path difference has <eigenvalues> $4\sin^2(k\pi/(2N))$, $0\le k<N$, and the square-grid operator sums two such spectra. Thus $L=8\cos^2(\pi/(2N))$. Finite-dimensional <projected gradient descent> for a <convex> objective with an $L$-Lipschitz <gradient> converges from every feasible starting point to a dual minimizer for fixed $0<\tau<2/L$. The theorem assumes a nonempty closed <convex set>, a <convex> <differentiable> objective with globally Lipschitz <gradient>, and a nonempty minimizer set. All hold here: $P_\lambda$ is <compact> and <convex>, and $F$ is a <continuous> <convex> quadratic. Finite-dimensional convergence is of the full <sequence>, rather than only its objective values.
Consequently \b[any fixed step with $0<\tau<1/4$ is safe on this grid]; the more conservative $0<\tau\le1/8$ is also safe. The dual minimizer need not be unique because $D^*$ has a <null space>, but $D^*p^k\to P_Cg$ and $u^k\to u$ uniquely. For $N=1$, the <gradient> penalty vanishes and $u=g$, so no positive-$L$ step restriction is needed.
Back to article page
