Prediction bounds for higher order total variation regularized least squares

We establish adaptive results for trend filtering: least squares estimation\nwith a penalty on the total variation of $(k-1)^{\\rm th}$ order differences.\nOur approach is based on combining a general oracle inequality for the\n$\\ell_1$-penalized least squares estimator with "interpolating vectors" to\nupper-bound the "effective sparsity". This allows one to show that the\n$\\ell_1$-penalty on the $k^{\\text{th}}$ order differences leads to an estimator\nthat can adapt to the number of jumps in the $(k-1)^{\\text{th}}$ order\ndifferences of the underlying signal or an approximation thereof. We show the\nresult for $k \\in \\{1,2,3,4\\}$ and indicate how it could be derived for general\n$k\\in \\mathbb{N}$.\n