Why an implicit step?
The smoothed edge diffusion in the preceding note uses a differentiable approximation to . At a zero edge difference, however, the unsmoothed absolute value has no ordinary derivative. Dividing by the difference or assigning a derivative of zero by fiat does not resolve this singularity. A different construction asks for the whole next image at once: balance fidelity to the old image against total variation. We can prove this finite-dimensional step exists and is unique, even when edges become exactly flat.
Definition 2.3.1
(Implicit graph-TV step)
Let be a finite undirected graph with vertices and nonnegative edge weights . Choose an orientation of each edge and let for an edge from to . Define
Here is the old image, the new image, and controls the strength of this step. Reversing an orientation changes neither nor . The sum is anisotropic edgewise graph TV; other discretizations can have different optimality conditions. An empty edge set is allowed and gives .
Existence and the edge-force certificate
Definition 2.3.2
(Subgradient and subdifferential)
For a convex function , a vector belongs to when for every . For a scalar, is if , if , and the entire interval if .
The interval is essential: a flat edge can transmit a force without acquiring a nonzero difference.
Theorem 2.3.3
(The unique step and its certificate)
For every and , the displayed minimization has exactly one solution. A vector is that solution if and only if there are edge forces satisfying
Equivalently, on a nonflat edge, while any is admissible on a flat edge, subject to the vertex equation. The image is unique; the certificate need not be.
Proof
(Existence by coercivity, the certificate by projection)
The objective is continuous and coercive because its quadratic term tends to infinity with and by nonnegative weights. It therefore attains a minimum. The quadratic is strictly convex and is convex, so the minimizer is unique.
To justify the certificate without differentiating , let and . Both are compact and convex, and
Let be the Euclidean projection of onto . Its projection inequality says for all . Put . Then maximizes over . Choose with . Since maximizes , we have . The sum of the bounds is therefore an equality, so every edge bound is an equality, giving the certificate. For any , the support formula yields . Expanding the quadratic and using shows the objective at exceeds that at by at least . Thus is the unique minimizer. Conversely, any certified satisfies the same inequality and must be the minimizer. This also proves .
Proof X-ray
What replaces the missing derivative?
Three ingredients do the work a derivative would normally do. The support representation turns a nonsmooth sum into a maximum of linear functions over a compact convex set; nonnegative weights are needed here, since would be empty if some were negative. The projection inequality onto then plays the role of the stationarity equation: it shows that maximizes , which is exactly the statement that is a subgradient. Finally, edge forces are recovered from the vertex force by a counting argument: the edgewise bounds add up to an equality, so each one is an equality. That is the sign condition on nonflat edges, and it says nothing on flat edges, where the box allows the whole interval.
The quadratic supplies the margin , which gives uniqueness of the image and the converse direction at once. What may fail to be unique is the edge vector with : two choices differ by an element of the kernel of , which is nonzero exactly when the graph has a cycle. On a forest is injective, and the edge force is unique even when edges are flat.
Energy, conservation, and dependence on data
Taking as a competitor gives the basic energy inequality
Thus TV cannot increase, but this statement alone says nothing about individual pixel values. The certificate yields more.
Proposition 2.3.4
(Energy, conservation and stability of the step)
Let be the step from with parameter .
- .
- For every connected component of the subgraph of positive-weight edges, .
- If is the step from on the same graph with the same weights and , then .
Proof
(Three consequences of the certificate)
For the energy estimate, the subgradient inequality for at gives
For conservation, multiply the vertex equation by the indicator : . An entry is nonzero only on an edge with exactly one endpoint in , and such an edge has weight zero, so . Hence . Isolated vertices are components as well.
For stability, take two inputs with outputs , write and . Adding the two subgradient inequalities gives . Hence
so .
The second statement implies no exchange of intensity across a missing or zero-weight edge. The third is nonexpansiveness. It concerns the same , graph and weights; it does not promise strict contraction, since constant inputs remain unchanged.
Two pixels: exact threshold
Worked example 2.3.5
(When an edge becomes flat)
Take one edge of weight with and . The mean is conserved. Write and . The objective becomes . Its unique minimizer is
For , the force is and reduces the contrast by . If , the pixels meet exactly at their mean and the compatible flat-edge force is . At equality the same formula still works. For instance , , , gives ; choosing instead gives with .
On a larger graph, a flat edge is not decoupled from its neighbors.
Worked example 2.3.6
(A flat pair pulled by its neighbor)
Take the path with unit weights, edges oriented and , and . Here , so the vertex equation reads
Try the pattern "first edge flat, second edge increasing". The second condition forces , so and . Flatness gives , hence . The second difference is , consistent with , so the certificate holds and this is the step. The sum is conserved. The energy estimate checks: , and , so .
Common mistake
(Expecting a flat pair to meet at its own mean)
In the path example, the pixels and fuse at , not at the mean of their old values. The pair sum is not conserved, because the nonflat edge to pixel transmits the force into the pair. Conservation holds for connected components of the positive-weight graph, not for an arbitrary cluster of fused pixels.
Counterexample mode
Zero difference does not mean zero force
For , and , the solution above is , yet the vertex equation requires . Setting the force to zero merely because the output difference is zero would give , which is not the minimizer. Nondifferentiability is resolved by a set of possible forces, not by choosing zero universally.
Worked example 2.3.7
(A triangle with an interval of certificates)
Take a triangle with unit weights, edges oriented , , , and a constant image . The step is , since every difference vanishes and the vertex equation becomes . At vertex this reads , at vertex , and at vertex . Hence every circulation with is a certificate. The image is unique, while the certificates form an interval, because the cycle gives a nonzero kernel.
One may repeat the step with and the same positive . Each step exists uniquely, does not increase TV, and preserves every positive-weight component sum. These discrete statements alone do not establish a continuous-time singular TV flow, a regularization limit, or a continuum PDE result.
Exercises
Exercise 2.3.8
(On a single edge of weight , let and . Find the new image and a valid force.)
Foundation
Solution(2)
- 1
Compare the contrast with the threshold
The initial contrast is and , so the new contrast is .
- 2
Recover the image and the force
The mean is , giving . With the orientation from to , the vertex equation gives , which satisfies and the sign condition.
Exercise 2.3.9
(A graph has two connected components and no edge between them: the unit-weight edges and . With and , find the step and explain the component means.)
Foundation
Solution(2)
- 1
Treat each component separately
The components do not interact, and on each. The contrasts and are both at most , so both edges become flat.
- 2
Use conservation on each component
The step is . The component means and (sums and ) are preserved; the global mean alone could not recover both values.
Exercise 2.3.10
(Show that if is constant on every positive-weight component, the step is exactly . Does nonexpansiveness imply strict decrease of the distance between any two different inputs?)
Core
Solution(2)
- 1
Evaluate the objective at
All positive-weight differences vanish, so . The objective is nonnegative and equals zero at , so its unique minimizer is .
- 2
Answer the question on contraction
No. Two distinct constant images are both fixed by the step, so their distance does not decrease.
Exercise 2.3.11
(Prove directly from the certificate that , and explain why this is stronger than the competitor estimate.)
CoreProof
Solution(2)
- 1
Use the subgradient inequality at
Since , we have .
- 2
Compare the coefficients
∎Comparing the objective at and at only gives the coefficient . The certificate doubles it, so the same decrease in allows only half as much squared movement of the image.