Computationally efficient change point detection for high-dimensional regression

2016/01/14 by Florencia Leonardi, Peter Bühlmann, Leonardi, Florencia +1 · 4 citations
Engineering · Mathematics · #Computation (stat.CO) #Control Systems and Identification #FOS: Computer and information sciences #FOS: Mathematics #Methodology (stat.ME) #Statistical Methods and Inference #Statistical and numerical algorithms #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1601.03704

openalex publication_date 2016/01/14 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

Large-scale sequential data is often exposed to some degree of inhomogeneity in the form of sudden changes in the parameters of the data-generating process. We consider the problem of detecting such structural changes in a high-dimensional regression setting. We propose a joint estimator of the number and the locations of the change points and of the parameters in the corresponding segments. The estimator can be computed using dynamic programming or, as we emphasize here, it can be approximated using a binary search algorithm with O(n log(n) Lasso(n)) computational operations while still enjoying essentially the same theoretical properties; here Lasso(n) denotes the computational cost of computing the Lasso for sample size n. We establish oracle inequalities for the estimator as well as for its binary search approximation, covering also the case with a large (asymptotically growing) number of change points. We evaluate the performance of the proposed estimation algorithms on simulated data and apply the methodology to real data.

Citations

• Optimal Detection of Changepoints With a Linear Computational Cost
• Change Point Detection in Correlation Networks
• A model selection approach for multiple sequence segmentation and\n dimensionality reduction

Cited by

• Multiple Changepoint Estimation in High-Dimensional Gaussian Graphical Models
• A review on minimax rates in change point detection and localisation
• Sparse Group Fused Lasso for Model Segmentation
• Change-point detection in a linear model by adaptive fused quantile method

Related

• An efficient two step algorithm for high dimensional change point regression models without grid search
• Simultaneous Change Point Detection and Identification for High Dimensional Linear Models
• Change Point Detection for High-dimensional Linear Models: A General Tail-adaptive Approach
• Detection and estimation of parameters in high dimensional multiple change point regression models via ℓ₁/ℓ₀ regularization and discrete optimization
• Divide and Conquer Dynamic Programming: An Almost Linear Time Change Point Detection Methodology in High Dimensions