Optimal Covariance Change Point Localization in High Dimension

Abstract

We study the problem of change point detection for covariance matrices in high dimensions. We assume that we observe a sequence {X_i}_{i=1,...,n} of independent and centered p-dimensional sub-Gaussian random vectors whose covariance matrices are piecewise constant. Our task is to recover with high accuracy the number and locations of the change points, which are assumed unknown. Our generic model setting allows for all the model parameters to change with n, including the dimension p, the minimal spacing between consecutive change points, the magnitude of smallest change size and the maximal Orlicz- 2 norm of the covariance matrices of the sample points. Without assuming any additional structural assumption, such as low rank matrices or having sparse principle components, we set up a general framework and a benchmark result for the covariance change point detection problem. We introduce two procedures, one based on the binary segmentation algorithm (e.g. Vostrikova, 1981) and the other on its extension known as wild binary segmentation of Fryzlewicz (2014), and demonstrate that, under suitable conditions, both procedures are able to consistently es- timate the number and locations of change points. Our second algorithm, called Wild Binary Segmentation through Independent Projection (WBSIP), is shown to be optimal in the sense of allowing for the minimax scaling in all the relevant parameters. Our minimax analysis reveals a phase transition effect based on the problem of change point localization. To the best of our knowledge, this type of results has not been established elsewhere in the high-dimensional change point detection literature.

44 pages

References in corpus (8)

• Optimal detection of changepoints with a linear computational cost
• Optimal detection of sparse principal components in high dimension
• Change-point detection in panel data via double CUSUM statistic
• Uniform change point tests in high dimension
• Optimal hypothesis testing for high dimensional covariance matrices
• Change-point detection in high-dimensional covariance structure
• On change point detection using the fused lasso method
• On pattern recovery of the fused Lasso

Cited by in corpus (15)

• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
• Statistically and Computationally Efficient Change Point Localization in Regression Settings
• Optimal nonparametric change point detection and localization
• Localizing Changes in High-Dimensional Vector Autoregressive Processes
• Estimating a change point in a sequence of very high-dimensional covariance matrices
• A review on minimax rates in change point detection and localisation
• Change point localization in dependent dynamic nonparametric random dot product graphs
• Localizing Changes in High-Dimensional Regression Models
• ALMA: Alternating Minimization Algorithm for Clustering Mixture Multilayer Network
• Spectral Analysis of High-dimensional Time Series
• A causal fused lasso for interpretable heterogeneous treatment effects estimation
• Segmentation of high dimensional means over multi-dimensional change points and connections to regression trees
• Sequential (Quickest) Change Detection: Classical Results and New Directions
• Sequential Subspace Change-Point Detection
• Homogeneity Tests of Covariance and Change-Points Identification for High-Dimensional Functional Data