Prediction bounds for higher order total variation regularized least squares
This work provides theoretical guarantees for trend filtering in signal processing, offering incremental improvements in statistical estimation by adapting to signal complexity.
The paper tackles the problem of establishing adaptive prediction bounds for trend filtering with higher-order total variation regularization, showing that the estimator adapts to the number of jumps in the underlying signal's differences, with results provided for orders up to 4 and extended to general orders.
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 $\ell_1$-penalized least squares estimator with "interpolating vectors" to upper-bound the "effective sparsity". This allows one to show that the $\ell_1$-penalty on the $k^{\text{th}}$ order differences leads to an estimator that can adapt to the number of jumps in the $(k-1)^{\text{th}}$ order differences of the underlying signal or an approximation thereof. We show the result for $k \in \{1,2,3,4\}$ and indicate how it could be derived for general $k\in \mathbb{N}$.