# Denoising and change point localisation in piecewise-constant high-dimensional regression coefficients

arXiv: https://arxiv.org/abs/2110.14298 · HTML: https://mlsanity.com/paper/2110.14298/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 53 references that are in the map.
- First posted on arXiv 27 Oct 2021.

## Builds on (most cited first, 9 of 9)

- [Adaptive piecewise polynomial estimation via trend filtering](https://mlsanity.com/paper/1304.2986/) (2013)
- [Univariate Mean Change Point Detection: Penalization, CUSUM and Optimality](https://mlsanity.com/paper/1810.09498/) (2018)
- [Optimal Change-Point Detection and Localization](https://mlsanity.com/paper/2010.11470/) (2020)
- [Localizing Changes in High-Dimensional Regression Models](https://mlsanity.com/paper/2010.10410/) (2020)
- [Functional Linear Regression with Mixed Predictors](https://mlsanity.com/paper/2012.00460/) (2020)
- [Prediction bounds for higher order total variation regularized least squares](https://mlsanity.com/paper/1904.10871/) (2019)
- [A review on minimax rates in change point detection and localisation](https://mlsanity.com/paper/2011.01857/) (2020)
- [On the total variation regularized estimator over a class of tree graphs](https://mlsanity.com/paper/1806.01009/) (2018)
- [Iterative Alpha Expansion for estimating gradient-sparse signals from linear measurements](https://mlsanity.com/paper/1905.06097/) (2019)

## Abstract (arXiv)

We study the theoretical properties of the fused lasso procedure originally proposed by citetibshirani2005sparsity in the context of a linear regression model in which the regression coefficient are totally ordered and assumed to be sparse and piecewise constant. Despite its popularity, to the best of our knowledge, estimation error bounds in high-dimensional settings have only been obtained for the simple case in which the design matrix is the identity matrix. We formulate a novel restricted isometry condition on the design matrix that is tailored to the fused lasso estimator and derive estimation bounds for both the constrained version of the fused lasso assuming dense coefficients and for its penalised version. We observe that the estimation error can be dominated by either the lasso or the fused lasso rate, depending on whether the number of non-zero coefficient is larger than the number of piece-wise constant segments. Finally, we devise a post-processing procedure to recover the piecewise-constant pattern of the coefficients. Extensive numerical experiments support our theoretical findings.