Motivation
Quadratic smoothness treats a large difference between adjacent pixels as especially expensive. This discourages noise, but it also discourages the steep transition that represents a genuine edge. Total variation changes the growth of the penalty: doubling a difference doubles its cost instead of quadrupling it. This modification leads to a convex optimization problem whose minimizer may have exactly constant regions separated by jumps.
The word “edge-preserving” needs care. A penalty does not know which observed jumps are meaningful. Total variation can reduce edge contrast, remove small features, and create flat regions where the true image varies gradually. A useful mathematical study should explain both what the energy guarantees and what it can fail to represent. We begin with a finite graph, where existence and uniqueness can be proved without importing infinite-dimensional compactness results.
Variational imaging and PDE imaging are closely connected. An energy supplies an optimality equation, and a gradient flow supplies an evolution intended to reduce that energy. Yet they are different objects: a minimizer is a static solution, while a discrete time scheme is an algorithm with its own stability restrictions. Deriving one does not automatically validate every implementation of the other.
Definitions
Definition 2.1.1
(Graph total variation)
Let the pixels be vertices of a finite undirected graph with vertices and edges. Choose an arbitrary orientation for each edge and let be its incidence matrix. For an edge directed from to , . Define graph total variation by
Reversing an edge changes a sign inside an absolute value and hence does not change this quantity. On a connected graph, exactly for constant vectors. On a grid this sum is commonly called anisotropic discrete TV. An isotropic alternative groups horizontal and vertical differences at each pixel and sums their Euclidean magnitudes. These are different discretizations; the distinction matters when comparing diagonal and axis-aligned edges.
For observed data and , consider
This is a denoising model, so its forward operator is the identity. Deblurring would replace the fidelity by and would require revisiting uniqueness. The unconstrained formulation allows any real intensity. A physical range constraint can be added, but its optimality conditions must then include that constraint.
Definition 2.1.2
(Subgradient)
A subgradient of a convex function at is a vector satisfying for all . For the absolute value, the subgradient is at a positive argument, at a negative argument, and the interval at zero.
The interval at zero is essential: ordinary differentiation cannot describe exact fusion of adjacent pixels.
Theorem/proposition
Theorem 2.1.3
(Unique TV denoising and an optimality certificate)
For every and , has a unique minimizer . A vector is that minimizer if and only if there is such that
In particular , with fixed to the sign whenever the corresponding difference is nonzero.
Theorem 2.1.4
(Stability and conservation of the mean)
Let and be the unique TV-denoised images for data and , with the same graph and parameter. Then
Also . If the graph has several connected components, this equality holds separately on every component.
Mean conservation is a property of this unconstrained identity-fidelity model. It should not be assumed for arbitrary blur operators, boundary treatments, penalties involving intensity itself, or constrained reconstruction rules. Stating the model precisely prevents an attractive property from being attributed to a much broader class of methods.
Proof sketch or proof idea
Proof
(Coercivity, strict convexity and the subgradient certificate)
The fidelity tends to infinity when tends to infinity, and TV is continuous and nonnegative. Thus the energy attains a minimum on a sufficiently large closed ball. Its quadratic term is strictly convex and its TV term is convex; their sum is strictly convex, giving uniqueness. The scalar subgradient formula and the chain rule for a finite sum of absolute linear forms yield the certificate. One can also verify sufficiency directly: insert the subgradient inequalities into and use the displayed stationarity equation. The remaining term is .
The second theorem uses the certificate of the first, once for each data set.
Proof
(Monotone subgradients and the kernel of )
For stability choose and with and . Adding the two subgradient inequalities gives . Subtract stationarity equations and take their inner product with :
If the left difference vanishes the claim is immediate; otherwise divide by its norm. To prove conservation, multiply the certificate by the all-ones row vector. Since , the penalty contributes zero. Component indicator vectors give the stronger componentwise statement.
Proof X-ray
The different sources of control
Each conclusion rests on a different property, and none of them uses differentiability of TV. Existence uses only coercivity: the fidelity grows without bound while TV is nonnegative, so the minimum is attained on a closed ball. Uniqueness uses strict convexity, which comes entirely from the identity fidelity, since the TV term is merely convex. That is the hypothesis that fails for a noninjective forward operator, as the counterexample under Common mistakes shows. The certificate describes the minimizer through the scalar subgradient of , and the interval at zero is what lets a fused edge carry a force.
Stability needs a third ingredient, monotonicity of the subdifferential, , obtained by adding two subgradient inequalities. Combined with the two stationarity equations it becomes , and the Cauchy–Schwarz inequality closes the argument. Conservation uses neither convexity nor monotonicity, only the algebraic fact for each component indicator. Replacing TV by a smooth approximation may simplify a numerical method, but smoothness plays no part in any of these steps.
The certificate also produces a finite-dimensional dual problem. Use and complete the square in . The resulting dual maximizes on the box . The primal image is at a dual optimum. A proposed is only a certificate after its sign conditions are checked; being inside the box alone is insufficient.
Concept lensGeometric
TV as bounded edge forces
Each dual variable is a force along a graph edge with magnitude at most one. Its divergence redistributes intensity between neighboring pixels. Where a difference is nonzero, the force saturates with its sign; where pixels fuse, an unsaturated force may balance the data. Summing divergences gives zero, explaining conservation without treating it as a numerical coincidence.
Worked examples
Worked example 2.1.5
(Two pixels: contrast reduction and exact fusion)
Take a single edge from the first pixel to the second and data . If the solution remains increasing, its certificate has and . Thus , valid for . When , set and . The difference is zero, so any is permitted; this choice satisfies stationarity. At the restored image is . It preserves the mean but reduces the true observed jump, illustrating why preserving an edge does not mean preserving its contrast exactly.
Worked example 2.1.6
(A constant image and a brightness shift)
If , the choice and gives zero fidelity and zero TV, so it is the unique minimizer. More generally, if minimizes the energy for , then minimizes it for : substitute into the energy and use . This shift equivariance explains why TV measures differences rather than brightness. It also shows that replacing the TV term by would encode a different prior, because that penalty discourages a large constant background.
Worked example 2.1.7
(Explicit diffusion can amplify a difference)
For quadratic smoothing on the two-pixel graph, the graph Laplacian is . A forward Euler step for is . The mean stays fixed and the difference is multiplied by . With and , the next state is . With , the difference changes sign and doubles in magnitude. The continuous heat equation is dissipative, but this time discretization is unstable for that step size.
For a general graph, is symmetric positive semidefinite because . Orthogonal eigenvectors reduce the explicit step to scalar factors . Euclidean nonexpansion holds when if . A sufficient condition for every updated pixel to be a convex combination of its old value and its neighbors is for an unweighted graph. This positivity condition and the spectral stability condition answer different questions.
To connect TV with PDEs, introduce the smooth approximation
For a sufficiently smooth stationary image, smooth variations, and a boundary condition that cancels the integration-by-parts boundary term, the Euler equation is
Its negative-gradient flow has right-hand side . Along a smooth flow satisfying those boundary conditions, differentiating the energy gives minus the squared norm of the gradient. This formal smooth calculation explains the sign. It is not an existence theorem for nonsmooth continuum TV flow, whose proper formulation requires additional analysis.
History of an idea
A constrained origin
Rudin, Osher, and Fatemi's 1992 paper minimized image total variation under noise-statistics constraints and used a projected evolution. The finite graph penalty model developed here is related, but its unconstrained formulation and finite-dimensional proofs should be distinguished from that original setting.
Common mistakes
Common mistake
(Setting the derivative of the absolute value to zero)
At a zero difference there is no ordinary derivative. Replacing its subgradient interval by the number zero would miss valid fused solutions. In the two-pixel example, fused data require the nonzero value to balance the fidelity even though the restored difference is zero. The subgradient describes that balance exactly.
Common mistake
(Pairing a difference operator with an incompatible divergence)
The isotropic and anisotropic grid penalties should not share an undocumented formula. Likewise, a forward-difference operator and its adjoint must use compatible boundary conventions. Choosing a divergence by visual analogy can reverse a sign or introduce a boundary source. A practical check is the discrete identity for arbitrary test arrays.
Common mistake
(Treating TV as free of artifacts)
TV is not a universal guarantee against artifacts. Since it favors sparse differences, it can flatten a ramp into a staircase. Small objects may disappear when their fidelity benefit does not compensate for their boundary penalty. Nonexpansion concerns the distance between outputs for two data sets; it does not assert that the output is closer than the raw data to every possible unknown image. Such a claim would need a statistical model or a specified class of signals.
The parameter must also be reinterpreted when intensity units change. Rescaling the data by multiplies the quadratic fidelity by but TV only by , so the same numerical does not represent the same trade-off.
For deblurring with a noninjective , strict convexity of the fidelity is lost. The TV penalty is convex but generally not strictly convex. The denoising uniqueness theorem therefore cannot simply be copied into a deblurring report. One must analyze the particular operator and feasible set. Even an algorithm that converges reliably may converge to one member of a nonunique solution set.
Counterexample mode
Uniqueness fails when the forward operator loses a pixel
Claim to test: the uniqueness theorem holds for any fidelity . Take the path , so , and let observe only the end pixels, , with and . By the triangle inequality,
with equality exactly when lies between and . The right side is the two-pixel problem with data , uniquely minimized at with value . Hence every with is a minimizer. The unobserved middle pixel is a direction in along which TV is constant, so the energy is not strictly convex. An injective restores strict convexity, and with it uniqueness.
Summary
Finite graph TV denoising has a unique minimizer, an explicit subgradient certificate, nonexpansive dependence on data, and mean conservation. The certificate provides a dual viewpoint and explains exact fusion. Quadratic diffusion and smoothed TV flows arise from energy descent, but discretized flows need their own stability and boundary checks. These guarantees describe the chosen energy; they do not identify every restored edge with a true physical feature.
Exercises
Exercise 2.1.8
(Solve the single-edge TV problem for data with . Give the formula for both the separated and fused regimes, including the threshold parameter.)
Foundation
Solution(3)
- 1
Treat the separated regime
Let . If , take ; the certificate gives , whose difference is positive, so the sign condition holds.
- 2
Treat the fused regime
If , take and . Then , and any in is allowed on the flat edge.
- 3
Check the threshold
At both formulas give , and uniqueness rules out any other solution. The threshold parameter is .
Exercise 2.1.9
(On any finite graph, prove that adding a constant to the data adds the same constant to the denoised image. Explain why disconnected graphs allow a separate constant on each connected component.)
FoundationProof
Solution(3)
- 1
Compare the two energies
Write . The fidelity of for data equals the fidelity of for , and because .
- 2
Transfer the minimizer
The map is a bijection of candidate images that preserves energy values, so it maps the minimizer to the minimizer.
- 3
Extend to components
∎A vector that is constant separately on each connected component also lies in , and the same substitution proves the componentwise statement.
Exercise 2.1.10
(Let , and . Test whether , satisfy both the primal certificate and the dual box constraint. Compute primal and dual objective values.)
Foundation
Solution(3)
- 1
Check the certificate
Here , so . The restored difference is zero, so is an admissible subgradient.
- 2
Evaluate both objectives
The primal value is . The dual value is .
- 3
Conclude
The two values agree, which confirms optimality: there is no duality gap for this pair.
Exercise 2.1.11
(For a graph Laplacian eigenvector with positive eigenvalue , determine all nonnegative Euler step sizes for which its amplitude does not increase. What happens at the two endpoints? Distinguish this answer from strict decay.)
Core
Solution(3)
- 1
Reduce to the amplitude factor
One step multiplies the mode by , so the condition is , equivalent to .
- 2
Examine the endpoints
At the mode does not change. At its sign reverses with unchanged amplitude. Strict decay occurs exactly for .
- 3
Note the role of positivity
A zero eigenvalue corresponds to a componentwise constant mode, which is unchanged for every step size, so the assumption matters.