Prediction bounds for higher order total variation regularized least squares

We establish adaptive results for trend filtering: least squares estimation with a penalty on the total variation of (k-1)rm th order differences. Our approach is based on combining a general oracle inequality for the ℓ1-penalized least squares estimator with "interpolating vectors" to upper-bound the "effective sparsity". This allows one to show that the ℓ1-penalty on the kth order differences leads to an estimator that can adapt to the number of jumps in the (k-1)th order differences of the underlying signal or an approximation thereof. We show the result for k ∈ 1,2,3,4 and indicate how it could be derived for general k∈ mathbbN.