Optimal rates for total variation denoising

Abstract

Motivated by its practical success, we show that the two-dimensional total variation denoiser satisfies a sharp oracle inequality that leads to near optimal rates of estimation for a large class of image models such as bi-isotonic, Hölder smooth and cartoons. Our analysis hinges on properties of the unnormalized Laplacian of the two-dimensional grid such as eigenvector delocalization and spectral decay. We also present extensions to more than two dimensions as well as several other graphs.

arXiv comment30 pages, 3 figures

References in corpus (4)

• Properties and refinements of the fused lasso
• On matrix estimation under monotonicity constraints
• On pattern recovery of the fused Lasso
• Regression modeling on stratified data with the lasso

Cited by in corpus (29)

• Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers
• The DFS Fused Lasso: Linear-Time Denoising over General Graphs
• Semi-supervised Learning in Network-Structured Data via Total Variation Minimization
• Vector-Valued Graph Trend Filtering with Non-Convex Penalties
• Multiple testing with the structure adaptive Benjamini-Hochberg algorithm
• 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
• New Risk Bounds for 2D Total Variation Denoising
• Synthesis and analysis in total variation regularization
• Non-parametric Quantile Regression via the K-NN Fused Lasso
• Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees
• On the total variation regularized estimator over a class of tree graphs
• Approximate $l_0$-penalized estimation of piecewise-constant signals on graphs
• A Variational View on Statistical Multiscale Estimation
• Graph-based regularization for regression problems with alignment and highly-correlated designs
• Iterative Alpha Expansion for estimating gradient-sparse signals from linear measurements
• On a phase transition in general order spline regression
• Frame-constrained Total Variation Regularization for White Noise Regression
• An Optimal Reduction of TV-Denoising to Adaptive Online Learning
• Oracle inequalities for square root analysis estimators with application to total variation penalties
• Exponential Family Trend Filtering on Lattices
• Graph-Fused Multivariate Regression via Total Variation Regularization
• A causal fused lasso for interpretable heterogeneous treatment effects estimation
• Learning Networked Exponential Families with Network Lasso
• Topologically penalized regression on manifolds
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs
• Total Variation Regularized Tensor-on-scalar Regression
• Distributed Cartesian Power Graph Segmentation for Graphon Estimation