Adaptive Risk Bounds in Univariate Total Variation Denoising and Trend Filtering

Abstract

We study trend filtering, a relatively recent method for univariate nonparametric regression. For a given positive integer $r$, the $r$-th order trend filtering estimator is defined as the minimizer of the sum of squared errors when we constrain (or penalize) the sum of the absolute $r$-th order discrete derivatives of the fitted function at the design points. For $r=1$, the estimator reduces to total variation regularization which has received much attention in the statistics and image processing literature. In this paper, we study the performance of the trend filtering estimator for every positive integer $r$, both in the constrained and penalized forms. Our main results show that in the strong sparsity setting when the underlying function is a (discrete) spline with few "knots", the risk (under the global squared error loss) of the trend filtering estimator (with an appropriate choice of the tuning parameter) achieves the parametric $n^{-1}$ rate, up to a logarithmic (multiplicative) factor. Our results therefore provide support for the use of trend filtering, for every $r$, in the strong sparsity setting.

110 pages, 8 figures

References in corpus (5)

• Asymptotics for minimisers of convex processes
• Approximate Recovery in Changepoint Problems, from ${\ell }_2$ Estimation Error Rates
• Nonparametric Shape-restricted Regression
• On Estimation of Isotonic Piecewise Constant Signals
• Approximate $l_0$-penalized estimation of piecewise-constant signals on graphs

Cited by in corpus (10)

• Nonparametric Shape-restricted Regression
• 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
• Frame-constrained Total Variation Regularization for White Noise Regression
• Regret Minimization in Isotonic, Heavy-Tailed Contextual Bandits via Adaptive Confidence Bands
• Oracle inequalities for square root analysis estimators with application to total variation penalties
• Deep Nonparametric Estimation of Discrete Conditional Distributions via Smoothed Dyadic Partitioning
• Distributed Cartesian Power Graph Segmentation for Graphon Estimation
• Estimating Piecewise Monotone Signals