Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers
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) 2 estimation error rate, parametrized by n, 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 [12] 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 adaptivity of the total variation denoiser to these smaller Sobolev function spaces.
The authors answer some open questions about the statistical performance of TV denoising in higher dimensions: They provide new lower bounds for classes of bounded total variation in higher dimensions, as well as lower and matching upper bounds for linear estimators over the same class. Their results show that the performance of linear estimators can be significantly worse than TV denoising if one picks a suitable n-dependent scaling for the total variation, which can be motivated by asking for a natural embedding of the TV class into other regularity classes to hold. Moreover, they give lower bounds for Sobolev classes in higher dimensions and show that contrary to the TV case, these are attained by linear estimators. Finally, they pose the question of whether TV denoising manages to achieve the minimax risk for Sobolev classes in dimension d >= 3 the same way it does for d <= 2. 
Novelty  The authors did a fine job of completing the picture of statistical minimax rates for total variation classes. Since TV denoising is heavily used in 2D, any results pertaining to that regime are important. Maybe the most interesting contribution is their establishing the “right” scaling (which is not constant) to be used for the variation term to allow comparison with other derivative based regularity classes. After this has been done, most of the results are interesting, but can be shown with standard techniques together with new estimates of spectral statistics of the grid graph.  For example, the minimax rate for the TV class simply follows from the observation that the l_1 ball is embedded in it, so it can be immediately reduced to that case which is already available in the literature.  I also agree with the authors on the conjectured minimax performance of TV denoising for Sobolev classes in higher dimensions being intriguing.  Quality  The proofs are sound and are executed with sufficient level of detail to be understood by someone with limited background in that field. It would have been even nicer to provide a bit of background on some of the concepts involved in the proofs, e.g. (linear) minimax rates for quadratically convex sets, but since this is restricted to the proofs in the supplementary material, this choice for the sake of brevity might be appropriate.  The comments and discussion are helpful in order to appreciate the formulation of the results.  Impact  The paper offers some nice insight into theoretical performance bounds for a widely used denoising algorithm, which will be of interest to the imaging community as well as theoretical statistics. On the other hand, it does not offer new algorithmic insights nor fundamentally new proof techniques. However, it is notable that most of their lower bound results hold for arbitrary graphs. Also, the authors offer some venues for further exploration such as a possible generalization to trend filtering and investigating the performance of TV denoising over Sobolev classes in higher dimensions.  Clarity  The introduction and motivation sections are very well written and succeed in motivating the results that follow. The presentation of the results is clear and the comments helpful in putting them into context.  Minor comments/corrections:  Main paper:  Line 4: parametrized _by_?  Supplement:  Line 8: “and in the second”: That seems to be dangling here.  Display following line  39: “C_n” n missing  Display following line 49, third to last line: Parentheses around the summands would be helpful  Display following line 63, first line: Is it actually an equality here?  Line 64: Donoho’s paper could already be referenced with a number here.  Second display following 68: Variable clash for i_j, used twice in different contexts  Display following line 82: The paper uses k instead of \tau. Also, it should be \theta instead of \beta.  Third line of display following line 82: Here, something about the nullspace is being used to guarantee that we can write I \simeq D D^\dag. This should be explained in slightly more detail.  Display following line 90: Again, the nullspace has to be well-behaved to be able to write this.