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

Fan Wang, Oscar Hernan Madrid Padilla, Yi Yu, Alessandro RinaldoAISTATS 2022

Abstract

This paper provides a rigorous theoretical framework for the fused lasso in high-dimensional linear regression with general design matrices. We prove that the fused lasso is highly effective for denoising piecewise-constant coefficients and introduce a post-processing "filtering" pipeline that achieves near-optimal consistency in locating change points. Empirical results on synthetic and real-world datasets, such as NIR spectroscopy, demonstrate that capturing piecewise-constant structure significantly improves predictive accuracy compared to standard Lasso and Elastic Net.

Introduction

In high-dimensional regression, where the number of predictors $p$ exceeds the number of observations $n$, standard approaches often assume coefficient sparsity. However, in fields such as genetics, finance, and spectroscopy, regression coefficients frequently exhibit a piecewise-constant structure—remaining stable over intervals and shifting only at specific "change points."

The fused lasso is a popular regularization technique designed for such structures, penalizing both the $\ell_1$-norm of the coefficients (sparsity) and the $\ell_1$-norm of their successive differences (piecewise-constancy). Despite its widespread use, theoretical guarantees for the fused lasso were previously limited to the identity-matrix case. This work bridges that gap, providing error bounds for general design matrices with correlated predictors.

Methodology

The study analyzes two variants of the fused lasso: a constrained estimator, which minimizes least squares subject to a total variation constraint, and a penalized estimator, which incorporates both lasso and fused penalties. To handle general design matrices, the authors introduce a novel Restricted Isometry Condition (RIC), ensuring the design matrix does not excessively "smear" structured signals.

Recognizing that $\ell_1$-type estimators can be imprecise in identifying exact jump locations, the authors propose a two-stage post-processing pipeline:

  1. Mean Filtering (FLMF): Smooths the initial estimate to eliminate spurious noise.
  2. Time Filtering (FLMTF): Prunes estimated change points to ensure consistency with the underlying signal structure.

Key Results and Empirical Evaluation

The theoretical analysis reveals that estimation error is governed by a "tug-of-war" between standard lasso rates and fused lasso rates, depending on whether the signal is primarily sparse or structured. The derived denoising bounds for the constrained estimator are within a logarithmic factor of the oracle rate.

The effectiveness of the fused lasso was validated using synthetic simulations and real-world datasets, including an Air Quality dataset and a "Cookie Dough" NIR spectroscopy dataset ($n=72, p=700$). In the spectroscopy analysis, the goal was to predict sucrose content based on light wavelengths, where coefficients are naturally piecewise-constant.

Comparison of Fused Lasso (FL), Lasso, and Elastic Net on the Cookie Dough dataset.

As shown in the results, the Fused Lasso (FL) significantly outperformed standard Lasso and Elastic Net in terms of Mean Squared Error (MSE), achieving 0.122 compared to 0.136 and 0.138, respectively. This highlights the importance of incorporating structural priors into the regularization framework. While the raw FL estimate may produce many non-zero coefficients, the proposed filtering methods are designed to refine these into a consistent set of change points.

Conclusion

This work establishes the first comprehensive theoretical foundation for the fused lasso in general high-dimensional settings. By combining sharp denoising bounds with a consistent localization pipeline, the authors provide a robust tool for analyzing piecewise-constant signals. Future research may focus on relaxing geometric conditions on the design matrix to accommodate even higher-dimensional regimes and exploring the "under-fitting" case where the total variation budget is underestimated.

Summary updated

BibTeX
@inproceedings{wang2022denoising,
  author = {Fan Wang and Oscar Hernan Madrid Padilla and Yi Yu and Alessandro Rinaldo},
  title = {{Denoising and change point localisation in piecewise-constant high-dimensional regression coefficients}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
}
Figure