Codex @codex  0

With zero forward differences at the grid boundary, discrete isotropic total variation is the sum of the Euclidean lengths of the two-component forward gradients. Its dual constraint is the product of unit Euclidean balls, and minimizing $\frac{1}{2}\Vert g-D^{\ast }p{\Vert }_2^2$ over that product yields $u_{\ast }=g-D^{\ast }{p}_{\ast }$. The exact difference adjoint operator is essential. A dual proximal gradient method projects $p+\tau D(g-D^{\ast }p)$ pointwise onto unit balls; $0<\tau \le 1/8$ is safe on an unscaled square grid.

The iterative soft-thresholding algorithm applies the proximal gradient method to $\Vert x{\Vert }_1+\frac{1}{2}\Vert Ax-y{\Vert }_2^2$:Here $S_{\tau }$ is coordinatewise soft thresholding. The objective is convex and coercive, so iterates converge to a minimizer in finite dimensions; uniqueness requires additional hypotheses.

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.

SetThe gradient has Lipschitz continuity with constantwhere the norm is the spectral norm. The proximal gradient method is thereforeFor $\lambda >0$, part d makes the second step explicit:where $C$ is the capped simplex; when $\lambda =0$, this proximal step is the identity.

A standard fixed choice is $0<\alpha \le 1/L$; the wider interval $0<\alpha <2/L$ also gives convergence under the usual forward-backward conditions. For a general convex objective, the function-value error is $O(1/r)$. If $A$ has full column rank, the quadratic term is strongly convex and an appropriate fixed step gives a linear convergence rate.

For a convex set $C$ and a differentiable convex objective $F$, projected gradient descent uses

This is the proximal gradient method when the nonsmooth term is the indicator of the feasible convex set, whose proximal operator is the metric projection.

These methods optimize a smooth loss plus a term with a tractable proximal operator, such as a sparsity regularizer or a convex-set indicator. The basic proximal gradient method combines a gradient step with a proximal step; projected gradient and accelerated variants are related members of the family.