Why make diffusion depend on contrast?
Linear heat flow sends intensity along each edge at a rate proportional to the difference between its endpoints. Thus a large jump produces a proportionally large flux, even when the jump is a meaningful boundary. To reduce that tendency, one may use a flux that grows more slowly than the contrast. This is a modeling choice: it does not tell us whether a given jump represents an object or noise. A thin feature can still disappear.
We make the choice precise on a finite graph, where the boundary convention is simply the list of edges. No edge crosses the image boundary unless it is explicitly included. This gives a no-flux model; it does not prove a continuum PDE result. The construction below smooths an anisotropic graph total variation, meaning a sum of absolute differences along individual edges. It is not the grouped Euclidean-norm isotropic pixel TV.
A regularized graph energy
Definition 2.2.1
(Smoothed graph TV energy and its gradient flow)
Let be a finite simple undirected graph with vertices. Choose an arbitrary orientation of each edge and write for the incidence matrix: for an edge oriented from to , . Let positive weights encode the relative strength of the chosen edges. For , set
The subtraction makes a constant image have energy zero; it does not affect the equations. The negative Euclidean gradient flow is
Reversing an orientation changes both the row of and the sign of its odd flux, leaving the equation unchanged. At vertex the same equation reads
For small contrasts the conductance approaches ; for large contrasts it is smaller. The flux magnitude approaches rather than increasing without bound. If the graph has multiple connected components, all statements about means and eventual constants below apply separately to each component.
Existence, conservation and stability
Theorem 2.2.2
(A global finite-dimensional flow)
For every initial image , the equation has a unique solution for every . Each connected component conserves its sum; its minimum cannot decrease and its maximum cannot increase. Moreover,
Two solutions with possibly different initial data satisfy . On each connected component the solution tends to its initial mean. These conclusions require the displayed positive and weights, and concern this finite graph.
Proof
(Lipschitz field, edge cancellation and a spectral gap)
The derivative lies in . Its Jacobian is positive semidefinite and bounded above in quadratic form by . Hence the vector field is globally Lipschitz, with constant at most . The standard finite-dimensional ODE theorem gives a unique global solution. For a component indicator , , so its sum is constant. The energy identity follows from the chain rule and .
To prove the maximum principle, observe that on each component every vertex attaining its current maximum has a nonpositive derivative, since each neighbor has no greater value. For a finite set of differentiable coordinates, the upper right Dini derivative of their maximum is the largest derivative among maximizers; it is therefore nonpositive. A continuous function with nonpositive upper right Dini derivative everywhere is nonincreasing. Apply the same argument to for the minimum.
Since is increasing, for and ,
Thus the flow is nonexpansive, not necessarily strictly contractive: two distinct constant images stay distinct. To prove convergence on a connected component, restrict to the component , let be its conserved mean and set . On , its initial range bounds every edge difference for all time. Writing for the weighted Laplacian restricted to the component, we have
The kernel of consists of the constant vectors on : the identity with positive weights forces a kernel vector to agree across every edge, and connectivity then makes it constant. For a component with at least two vertices, the second-smallest eigenvalue of is therefore positive. Since , we obtain . Grönwall's inequality gives . An isolated vertex is already constant. This proves convergence. The estimate is a bound, not an exact contrast-decay formula.
Proof X-ray
Which property of the field gives which conclusion
The theorem bundles five conclusions, and the proof draws them from four separate facts about the vector field. Global existence uses only the bound : it makes the field globally Lipschitz, so no solution can blow up in finite time. This is the first place where is indispensable. Conservation uses only the algebraic identity , which holds for any vector of edge fluxes. The maximum principle uses the sign of the conductance , while nonexpansiveness uses the monotonicity of . The counterexample below keeps a positive conductance but loses monotonicity, and the contraction estimate goes with it. Energy dissipation, by contrast, implies none of these four properties.
The convergence argument is the one non-routine step. It needs a lower bound on the conductance, which degenerates as the contrast grows. The maximum principle supplies that bound: the range never exceeds its initial value , so every conductance stays at least . Comparison with the linear Laplacian then works, connectivity makes its kernel exactly the constants, and the positive gap forces the deviation from the conserved mean to decay. The order matters: without the maximum principle proved first, the rate constant would not be uniform in time.
A safe explicit step
Let , , and . For a graph with at least one edge, forward Euler is
Two different properties of this scheme are guaranteed by two different step bounds.
Proposition 2.2.3
(Two sufficient step conditions)
Let the graph have at least one edge, and let .
- If , then every is a convex combination of and the values at the neighbors of . Hence the range of each component cannot expand, and every component sum is conserved.
- If , then for every state .
Proof
(A convex combination, and a descent inequality)
Write , so that and
The neighbor coefficients are nonnegative and sum to at most , so the first coefficient is nonnegative as well. This is the convex-combination claim. Summing the update over a component gives zero total change, because each edge flux enters once with each sign.
For the energy, the Hessian is , and its operator norm is at most because . Integrating the gradient along a line gives the descent inequality . Taking shows
and the bracket is nonnegative when .
Both bounds are sufficient and need not be sharp for a particular image. Equality in the energy bound does not by itself prove convergence of the iterates, and range preservation and energy decrease are distinct properties that should be checked separately. An edgeless graph has zero vector field and needs no step restriction.
Common mistake
(Reusing the heat-equation step size)
For linear heat flow with weights , the explicit step keeps every update a convex combination. Here the conductance can be as large as , so the safe bound is , which shrinks with . On one unit edge with , and , the flux is , so . The range has grown from to about . The step must be scaled with .
Worked examples
Worked example 2.2.4
(A two-pixel step)
Take a single unit-weight edge, , and . Its contrast is and the initial rate is . With , one Euler step gives . Its sum remains and both entries remain between and . The updated contrast is , not zero: a single step does not perfectly preserve or remove the edge.
For the continuous flow, writing gives . At , its instantaneous rate is . The quadratic heat model would instead give with unit coefficient. This compares the rates at this particular scaling; changing also changes the small-contrast rate.
Common mistake
(Bounded flux does not mean edges are kept)
The flux across an edge never exceeds in magnitude, so a large jump is smoothed more slowly than under heat flow. It is still smoothed. By the theorem every connected component converges to its mean, and in the example above whenever . On a finite graph this flow delays the loss of an edge; it does not prevent it. Any edge-preserving use of the flow therefore depends on stopping it at a finite time.
Worked example 2.2.5
(A weighted three-pixel row)
For edges of weight and of weight , take and . The flux across the first edge is zero and that across the second is . Hence and the sum of the rates is zero. The weighted maximum degree is , so is sufficient for a range-preserving explicit step for every state.
Where intuition can fail
Counterexample mode
A decreasing conductance need not give a nonexpansive flow
Consider instead the flux on one unit-weight edge. Its conductance decreases with contrast, but is negative for . Starting with two zero-mean images whose positive contrasts are and , their contrasts initially obey and . Thus : the Euclidean distance between these two solutions initially increases. The monotonicity used in the contraction proof has failed. This calculation does not claim that every trajectory of this alternative model grows unbounded.
A very large Euler step can also undo smoothing, as the next computation shows.
Worked example 2.2.6
(A step beyond both bounds)
Take one unit-weight edge, , and . Here has eigenvalues and , so and the energy bound requires ; the range bound is also . The contrast obeys , so
Its magnitude exceeds , so the energy increases even though the continuous flow dissipates it. The new values also leave the initial range . Both conclusions of the proposition fail here, and the step violates both of its hypotheses.
Neither this finite example nor the smooth energy proves existence, uniqueness, or convergence for singular continuum TV flow as .
Exercises
Exercise 2.2.7
(On a two-pixel unit edge with and initial values , find the instantaneous derivatives and show that the mean is constant. What is the limiting image?)
Foundation
Solution(3)
- 1
Compute the derivatives
The difference is and , so .
- 2
Check the mean
At every time the two derivatives are , so their sum is zero by edge cancellation. The mean stays at its initial value .
- 3
Identify the limit
The graph is connected, so by the theorem the solution tends to the constant image with the conserved mean, namely .
Exercise 2.2.8
(For a graph with two disconnected edges and , starting at , find the limiting image and explain why the global mean alone is insufficient.)
Foundation
Solution(2)
- 1
Treat the components separately
No edge joins to , so no intensity is exchanged between them. Their conserved means are and .
- 2
State the limit
Each component tends to its own mean, so the limit is . The global mean is conserved as well, but it does not determine the two separate sums and .
Exercise 2.2.9
(For the weighted three-pixel row above, calculate one Euler step with from and check its range and sum.)
Foundation
Solution(3)
- 1
Check the step bound
The weighted maximum degree is and , so satisfies the range condition of the proposition.
- 2
Take the step
The derivative from the worked example is , so the new image is .
- 3
Check range and sum
All three entries lie in and their sum is , as the proposition predicts.
Exercise 2.2.10
(Show that the Hessian bound used above follows from the quadratic-form inequality , and prove that inequality. Explain why cannot be substituted into this proof.)
CoreProof
Solution(3)
- 1
Prove the quadratic-form inequality
Since and for every edge, each term is at most . Summing gives .
- 2
Pass to the operator norm
The Hessian is symmetric positive semidefinite, so its operator norm is its largest eigenvalue, the maximum of the quotient over unit vectors. That maximum is at most .
- 3
Explain the role of
∎At the bound is undefined, and is not differentiable at zero, so no Hessian exists there. A nonsmooth argument is needed instead.