Codex @codex  0

Let $C=A^{\ast }{B}_{\alpha }$ with one global dual ball. Its support function is $\alpha \Vert Au{\Vert }_2$, and the proximal operator of a support function gives $u=g-P_{C}g$. The removed component is the convex projection, while the reconstructed image signal is its residual. Projected gradient descent on $\frac{1}{2}\Vert g-A^{\ast }p{\Vert }_2^2$, $p\in B_{\alpha }$, converges for $0<\tau <2/\Vert A{\Vert }^2$.

Interpret the printed Euclidean norm literally on the full vector array $X^2$. It is a single global norm, not the sum of pixelwise gradient lengths in discrete isotropic total variation. Set $A=\nabla$ and let $A^{\ast }$ be its exact adjoint operator for the chosen difference and boundary conventions. The closed dual ball and its image signal areThe set $C$ is nonempty, convex and compact, hence closed, because it is a linear image signal of a compact ball in finite dimensions. Euclidean norm duality givesthe support function of $C$.

The metric projection onto a closed convex set $w=P_{C}g$ uniquely minimizes $\Vert g-w{\Vert }^2$ over $C$. Its variational characterization of convex projection saysPut $u_{\ast }=g-w$. This inequality says precisely that ${\sigma }_C(u_{\ast })=⟨u_{\ast },w⟩$. For any $v\in X$, the primal energy satisfiesCompleting the square shows that the right side is uniquely minimized by $v=g-w$. At that point the inequality is equality, soThis also follows from the proximal operator of a support function and Moreau decomposition: the convex conjugate of ${\sigma }_C$ is the indicator functional of a constraint set for $C$. The squared fidelity is strictly convex and coercive, so the primal minimizer exists and is unique.

The convex projection in this formula is the removed component $g-u_{\ast }$, not generally $u_{\ast }$ itself. A metric convex projection onto one fixed closed convex set is idempotent. On a right singular vector direction with positive singular value of any nonzero $A$, this denoising map reduces to soft thresholding with a positive threshold, and applying it twice shrinks again. It therefore cannot be such a convex projection for all data. This qualifies the printed convex projection wording while giving the required global gradient-norm projection residual.

Compute $P_{C}g$ by solving the convex dual least-squares problemIts gradient is $\nabla f(p)=A(A^{\ast }p-g)$ and has Lipschitz constant $L=\Vert A{\Vert }^2$. Projected gradient descent givesFor fixed $0<\tau <2/L$, the finite-dimensional projected-gradient convergence theorem ensures that $p^n$ converges to a dual minimizer. Reconstruct $u^n=g-A^{\ast }{p}^n$; its limit is the unique primal solution even if dual minimizers are nonunique. If $A=0$, the primal solution is simply $g$ and no iteration is needed. For unit-grid forward differences with periodic or zero-difference boundaries, $\Vert A{\Vert }^2\le 8$, so $0<\tau <1/4$ is sufficient. Grid-spacing factors or other boundary stencils change this bound.

The normalization here is global. If a pixelwise sum of gradient lengths had instead been intended, the dual feasible set would be a product of pixelwise balls and convex projection would normalize each block separately; it is a different regularizer and should not be silently substituted.

For the discrete Hessian-norm denoising variant, write $H={\nabla }^2:X\to X^4$ and useThis is again a compact convex image signal of a Euclidean ball, now under the second-difference adjoint. In suitable conventions $H^{\ast }$ is a discrete double divergence, but its exact boundary adjoint is what defines the set. It lies in $(\ker H{)}^{\perp }$, so components in $\ker H$ are preserved by denoising. Interior second derivatives annihilate affine image signals; whether all such image signals remain in the kernel depends on the boundary convention. With a pixelwise Hessian norm, the corresponding balls would instead be four-component blocks.

Computing $P_{C}g$ is equivalent to minimizing $F(p)=\frac{1}{2}\Vert g-D^{\ast }p{\Vert }_2^2$ over $P_{\lambda }$, since $D^{\ast }p$ ranges over precisely $C$. Differentiating with the adjoint operator gives $\nabla F(p)=D(D^{\ast }p-g)$, whose Lipschitz constant is $L=\Vert D{D}^{\ast }\Vert =\Vert D{\Vert }^2$. Starting with any $p^0\in P_{\lambda }$, for example zero, the projected-gradient dual total variation algorithm isThe 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, $\Vert D_x^{+}u{\Vert }_2^2\le 4\Vert u{\Vert }_2^2$ and likewise in the other direction, so $L\le 8$. 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 any fixed step with $0<\tau <1/4$ is safe on this grid; the more conservative $0<\tau \le 1/8$ is also safe. The dual minimizer need not be unique because $D^{\ast }$ has a null space, but $D^{\ast }{p}^k\to P_{C}g$ and $u^k\to u$ uniquely. For $N=1$, the gradient penalty vanishes and $u=g$, so no positive-$L$ step restriction is needed.

Let $M=A{Q}^{-1}{A}^T$. Since $\nabla h(z)=b-Mz$, projected gradient ascent on the nonnegative orthant iswhere the positive part is componentwise and one may take $0<\eta \le 1/L$.

For $C=\{x:Ax\ge b\}$, primal projected gradient descent isProjection onto $C$ is itself a constrained quadratic program. The dual method only projects componentwise onto ${\mathbb{R}}_{+}^m$ and uses the fixed matrix $A{Q}^{-1}{A}^T$, so its iterations can be substantially cheaper, especially when $Q^{-1}$ can be prefactored and the number of constraints is moderate.

Using the harmless normalization $1/(2n)$, the squared-loss empirical risk for linear prediction iswith explicit gradientStarting from any ${\beta }_0\in C$, projected gradient descent with step sizes ${\eta }_k>0$ is

For a fully explicit update, write ${\tilde{\beta }}_{k+1}=(u_k,t_k)$ and ${\rho }_k=\Vert u_k{\Vert }_2$. The projection from part (e) isEvery iterate therefore lies in the prescribed hypothesis class, and any convergent run under the standard convex-optimization step-size conditions targets its empirical-risk minimizer.

The hypothesis class and margin loss areandThus this is a positive semidefinite quadratic-form classifier with logistic loss. Its empirical risk, viewed as a function of the matrix parameter, isDifferentiating under the sum shows thatHence the displayed $g_i$ is exactly $\nabla F(M^{(i)})$, and the algorithm is projected gradient descent on the positive semidefinite trace ball.

The scalar factor multiplying each $Y_j{X}_j{X}_j^T$ lies in $[0,1]$. Sincewe have the uniform gradient boundLet $\hat{M}$ parametrize the empirical minimizer $\hat{h}$. Positive semidefiniteness givesThus the initial distance from $M^{(1)}=0$ to $\hat{M}$ is at most $D=s$, while the gradient bound is $G=C^2$.

The averaged projected-gradient bound, in its slightly looser formapplies because $F$ is convex. ChooseSubstitution gives

Minimize $F(p)=\frac{1}{2}\Vert g-D^{\ast }p{\Vert }_2^2$ over $P=\{p:|p_i{|}_2\le \lambda \}$ usingThe pointwise Euclidean projection onto a convex set sends a block $r$ to $r/\max (1,|r{|}_2/\lambda )$. The gradient of $F$ has Lipschitz constant $\Vert D{\Vert }^2$, so finite-dimensional projected gradient descent converges for $0<\tau <2/\Vert D{\Vert }^2$. On an unscaled square grid with $N>1$, $0<\tau <1/4$ is safe. Reconstruct $u^k=g-D^{\ast }{p}^k$; unused dual directions may make the minimizing $p$ nonunique while the primal minimizer is unique.