Abstract
We consider the problem of estimating a function defined over $n$ locations on a $d$-dimensional grid (having all side lengths equal to $n^{1/d}$). When the function is constrained to have discrete total variation bounded by $C_n$, we derive the minimax optimal (squared) $\ell_2$ estimation error rate, parametrized by $n$ and $C_n$. 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.
Introduction: The Challenge of Higher Dimensions
In signal processing and statistics, recovering a "true" signal from noisy observations often relies on assumptions about the signal's smoothness. A common constraint is "bounded variation," which in 1D is well-handled by non-linear methods like the fused lasso (Total Variation denoising). These methods excel at preserving sharp jumps while smoothing noise—a property known as spatial inhomogeneity.
As we transition to 2D images or 3D volumetric data, the computational cost of non-linear optimization often leads researchers toward simpler linear estimators, such as Laplacian smoothing. This paper investigates whether this computational simplicity comes at a fundamental statistical cost: Do linear estimators achieve the minimax optimal error rates in higher-dimensional Total Variation (TV) classes?
Methodology: Estimators and Canonical Scaling
The study compares two primary classes of estimators:
- Total Variation (TV) Denoising: A non-linear approach solving a convex optimization problem that penalizes the $\ell_1$ norm of differences between neighboring grid points.
- Linear Smoothers: Estimators defined by a linear transformation of the input data ($\hat{\theta} = Sy$), including Laplacian Smoothing and Laplacian Eigenmaps.
A critical component of the analysis is the introduction of canonical scaling for the TV bound ($C_n \asymp \sqrt{n}$ in 2D). This ensures that the complexity of the function class remains physically meaningful as the grid size $n$ increases, allowing for a fair comparison of minimax risks across different dimensions.
Statistical Performance and the "Linear Gap"
The core finding is a persistent "linear gap" in higher dimensions. While linear smoothers are optimal for globally smooth Sobolev spaces (where squared differences are penalized), they are fundamentally suboptimal for TV classes.
As shown in the figure above, under canonical scaling in 2D, the Mean Squared Error (MSE) of linear estimators like Laplacian smoothing fails to converge (remaining at $n^0$), whereas TV denoising achieves the optimal $n^{-1/2}$ rate. This demonstrates that linear methods cannot adapt to the spatially inhomogeneous features—like sharp edges—that define TV classes.
Qualitative Evidence: The Cameraman Benchmark
The theoretical suboptimality of linear methods translates directly to image quality. In the standard "Cameraman" benchmark, TV denoising effectively preserves the sharp boundaries of the figure against the background, whereas linear methods tend to either leave excessive noise or blur critical edges.
Key Insights
- Optimality of TV Denoising: TV denoising is proven to be minimax rate optimal for $d$-dimensional grids, with an error rate scaling as $C_n/n$.
- The Sobolev Exception: Linear estimators are only optimal when the signal is restricted to Sobolev spaces, which lack the sharp transitions found in TV spaces.
- Phase Transition at $d \ge 3$: A unique transition occurs at three dimensions where Sobolev spaces become significantly easier to estimate than TV spaces, unlike the $d=1$ and $d=2$ cases.
Conclusion and Future Directions
This work establishes that for sophisticated denoising tasks in higher dimensions, computationally simpler linear methods cannot be used without sacrificing significant statistical accuracy. Future research will explore the adaptivity of TV denoisers to Sobolev smoothness in $d \ge 3$ and extend these findings to non-grid graph topologies.
Summary updated