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

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.

References in corpus (2)

• Modular proximal optimization for multidimensional total-variation regularization
• Optimal rates for total variation denoising

Cited by in corpus (18)

• The DFS Fused Lasso: Linear-Time Denoising over General Graphs
• Multiscale spatial density smoothing: an application to large-scale radiological survey and anomaly detection
• Minimax Distribution Estimation in Wasserstein Distance
• Approximate Recovery in Changepoint Problems, from ${\ell }_2$ Estimation Error Rates
• Online Forecasting of Total-Variation-bounded Sequences
• Multivariate extensions of isotonic regression and total variation denoising via entire monotonicity and Hardy-Krause variation
• On the total variation regularized estimator over a class of tree graphs
• Approximate $l_0$-penalized estimation of piecewise-constant signals on graphs
• Graph-based regularization for regression problems with alignment and highly-correlated designs
• Adaptive Non-Parametric Regression With the $K$-NN Fused Lasso
• Frame-constrained Total Variation Regularization for White Noise Regression
• Logistic regression with total variation regularization
• Oracle inequalities for square root analysis estimators with application to total variation penalties
• An Optimal Reduction of TV-Denoising to Adaptive Online Learning
• Graphon estimation via nearest neighbor algorithm and 2D fused lasso denoising
• Adaptive Online Estimation of Piecewise Polynomial Trends
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs
• Tree-Projected Gradient Descent for Estimating Gradient-Sparse Parameters on Graphs