Fast Algorithms for Detection of Structural Breaks in High Dimensional Data

Abstract

Many real time series data sets exhibit structural changes over time. It is then of interest to both estimate the (unknown) number of structural break points, together with the parameters of the statistical model employed to capture the relationships amongst the variables/features of interest. An additional challenge emerges in the presence of very large data sets, namely on how to accomplish these two objectives in a computational efficient manner. In this talk, we outline a novel procedure which leverages a block segmentation scheme (BSS) that reduces the number of model parameters to be estimated through a regularized least squares criterion. Specifically, BSS examines appropriately defined blocks of the available data, which when combined with a fused lasso based estimation criterion, leads to significant computational gains without compromising on the statistical accuracy in identifying the number and location of the structural breaks. This procedure is further coupled with new local and global screening steps to consistently estimate the number and location of break points. The procedure is scalable to large size high-dimensional time series data sets and can provably achieve significant computational gains. It is further applicable to various statistical models, including regression, graphical models and vector-autoregressive models. Extensive numerical work on synthetic data supports the theoretical findings and illustrates the attractive properties of the procedure. Applications to neuroimaging data will also be discussed.