betaFeedback

WorksMathematics

Pointwise Minmax Representations for Total Variation Denoising on Graphs

Abstract

Total variation denoising (TVD) is a fundamental method in image denoising, signal processing, and nonparametric regression. We establish exact pointwise minmax/maxmin representations for TVD on arbitrary finite graphs, extending recent one-dimensional results. Under squared loss, fitted values are expressed through corrected local averages over nested connected vertex sets. The correction is a signed boundary count: edges leaving the inner set contribute +1 if they remain within the outer set and -1 otherwise. To the best of our knowledge, this representation is new even for two-dimensional TVD. We show that Brunk's classical minmax formulas for isotonic regression on every finite directed acyclic graph arise as special cases of our graph TVD representation. The exact reduction proceeds through asymmetric TVD and nearly isotonic regression, which coincides with isotonic regression above a finite penalty threshold. We further extend the representations to arbitrary finite separable convex losses, assuming coercivity of the full objective, but without requiring differentiability or strict convexity. For nonunique solutions, the possible fitted values at each coordinate form a compact interval. Its lower and upper endpoints admit maxmin and minmax representations, respectively, through scalar local optimization problems and are attained simultaneously at all coordinates by two extremal solutions. This yields exact representations for quantile TVD on arbitrary graphs and unifies TVD, nearly isotonic regression, and isotonic regression within a single pointwise framework for general separable convex losses.

Introduction and Main Results

Total variation denoising (TVD) is a classical nonparametric regression and denoising method that has been extensively studied in statistics, applied mathematics, and signal processing. It was introduced in the seminal work of Rudin et al. [21], which proposed total variation regularization for two-dimensional image denoising. In one dimension, given observations y1,…,yny_1,\ldots,y_n, the TVD estimator, for λ≥0\lambda\ge0, is

θ^(λ)=arg⁡min⁡θ∈Rn{12∑i=1n(yi−θi)2+λ∑i=1n−1∣θi+1−θi∣}(1)\widehat{\theta}^{(\lambda)} = \underset{\theta\in\mathbb{R}^n}{\arg\min}\left\{\frac{1}{2}\sum_{i=1}^{n}(y_i-\theta_i)^2+\lambda\sum_{i=1}^{n-1}|\theta_{i+1}-\theta_i|\right\} \tag*{(1)}

The total variation (TV) penalty promotes sparsity in the first-order differences of the fitted signal, and consequently the estimator θ^(λ)\widehat{\theta}^{(\lambda)} is piecewise constant. This estimator is also known as the fused lasso ([23]) and is closely related to locally adaptive regression splines ([12]).

In the setting of image denoising, the corresponding TV penalty sums absolute differences across horizontally and vertically adjacent pixels. If G=(V,E)G=(V,E) is the 2D2D grid graph, this penalty is

TV⁡G(θ)=∑{u,v}∈E∣θu−θv∣.(2)\operatorname{TV}_G(\theta)=\sum_{\{u,v\}\in E}|\theta_u-\theta_v|. \tag*{(2)}

This is the so-called anisotropic form of the total variation penalty. The definition in (2) extends naturally to any finite undirected graph, yielding graph TVD, also known as the graph fused lasso. This estimator encourages piecewise constant signals on connected regions of the graph; see Tibshirani and Taylor [24] for its formulation within generalized lasso, and [27, 7, 11] for statistical and computational developments.

The nondifferentiable TV penalty couples neighboring coordinates, making the fitted values of θ^(λ)\widehat{\theta}^{(\lambda)} difficult to characterize explicitly. Despite the long history of TVD, an exact pointwise representation was established only recently in the univariate setting by Chatterjee [3]. This representation is explicit and expresses each fitted value as a min–max, or equivalently a max–min, of simple functions of local averages over nested intervals containing the target point. It also provides a direct route to pointwise statistical analysis, which is difficult to carry out using the global optimization formulation alone.

In subsequent work, Ghoshal and Chatterjee [6] established a corresponding representation for quantile TVD, replacing the averages by suitable local order statistics. Quantile loss is neither differentiable nor strictly convex, and the fitted TVD solution need not be unique. Their formulae characterize the endpoints of the interval of possible fitted values at each coordinate.

These two results raise three natural questions, which we answer in this paper.

  1. Does a similar representation hold for two-dimensional TVD? The results of Chatterjee [3] and Ghoshal and Chatterjee [6] only hold for the one-dimensional case.

The main contribution of this article is to show that an exact representation holds on every finite graph, including the 2D2D lattice/grid graph. In one dimension, the representation takes a min–max over nested intervals of local averages with correction terms determined by the position of the inner interval within the outer interval. Our graph representation gives a remarkably clean and natural generalization: intervals become connected vertex sets, and the correction is determined by a count of edges leaving the inner set II, with opposite signs according to whether they remain inside or leave the outer set JJ.

  1. How is this representation related to the classical isotonic minmax formula? The classical min–max formulas for isotonic regression are a cornerstone of shape-restricted inference: they express a globally constrained estimator through local averages and provide a direct route to its pointwise statistical analysis Robertson et al. [19]; Zhang [28]; Chatterjee et al. [4]. We show that these formulas are instances of a more general pointwise representation for graph TVD. In particular, the classical formula over intersections of upper and lower sets on a DAG emerges from our formula over nested connected sets. The bridge is asymmetric TVD, which includes nearly isotonic regression Tibshirani et al. [25], which further agrees exactly with isotonic regression once the penalty exceeds a finite threshold. This places order-constrained estimation and total variation regularization within a common min–max framework.

  1. Does the representation extend to a general convex loss? The quantile result suggests that such minmax representations can hold for TVD with other (possibly nondifferentiable) losses beyond just the squared loss. In this article, we establish a min-max/maxmin representation for arbitrary finite, separable convex losses. This general formula recovers both the squared-loss formula of Chatterjee [3] and the quantile formula of Ghoshal and Chatterjee [6].

Taken together, these results establish a unified pointwise min–max characterization of graph TVD, quantile TVD, nearly-isotonic regression, and isotonic regression. In the next section, we give a precise statement of our pointwise min-max representation for graph TVD.

Squared-loss TVD on a general graph

Let G=(V,E)G=(V,E) be a finite undirected graph with V≠∅V\ne\varnothing. Given y∈RVy\in\mathbb{R}^{V}, define the total variation denoising estimator (for the graph GG) as follows:

θ^(λ)=arg⁡min⁡θ∈RV{12∑u∈V(yu−θu)2+λTV⁡G(θ)}(3)\widehat{\theta}^{(\lambda)}=\underset{\theta\in\mathbb{R}^{V}}{\arg\min}\left\{\frac{1}{2}\sum_{u\in V}(y_u-\theta_u)^2+\lambda\operatorname{TV}_{G}(\theta)\right\} \tag*{(3)}

where

TV⁡G(θ)=∑{u,v}∈E∣θu−θv∣.(4)\operatorname{TV}_{G}(\theta)=\sum_{\{u,v\}\in E}\lvert\theta_u-\theta_v\rvert. \tag*{(4)}

The objective is strictly convex and coercive, so the minimizer exists and is unique. Write C\mathcal{C} for the collection of nonempty vertex sets whose induced subgraphs are connected, and let Ci={J∈C:i∈J}\mathcal{C}_i=\{J\in\mathcal{C}:i\in J\}. For a nonempty set II, write yˉI=∣I∣−1∑u∈Iyu\bar{y}_I=\lvert I\rvert^{-1}\sum_{u\in I}y_u. For disjoint sets A,B⊆VA, B \subseteq V, let ∣E(A,B)∣|E(A,B)| denote the number of edges with one endpoint in AA and the other in BB.

For any pair of nested subsets ∅≠I⊆J⊆V\varnothing\ne I \subseteq J \subseteq V, let us define

CI,J=∣E(I,J∖I)∣−∣E(I,Jc)∣(5)C_{I,J}=|E(I,J\setminus I)|-|E(I,J^{c})| \tag*{(5)}

where Jc=V∖JJ^{c}=V\setminus J. Every edge leaving II contributes either +1+1, if it remains inside JJ, or −1-1, if it leaves JJ as well. Thus CI,JC_{I,J} is a signed count of the boundary of II (number of edges leaving II) with respect to the outer set JJ. We are now ready to state the main result of this paper.

Theorem 1.1 (Pointwise representation for graph TVD). For every finite undirected graph G=(V,E)G=(V,E), every y∈RVy\in\mathbb{R}^{V}, every λ≥0\lambda\ge0, and every i∈Vi\in V,

θ^i(λ)=max⁡J∈Cimin⁡I∈CiI⊆J{yˉI+λCI,J∣I∣}(6)\widehat{\theta}^{(\lambda)}_i=\max_{J\in\mathcal{C}_i}\min_{\substack{I\in\mathcal{C}_i\\ I\subseteq J}}\left\{\bar{y}_I+\frac{\lambda C_{I,J}}{|I|}\right\} \tag*{(6)}
=min⁡J∈Cimax⁡I∈CiI⊆J{yˉI−λCI,J∣I∣}.(7)=\min_{J\in\mathcal{C}_i}\max_{\substack{I\in\mathcal{C}_i\\ I\subseteq J}}\left\{\bar{y}_I-\frac{\lambda C_{I,J}}{|I|}\right\}. \tag*{(7)}

Remark 1. In the above result, the connectedness restrictions on II and JJ can be dropped. Both identities remain valid when II and JJ range over arbitrary vertex sets satisfying i∈I⊆Ji\in I\subseteq J.

How to read the min–max representation

Fix a vertex ii. Choose an outer connected set JJ containing ii, and then an inner connected set II such that i∈I⊆Ji\in I\subseteq J. The pair (I,J)(I,J) gives a corrected local average: the ordinary average yˉI\bar{y}_I, adjusted by λCI,J/∣I∣\lambda C_{I,J}/|I|. In the max–min formula this correction is added; in the min–max formula it is subtracted. The inner optimization compares these corrected averages for a fixed JJ, and the outer optimization then selects among the possible choices of JJ.

Let us consider the toy case when n=2n=2, where the graph has two vertices and one edge, and see what the minmax representation gives us. Write yˉ=(y1+y2)/2\bar{y}=(y_1+y_2)/2. To find the fitted value at vertex 1, there are two choices of outer set. If J={1}J=\{1\}, necessarily I={1}I=\{1\}, and CI,J=−1C_{I,J}=-1. If J={1,2}J=\{1,2\}, the two choices are I={1}I=\{1\}, for which CI,J=1C_{I,J}=1, and I={1,2}I=\{1,2\}, for which CI,J=0C_{I,J}=0. Thus the min–max identity reads

θ^1(λ)=min⁡{y1+λ,max⁡{y1−λ,yˉ}}=proj⁡[y1−λ,y1+λ](yˉ).\begin{aligned} \widehat{\theta}^{(\lambda)}_1=\min\{y_1+\lambda,\max\{y_1-\lambda,\bar{y}\}\} \\ &=\operatorname{proj}_{[y_1-\lambda,y_1+\lambda]}(\bar{y}). \end{aligned}

By symmetry, the corresponding expression for vertex 2 projects yˉ\bar{y} onto [y2−λ,y2+λ][y_2-\lambda,y_2+\lambda]. Writing d=y2−y1d=y_2-y_1 and evaluating these projections gives

(θ^1(λ),θ^2(λ))={(yˉ,yˉ),∣d∣≤2λ,(y1+λ,y2−λ),d>2λ,(y1−λ,y2+λ),d<−2λ.\begin{pmatrix}\widehat{\theta}^{(\lambda)}_1,\widehat{\theta}^{(\lambda)}_2\end{pmatrix} = \begin{cases} (\bar{y},\bar{y}), & |d|\le2\lambda,\\ (y_1+\lambda,y_2-\lambda), & d>2\lambda,\\ (y_1-\lambda,y_2+\lambda), & d<-2\lambda. \end{cases}

Hence observations separated by at most 2λ2\lambda are fused at their average. Otherwise, the two fitted values remain distinct, with each observation shifted toward the other by λ\lambda.

Comparison with the 1D Result

On a one-dimensional chain graph, connected vertex sets are intervals. An interval has at most two boundary edges, and (5) recovers the correction factors in Chatterjee [3]. For example, when JJ avoids the endpoints {1,n}\{1,n\}, CI,J=2C_{I,J}=2 if II lies strictly inside JJ, CI,J=−2C_{I,J}=-2 if I=JI=J, and CI,J=0C_{I,J}=0 if II shares exactly one endpoint with JJ.

In Chatterjee [3], these correction factors were specified case by case, without a unifying formula. Equation (5) reveals their underlying structure: CI,JC_{I,J} is a signed count of the boundary edges of II, with each edge connecting II to J∖IJ\setminus I contributing 11, and each edge connecting II to JcJ^{c} contributing −1-1. This interpretation is purely graph theoretic and makes no reference to the linear ordering of the 1D chain graph. A central contribution of this paper is to identify this graph-theoretic structure and establish that the same signed boundary count yields an exact pointwise min–max representation on every finite graph.

Implications for two-dimensional TVD

On a two-dimensional grid, the representation involves arbitrary connected vertex sets containing the vertex of interest. Unlike connected sets on the 1D chain, these sets need not have a simple geometric form: they can have irregular boundaries and are not restricted to rectangles. Thus the local averages appearing in the formula range over a much richer collection of regions than in one dimension.

The representation does not by itself provide a practical method for computing the estimator. On a two-dimensional grid, the number of admissible pairs I⊆JI\subseteq J can be prohibitively large, making direct enumeration infeasible. Even in one dimension, computation is better handled by specialized algorithms, such as the O(n)O(n) dynamic programming algorithm of Johnson [8] or the fast direct algorithm of Condat [5], without evaluating the min–max formula.

We anticipate that the representation will instead be useful for studying the pointwise statistical properties of two-dimensional TVD. It expresses each fitted value through maxima and minima of explicit local averages with boundary corrections, making the roles of the observations and the geometry of the graph directly visible. In particular, fixing an outer set JJ in the two representations gives upper and lower bounds on the fitted value. Such bounds offer a starting point for analyzing pointwise estimation error in terms of local signal variation, noise averages, and local geometry of the graph.

A preview of the proof

Why does the representation involve an outer set JJ, an inner set I⊆JI\subseteq J, and a min–max over these choices? An instructive starting point is the following elementary identity, valid for every vector v∈RVv\in\mathbb{R}^{V}:

References

  1. [1]Richard E. Barlow, David J. Bartholomew, J. M. Bremner, and Hugh D. Brunk. Statistical Inference under Order Restrictions: The Theory and Application of Isotonic Regression. Wiley, London, 1972.
  2. [2]Hugh D. Brunk. Maximum likelihood estimates of monotone parameters. The Annals of Mathematical Statistics, 26(4):607–616, 1955. doi: 10.1214/aoms/1177728420.DOI
  3. [3]Sabyasachi Chatterjee. Minmax trend filtering: Generalizations of total variation denoising via a local minmax/maxmin formula. The Annals of Statistics, 2026. URL https://arxiv.org/abs/2410.03041. To appear. arXiv:2410.03041.
  4. [4]Sabyasachi Chatterjee, Adityanand Guntuboyina, and Bodhisattva Sen. On risk bounds in isotonic and other shape restricted regression problems. The Annals of Statistics, 43(4):1774–1800, 2015. doi: 10.1214/15-AOS1324.DOI
  5. [5]Laurent Condat. A direct algorithm for 1-D total variation denoising. IEEE Signal Processing Letters, 20(11):1054–1057, 2013. doi: 10.1109/LSP.2013.2278339.DOI
  6. [6]Deep Ghoshal and Sabyasachi Chatterjee. An exact pointwise characterization for total variation denoising in quantile regression. Preprint. arXiv:2605.01237, 2026. URL https://arxiv.org/abs/2605.01237.
  7. [7]Jan-Christian Hütter and Philippe Rigollet. Optimal rates for total variation denoising. In Proceedings of the 29th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 49, pages 1115–1146. PMLR, 2016. URL https://proceedings.mlr.press/v49/huetter16.html.arxiv.org/abs/1603.09388
  8. [8]Nicholas A. Johnson. A dynamic programming algorithm for the fused lasso and L₀-segmentation. Journal of Computational and Graphical Statistics, 22(2):246–260, 2013. doi: 10.1080/10618600.2012.681238.DOI
  9. [9]Alexander I. Jordan, Anja Mühlmann, and Johanna F. Ziegel. Characterizing the optimal solutions to the isotonic regression problem for identifiable functionals. Annals of the Institute of Statistical Mathematics, 74(3):489–514, 2022. doi: 10.1007/s10463-021-00808-0.DOI
  10. [10]Roger Koenker and Gilbert Bassett, Jr. Regression quantiles. Econometrica, 46(1):33–50, 1978. doi: 10.2307/1913643.DOI
  11. [11]Oscar Hernan Madrid Padilla, James Sharpnack, James G. Scott, and Ryan J. Tibshirani. The DFS fused lasso: Linear-time denoising over general graphs. Journal of Machine Learning Research, 18(176):1–36, 2018. URL https://jmlr.org/papers/v18/16-532.html.
  12. [12]Enno Mammen and Sara van de Geer. Locally adaptive regression splines. The Annals of Statistics, 25(1):387–413, 1997. doi: 10.1214/aos/1034276635.DOI
  13. [13]Kentaro Minami. Estimating piecewise monotone signals. Electronic Journal of Statistics, 14(1):1508–1576, 2020. URL https://arxiv.org/abs/1905.01840.
  14. [14]Alexandre Mösching and Lutz Dümbgen. Monotone least squares and isotonic quantiles. Electronic Journal of Statistics, 14(1):24–49, 2020. doi: 10.1214/19-EJS1659.
  15. [15]Vladimir Pastukhov. Fused lasso nearly-isotonic signal approximation in general dimensions. Statistics and Computing, 34:120, 2024. doi: 10.1007/s11222-024-10432-6.DOI
  16. [16]Vladimir Pastukhov. A generalized lasso formulation of weighted and regularized (nearly-)isotonic regression on graphs. Preprint. arXiv:2611.04018, 2026. URL https://arxiv.org/abs/2611.04018.
  17. [17]Nicholas G. Polson and James G. Scott. Mixtures, envelopes and hierarchical duality. Journal of the Royal Statistical Society, Series B, 78(4):701–727, 2016. doi: 10.1111/rssb.12130.DOI
  18. [18]Tim Robertson and F. T. Wright. Algorithms in order restricted statistical inference and the Cauchy mean value property. The Annals of Statistics, 8(3):645–651, 1980. URL https://www.jstor.org/stable/2240598.DOI
  19. [19]Tim Robertson, F. T. Wright, and R. L. Dykstra. Order Restricted Statistical Inference. Wiley, Chichester, 1988.
  20. [20]R. T. Rockafellar. Convex Analysis. Princeton University Press, Princeton, NJ, 1997.
  21. [21]Leonid I. Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D, 60(1–4):259–268, 1992. doi: 10.1016/0167-2789(92)90242-F.DOI
  22. [22]Veerananjaneyulu Sadhanala, Robert Bassett, James Sharpnack, and Daniel J. McDonald. Exponential family trend filtering on lattices. Electronic Journal of Statistics, 18(1):1749–1814, 2024. URL https://arxiv.org/abs/2209.09175.
  23. [23]Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight. Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society, Series B, 67 (1):91–108, 2005. doi: 10.1111/j.1467-9868.2005.00490.x.DOI
  24. [24]Ryan J. Tibshirani and Jonathan Taylor. The solution path of the generalized lasso. The Annals of Statistics, 39(3):1335–1371, 2011. doi: 10.1214/11-AOS878.DOI
  25. [25]Ryan J. Tibshirani, Holger Hoefling, and Robert Tibshirani. Nearly-isotonic regression. Technometrics, 53(1):54–61, 2011. doi: 10.1198/TECH.2010.10111.DOI
  26. [26]Sara van de Geer. Logistic regression with total variation regularization. Transactions of A. Razmadze Mathematical Institute, 174(2):217–233, 2020. URL https://rmi.tsu.ge/transactions/TRMI-volumes/174-2/v174%282%29-10.pdf.arxiv.org/abs/2003.02678
  27. [27]Yu-Xiang Wang, James Sharpnack, Alexander J. Smola, and Ryan J. Tibshirani. Trend filtering on graphs. Journal of Machine Learning Research, 17(105):1–41, 2016. URL https://www.jmlr.org/papers/v17/15-147.html.
  28. [28]Cun-Hui Zhang. Risk bounds in isotonic regression. The Annals of Statistics, 30(2):528–555, 2002. doi: 10.1214/aos/1021379864.DOI

Paper details

vlnc:W_act4tnuf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents