Graph total variation ($s(\theta )={\sum }_{\{i,j\}\in E}|{\theta }_i-{\theta }_j|=\Vert D\theta {\Vert }_1$)

The graph total variation measures absolute variation of a vertex signal across edges. It is independent of the orientation used for the oriented incidence matrix. It vanishes exactly on signals constant on each connected component of a graph. A graph total variation denoising estimator combines this penalty with squared error, favouring signals that are piecewise constant on connected regions.

Graph total variation denoising is a penalized least-squares estimator for noisy vertex signals on a graph. The squared loss is strictly convex, so the fitted signal is unique. Its basic inequality for a penalized least-squares estimator separates a noise inner product from the change in penalty. The incidence pseudoinverse decomposition controls the nonconstant noise through the geometry of the graph.