# Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers

arXiv: https://arxiv.org/abs/1605.08400 · HTML: https://mlsanity.com/paper/1605.08400/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2016.

## Built on by (most cited first, 20 of 20)

- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs](https://mlsanity.com/paper/2106.01529/) (2021)
- [Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms](https://mlsanity.com/paper/2305.19570/) (2023)
- [An Optimal Reduction of TV-Denoising to Adaptive Online Learning](https://mlsanity.com/paper/2101.09438/) (2021)
- [An Equivalence Between Static and Dynamic Regret Minimization](https://mlsanity.com/paper/2406.01577/) (2024)
- [Total Variation Graph Neural Networks](https://mlsanity.com/paper/2211.06218/) (2022)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs](https://mlsanity.com/paper/2111.07394/) (2021)
- [Dynamic Regret Reduces to Kernelized Static Regret](https://mlsanity.com/paper/2507.05478/) (2025)
- [Multivariate Trend Filtering for Lattice Data](https://mlsanity.com/paper/2112.14758/) (2021)
- [Dynamic Ranking and Translation Synchronization](https://mlsanity.com/paper/2207.01455/) (2022)
- [Rates of Convergence for Regression with the Graph Poly-Laplacian](https://mlsanity.com/paper/2209.02305/) (2022)
- [The Voronoigram: Minimax Estimation of Bounded Variation Functions From Scattered Data](https://mlsanity.com/paper/2212.14514/) (2022)
- [Variance estimation in graphs with the fused lasso](https://mlsanity.com/paper/2207.12638/) (2022)
- [Nonsmooth Nonparametric Regression via Fractional Laplacian Eigenmaps](https://mlsanity.com/paper/2402.14985/) (2024)
- [A Cross Validation Framework for Signal Denoising with Applications to Trend Filtering, Dyadic CART and Beyond](https://mlsanity.com/paper/2201.02654/) (2022)
- [Spatially Adaptive Online Prediction of Piecewise Regular Functions](https://mlsanity.com/paper/2203.16587/) (2022)
- [Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution](https://mlsanity.com/paper/2302.03933/) (2023)
- [Joint Learning of Linear Dynamical Systems under Smoothness Constraints](https://mlsanity.com/paper/2406.01094/) (2024)
- [Dynamic angular synchronization under smoothness constraints](https://mlsanity.com/paper/2406.04071/) (2024)
- [Joint estimation of smooth graph signals from partial linear measurements](https://mlsanity.com/paper/2505.23240/) (2025)
- [Multitask Regression with Pairwise Fusion](https://mlsanity.com/paper/2609.27280/) (2026)

## Abstract (arXiv)

We consider the problem of estimating a function defined over n locations on a d-dimensional grid (having all side lengths equal to n1/d). When the function is constrained to have discrete total variation bounded by Cn, we derive the minimax optimal (squared) ℓ2 estimation error rate, parametrized by n and Cn. Total variation denoising, also known as the fused lasso, is seen to be rate optimal. Several simpler estimators exist, such as Laplacian smoothing and Laplacian eigenmaps. A natural question is: can these simpler estimators perform just as well? We prove that these estimators, and more broadly all estimators given by linear transformations of the input data, are suboptimal over the class of functions with bounded variation. This extends fundamental findings of Donoho and Johnstone [1998] on 1-dimensional total variation spaces to higher dimensions. The implication is that the computationally simpler methods cannot be used for such sophisticated denoising tasks, without sacrificing statistical accuracy. We also derive minimax rates for discrete Sobolev spaces over d-dimensional grids, which are, in some sense, smaller than the total variation function spaces. Indeed, these are small enough spaces that linear estimators can be optimal---and a few well-known ones are, such as Laplacian smoothing and Laplacian eigenmaps, as we show. Lastly, we investigate the problem of adaptivity of the total variation denoiser to these smaller Sobolev function spaces.