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

Fan Wang, Oscar Madrid, Yi Yu, Alessandro Rinaldo
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:4309-4338, 2022.

Abstract

We study the theoretical properties of the fused lasso procedure originally proposed by Tibshirani et al. (2005) 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-wang22c, title = { Denoising and change point localisation in piecewise-constant high-dimensional regression coefficients }, author = {Wang, Fan and Madrid, Oscar and Yu, Yi and Rinaldo, Alessandro}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {4309--4338}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/wang22c/wang22c.pdf}, url = {https://proceedings.mlr.press/v151/wang22c.html}, abstract = { We study the theoretical properties of the fused lasso procedure originally proposed by Tibshirani et al. (2005) 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. } }
Endnote
%0 Conference Paper %T Denoising and change point localisation in piecewise-constant high-dimensional regression coefficients %A Fan Wang %A Oscar Madrid %A Yi Yu %A Alessandro Rinaldo %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-wang22c %I PMLR %P 4309--4338 %U https://proceedings.mlr.press/v151/wang22c.html %V 151 %X We study the theoretical properties of the fused lasso procedure originally proposed by Tibshirani et al. (2005) 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.
APA
Wang, F., Madrid, O., Yu, Y. & Rinaldo, A.. (2022). Denoising and change point localisation in piecewise-constant high-dimensional regression coefficients . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:4309-4338 Available from https://proceedings.mlr.press/v151/wang22c.html.

Related Material