Motivation
An energy model becomes useful computationally only when we can solve it reliably. Writing its stationary equation is not enough when the penalty is nondifferentiable, and reporting a visually stable iterate does not tell us how far it is from the chosen model's optimum. We need an update that respects the nonsmooth penalty, a justified step size, and a numerical quantity that certifies the remaining optimization error.
For finite graph total variation, the dual variables are especially convenient. Each edge variable lies in a bounded interval. Projection onto those intervals is just clipping, while applying the incidence matrix and its transpose requires local differences and accumulation at vertices. This gives a complete algorithm with an elementary convergence proof. We will prove both convergence of the iterates and a rate for dual objective error, carefully distinguishing those from a rate for every possible primal quantity.
The derivation uses exact finite-dimensional arithmetic. Floating-point errors and approximate linear solves require their own tolerances. The method converges to the minimizer of a specified model; that guarantee does not establish that the model is an accurate account of a particular camera or scene.
Definitions
Definition 6.1.1
(Graph-TV energy and its box-constrained dual)
Let be an oriented incidence matrix and let . For define
For define
The energy has a unique minimizer by coercivity and strict convexity.
The scalar identity yields the saddle expression . Minimizing it over by completing the square gives . Thus every feasible supplies a lower bound on the primal minimum, and maximizing is equivalent to minimizing over the box. This derivation does not yet require exchanging a minimum and maximum.
The gradient is and its Lipschitz constant can be taken as . For a nonzero incidence matrix, choose and iterate
Projection clips each coordinate to . This is a gradient step for , followed by projection; the plus sign in the displayed expression comes from the negative gradient formula. If there are no edges, the primal solution is simply and no iteration is needed.
For an unweighted graph of maximum degree , . Therefore is a safe computable choice. A sharper norm estimate may permit a larger step, but an arbitrary convenient number has no convergence guarantee from the proof below.
An implementation can follow the mathematical operations directly. Initialize one feasible number per edge, usually zero. Recover the current vertex image by subtracting the accumulated edge divergence from the data. Difference this image along each oriented edge, add the scaled difference to the edge variable, and clip. Recover the image again from the updated variables before evaluating its certificate. This last ordering matters: pairing a new dual vector with an old recovered image keeps weak duality valid but does not make the square term in the simplified gap vanish. Store both terms of the general formula unless that pairing has been checked.
Each edge value must be read together with the orientation that defines it. Reversing one edge changes the sign of both its difference and its dual component, so the accumulated contribution at the vertices is unchanged. The transpose is not another smoothing operator chosen by intuition; it is the adjoint fixed by the inner products. Several different edge arrays can accumulate to the same vertex vector, which is exactly why the dual solution need not be unique; it is not evidence of a programming error.
The initial value need not be zero, but it must be feasible; otherwise its dual value need not be a valid lower bound. An edge estimate taken from another program should be projected before its certificate is evaluated. The image must be recovered from all current edge values: updating only some pixels while treating the formula as a full synchronous step is a different method. The proof below covers the fixed-step synchronous projected iteration; asynchronous updates or arbitrary acceleration by extrapolation need their own convergence check.
Choose a requested tolerance in the norm of the image or in energy units. For an image tolerance, stop when the feasible gap is at most half its square. For an energy tolerance, the same gap directly bounds the primal energy above its optimum. The exact method eventually meets every strictly positive tolerance because its gap tends to zero. This statement does not provide a uniform iteration count for the gap from the objective-rate theorem alone. In a numerical implementation, report the achieved gap and feasibility error with the iteration count; a maximum iteration limit should be reported as an unfinished certificate if that tolerance has not been reached.
Theorem/proposition
Theorem 6.1.2
(Convergence and a dual objective rate)
For , , and , the projected iterates converge to a minimizer of over . The primal iterates converge to the unique TV minimizer . For any dual minimizer and ,
The dual minimizer itself need not be unique.
Theorem 6.1.3
(A computable gap and an image-error bound)
For any image and feasible , the nonnegative primal-dual gap is
It bounds . In particular, with the square term vanishes. Along the projected iterates this gap tends to zero, so it supplies a valid stopping certificate.
The norm bound involves optimization error relative to the chosen TV minimizer, not reconstruction error relative to an unknown true image. Also, the dual objective rate does not by itself assert the identical rate for the displayed primal-dual gap. The convergence proof ensures that gap vanishes; a stronger quantitative rate would require an additional argument.
Concept lensGeometric
The minimizer is the data minus a projection
The dual problem minimizes over the box, so it asks for the point of the convex polytope nearest to . Hence and
Projection onto a closed convex set is unique even when many map to the same point of , which is the geometric reason why is unique while the dual minimizer need not be. The projected iteration computes this projection through its box coordinates.
Proof sketch or proof idea
Proof
(Projected-gradient argument for convergence and rates)
Projection of a vector onto a closed convex set satisfies for all . This follows by differentiating squared distance along the feasible segment from the projection toward . Set . Convexity and the quadratic Lipschitz upper bound combine with this projection inequality to give
To check it, use and , then substitute the projection bound for . For a minimizing , the left side is nonnegative and the last coefficient is nonnegative. Distances to every minimizer therefore never increase. Summing over iterations telescopes the squared distances. The objective also decreases, so its last error is no larger than the average of its first errors. This proves the objective rate.
For actual iterate convergence we need another step. Taking in the projection inequality gives . This coefficient is positive, hence the squared step lengths have finite sum and steps tend to zero. The box is compact, so some subsequence converges to . Continuity of gradient and projection makes a fixed point. Its projection inequality is precisely for all feasible , which proves convex optimality. Distances of the entire sequence to this particular minimizer are nonincreasing, and the convergent subsequence makes those distances tend to zero. Thus the entire sequence converges.
At a dual minimizer, and the same variational inequality says maximizes over the box. Coordinatewise, it therefore has the sign of every nonzero difference. Together with , these are exactly the primal TV optimality conditions. This establishes equality of primal and dual values without assuming it in advance. Expanding the quadratic at any minimizer gives
The first term is nonnegative by the minimizing variational inequality, yielding the primal norm rate.
Proof X-ray
Where the step bound, the box and the quadratic structure enter
The argument has three stages, and each rests on a different hypothesis. The three-point inequality combines convexity of , the Lipschitz upper bound and the projection inequality. The condition is used there only to make the coefficient nonnegative, so that distances to every minimizer are nonincreasing and the sum telescopes into the rate.
A decreasing bounded objective converges, but that alone does not make the points converge. The sufficient-decrease inequality obtained with makes the steps square-summable; compactness of the box supplies a cluster point; continuity of gradient and projection makes it a fixed point and hence a minimizer. Monotone distance to that particular minimizer then forces the whole sequence to it. Nothing here requires the dual minimizer to be unique, which matters because is singular whenever the graph contains a cycle.
The primal statements come from the exact quadratic expansion of at a minimizer: the linear term is nonnegative by the variational inequality, and the remainder is exactly . This shows that every dual minimizer recovers the same image, and converts the objective rate into the image rate with a factor of two.
The second theorem needs only algebra and two inequalities.
Proof
(Completing the square in the gap)
Complete the square to verify the gap formula. Each remaining edge term is nonnegative because . Strong convexity of the fidelity gives ; weak duality gives . Combining them proves the error certificate. At the limiting primal-dual optimum the gap is zero, and continuity makes the iterated gaps tend to zero.
The step condition in the first theorem cannot simply be dropped, even though the box keeps every iterate bounded.
Counterexample mode
Doubling the safe step makes the iteration cycle
Claim to test: because projection keeps the iterates in a compact box, any positive step converges. Take , and , so , and use . From we get and , so . Then and , so . The iterates cycle between and , the images alternate between and , and the gaps are and , never zero. The minimizer is with . Before clipping, , and clipping cannot increase the distance to , so every converges in this example. The theorem's condition lies inside that range; does not.
Worked examples
Worked example 6.1.4
(A two-pixel problem solved in one projected step)
Let , , and . Here , so and choose . Starting at , the step gives . Then . Its difference is one with matching positive certificate, so its gap is zero. The primal value is , while the dual is . Exact equality certifies the result without reference to a stopping-iterate count.
Worked example 6.1.5
(A nonzero gap exposes unfinished optimization)
On a three-pixel path, take , , and the two forward differences. The largest eigenvalue of is three. With and zero initialization, , giving . Its differences are , so the gap is . Directly, and . The image error to the unknown optimizer is therefore at most . In fact the optimum is with certificate and energy two; its squared distance from the first iterate is , within the certificate.
Worked example 6.1.6
(An operator norm bound from graph degree)
For any vector , each edge satisfies . Summing yields . On a path the degree bound gives four, although the three-pixel exact squared norm is three. Using the bound is conservative but valid. On a large image grid the same argument avoids computing an expensive largest singular value, provided the actual weights and boundary degrees match the stated unweighted graph.
The solver also extends to a strongly convex blurred-image model with . Put , , and . Minimizing the quadratic saddle expression gives dual value . Minimize the latter quadratic part over the same box; its gradient is still and its Hessian is . The preceding projected-gradient proof applies with its operator norm as . Each iteration now requires an accurate positive-definite linear solve. Removing is legitimate only if remains positive definite; the denoising proof does not justify inverting a singular matrix.
Common mistakes
Common mistake
(Clipping the image, or stepping uphill)
Clipping the image instead of the dual edge variables solves a different problem, and reversing the sign in the update performs ascent on . Both errors still produce plausible-looking iterates. A useful implementation check is the adjoint identity with the exact boundary convention. Gap nonnegativity and a decreasing dual objective are further checks; they do not excuse using inconsistent operators.
Common mistake
(Stopping because a step is small)
One should not stop solely because a single step is small: a tiny chosen step can make slow progress look converged. A feasible gap certificate gives a model-based numerical tolerance. If approximate arithmetic makes the computed gap slightly negative, first investigate consistency and roundoff rather than interpreting it as better-than-optimal performance. The mathematics gives nonnegative gaps in exact arithmetic.
Summary
Finite graph TV admits a box-constrained smooth dual with a clipping-based projected-gradient update. Projection geometry yields a dual objective rate; compactness, vanishing steps, and monotone distances yield full iterate convergence. Optimal dual forces recover the unique primal image. A computable primal-dual gap bounds optimization error and supports a meaningful stopping rule, while a positive-definite quadratic fidelity extends the same method to restoration.
Exercises
Exercise 6.1.7
(Solve the two-pixel example with , starting at zero and using . Give the first dual iterate, the recovered image and the gap.)
Foundation
Solution(3)
- 1
Compute the step and the first iterate
Here and . Since , the first iterate is , already feasible.
- 2
Recover the image
.
- 3
Evaluate the gap
The difference of is zero and , so the gap is zero. The primal value is and the dual value is .
Exercise 6.1.8
(Prove that coordinatewise clipping minimizes squared distance to the box . Why does clipping each coordinate independently work here but not for a Euclidean unit ball?)
CoreProof
Solution(3)
- 1
Separate the coordinates
For the box, and the constraint involves each coordinate alone, so the minimization splits into independent scalar problems.
- 2
Solve the scalar problem
The minimizer of over is itself when and the nearer endpoint otherwise. Putting these together gives clipping.
- 3
Contrast with the ball
∎A ball constraint couples the coordinates through , so independent interval decisions need not lie in the ball. Its projection instead rescales radially when the vector is outside.
Exercise 6.1.9
(A feasible pair has gap . Give the guaranteed Euclidean image-error bound. Does this bound measure distance to the true photographed image?)
Foundation
Solution(2)
- 1
Apply the gap bound
.
- 2
Identify what is measured
The bound measures distance to this model's exact minimizer . Noise, blur mismatch and regularization bias can make that minimizer differ from the true image, and the optimization certificate does not bound those other errors.
Exercise 6.1.10
(For the blurred-image extension with positive definite, prove . State a safe step size using a known positive lower bound on that eigenvalue.)
Core
Solution(2)
- 1
Bound the Rayleigh quotient
For every vector , , because . The matrix is symmetric positive semidefinite, so its norm is the largest value of this quotient.
- 2
Choose the step
If and , then , so any positive is safe. A value of exceeding the true is not a lower bound, and the resulting step has no guarantee.