Source-linked AI summary
Multiple-change-point detection for high dimensional time series via sparsified binary segmentation
Haeran Cho, Piotr Fryzlewicz
TL;DR
The paper addresses high-dimensional segmentation of second-order time-series structure, where standard CUSUM aggregation can fail. It proposes Sparsified Binary Segmentation and establishes consistency, alongside a multivariate Locally Stationary Wavelet model.
Problem
High-dimensional segmentation of multivariate time series’ second-order structure remains relatively underexplored, while standard maximum and average CUSUM aggregation can fail in some high-dimensional scenarios.
Method
Sparsified Binary Segmentation aggregates CUSUM statistics from local periodograms and cross-periodograms only when they pass a threshold, reducing irrelevant noisy contributions.
Results
The paper establishes SBS consistency for the number and location of change-points, with location-estimator convergence improving on prior binary-segmentation results and being near-optimal in the univariate case.
Takeaways & Limitations
The work provides a high-dimensional binary-segmentation approach and introduces a multivariate Locally Stationary Wavelet model for establishing its consistency.
Takeaways & Limitations
The SBS algorithm imposes a restriction on change-point dispersion, and high-dimensional scenarios exist where the compared estimators fail.
Abstract
from arXiv · showhide
Time series segmentation, a.k.a. multiple change-point detection, is a well-established problem. However, few solutions are designed specifically for high-dimensional situations. In this paper, our interest is in segmenting the second-order structure of a high-dimensional time series. In a generic step of a binary segmentation algorithm for multivariate time series, one natural solution is to combine CUSUM statistics obtained from local periodograms and cross-periodograms of the components of the input time series. However, the standard "maximum" and "average" methods for doing so often fail in high dimensions when, for example, the change-points are sparse across the panel or the CUSUM statistics are spuriously large. In this paper, we propose the Sparsified Binary Segmentation (SBS) algorithm which aggregates the CUSUM statistics by adding only those that pass a certain threshold. This "sparsifying" step reduces the impact of irrelevant, noisy contributions, which is particularly beneficial in high dimensions. In order to show the consistency of SBS, we introduce the multivariate Locally Stationary Wavelet model for time series, which is a separate contribution of this work.
1 Introduction
The paper addresses multiple change-point detection in the second-order structure of possibly high-dimensional multivariate time series. It proposes Sparsified Binary Segmentation and establishes consistency within a new multivariate Locally Stationary Wavelet framework.
- Motivation: High-dimensional multivariate series can exhibit nonstationarity, strong correlations, and massive volume, while segmentation of their second-order structure remains comparatively underexplored.The paper models autocovariance and cross-covariance as approximately piecewise constant between change-points.
- Method: Sparsified Binary Segmentation (SBS) is a CUSUM-based binary segmentation algorithm for identifying multiple change-points in second-order structure.Its input consists of localized periodograms and cross-periodograms computed from the original multivariate series.
- Method: SBS thresholds individual CUSUM statistics and aggregates only surviving temporal fragments, reducing contributions from sequences without change-points.The dimension-reduction step is expected to be particularly beneficial in high-dimensional settings.
- Method: CUSUM aggregation automatically identifies common change-points across components, avoiding post-processing needed when components are segmented separately.This characteristic is described as particularly attractive in high-dimensional situations.
- Theory: The paper proves consistency for the number and locations of change-points, with location-estimation rates improving on earlier univariate binary-segmentation results and being near-optimal under stated spacing conditions.The theoretical analysis adapts proof techniques to the high-dimensional time-series setting.
- Theory: The multivariate Locally Stationary Wavelet model provides the theoretical setting for the consistency results and is presented as a separate contribution.It extends univariate and bivariate LSW models to multivariate time series.
2 The SBS algorithm in a generic setting
The SBS algorithm extends binary segmentation to panels of multiplicative sequences by aggregating only CUSUM statistics that exceed a threshold. It is designed for high-dimensional settings where standard average and maximum aggregation can fail, and its consistency is established under stated assumptions.
- Algorithm: SBS extends univariate binary segmentation to a panel of multiplicative sequences by examining component CUSUM statistics simultaneously.The algorithm recursively locates candidate change-points and continues on the resulting left and right intervals.
- Algorithm: Only component CUSUM statistics exceeding πT contribute to the aggregated SBS statistic.An indicator function retains contributions above the threshold, so the statistic is non-zero when at least one component exceeds πT.
- High-dimensional behavior: Standard average aggregation can fail when change-points are sparse across a high-dimensional panel, whereas thresholded aggregation maintains the peak near the true change-point.In the d = 100 sparse example, averaging many irrelevant CUSUM statistics moves the maximum far from the true change-point, while thresholded aggregation succeeds.
- High-dimensional behavior: Spuriously large CUSUM statistics can also undermine standard aggregation, while SBS is reported to handle this high-dimensional difficulty better.The example attributes a spurious large value to strong autocorrelation and reports successful localization by the thresholded statistic around t = 100.
- Consistency: Under (A1)–(A4), SBS consistently estimates the number of change-points and locates each one within C1εT.When δT ≍ T, the localization rate εT is described as near-optimal up to a logarithmic factor; the theorem also allows d to diverge with T.
3 The SBS algorithm in the multivariate LSW model
The multivariate LSW model links piecewise-constant second-order structure to wavelet periodograms and cross-periodograms, providing inputs for SBS segmentation. The construction also motivates a non-negative multiplicative alternative for cross-periodograms and establishes consistency under stated conditions.
- Multivariate LSW model: The multivariate LSW model represents multivariate, piecewise stationary time series using wavelet-based building blocks and scale- and location-dependent transfer functions.
- Second-order structure: Autocovariance and cross-covariance functions inherit piecewise constancy from the model parameters, with identical change-point locations.
- Detection inputs: Changes in multivariate second-order structure are detectable from wavelet periodograms and cross-periodograms across multiple scales.
- Cross-periodogram alternative: A non-negative multiplicative alternative to the wavelet cross-periodogram follows the multiplicative model up to negligible biases while retaining the same change-point information.
- SBS-MVTS: SBS-MVTS applies sparsified binary segmentation to multivariate time series with piecewise constant second-order structure.
- Consistency: Theorem 2 states that, under (B1)–(B5), the estimated number and locations of change-points satisfy consistency bounds for the specified threshold regimes.
4 Simulation study
Simulations compare thresholded, average, and maximum binary-segmentation variants across multivariate settings with sparse, moderate, and dense changes. The thresholded method performs best overall, particularly for location accuracy and sparse changes.
- Simulation settings: The simulated studies include autoregressive, factor-model, and other multivariate settings with controlled sparsity and changing dependence structures.
- Experimental design: The simulations evaluate SBS-MVTS against otherwise identical binary-segmentation algorithms using average and maximum aggregation.
- Overall comparison: THR outperforms AVG and MAX overall, while AVG is especially weaker for sparse change-points and tends to overestimate their number.
- Location accuracy: THR and MAX detect similar numbers of change-points, but THR locates them more accurately, especially in models (M3)–(M4).
- Aggregation behavior: THR typically combines information across many components, whereas MAX effectively bases locations on one individual component.
- Robustness: THR performance changes little between p = 50 and p = 100, and location accuracy remains preserved when change-points are not aligned.
5 Detecting change-points in the component processes of S&P 500
The SBS-MVTS algorithm is applied to S&P 500 constituent returns, producing change-points whose patterns are examined against historical financial events and stationarity diagnostics.
- Data and setup: The study analyzes daily closing-price time series for 456 S&P 500 constituents from 1 January 2007 to 31 December 2011.The selected constituents remained in the index throughout the recent financial crisis.
- Detection results: SBS-MVTS detected change-points in subsets of the component processes, with detections from the first 100 components also represented among those from the first 200.The first-100 analysis returned t = 67, 129, 198, 276, 427, 554, 718, 864, 1044, 1147.
- Detection results: Applied to the full p-variate series, SBS-MVTS returned the change-points summarized in Table 5, alongside nearby historical events.The corresponding TED-spread change-points are marked in Figure 4.
- Financial interpretation: The volatile TED spread during 2007–2011 is reflected in some of the change-points detected by SBS-MVTS.The TED spread rose during the subprime mortgage crisis, exceeded 300 bps in mid-September 2008, and rose again during the European debt crisis.
- Validation: Multivariate stationarity testing was difficult because few procedures existed and the available methods were not easily applicable at p = 456.The analysis therefore examined the first few principal-component series within each segment.
- Validation: Stationarity and residual diagnostics generally supported the detected segmentation, although some segments suggested additional changes were blocked by the algorithm’s dispersion restriction.Most segments containing change-points had at least one small p-value, while segments without change-points generally had p-values above α∗.
A Proof of Theorem 1
The proof establishes consistency of binary segmentation by showing that detectable peaks identify change-points accurately and that recursive segmentation continues until all relevant changes are found under the stated assumptions.
- Recursive termination: The remaining lemmas show that segments with changes still to be detected satisfy conditions ensuring either a detectable signal or termination near segment boundaries.These conditions support the iterative consistency argument for all change-points.
- Localization: Lemma 4 bounds the estimated change-point’s error by c0εT when the true change-point lies in the admissible interval Ds,e.The interval restricts the relative segment lengths around the candidate change-point.
- Single-sequence consistency: For a single sequence, the algorithm detects and locates each change-point within distance c0εT of a true change-point with probability tending to one.The argument proceeds recursively, with detected change-points preserving the conditions needed for subsequent steps.
- Multisequence extension: The proof extends to d > 1 sequences by considering segments containing one or more change-points under spacing and balance conditions.The assumptions require separated change-points and control over the spacing of consecutive changes.
- Thresholding argument: Within the relevant interval, thresholding does not affect the peak around a change-point, so the sparsified statistic retains the CUSUM-type peak needed for detection.The thresholded statistic has the same functional form as the CUSUM statistic near the change-point.
B Multivariate LSW time series
The multivariate LSW model represents high-dimensional time series through evolving wavelet spectra and cross-spectra, linking these quantities to second-order dependence and its change-points.
- The model enables time-scale decomposition and rigorous estimation of a multivariate process’s second-order structure.
- Its primary modelling quantities are the Evolutionary Wavelet Spectrum and Evolutionary Wavelet Cross-spectrum.
- Under (B1)–(B2), EWS and EWCS changes correspond asymptotically one-to-one with autocovariance and cross-covariance changes.
- The expectations of wavelet periodograms and cross-periodograms correspond asymptotically to autocovariance and cross-covariance functions.
- Consequently, change-points in autocovariance and cross-covariance functions are detectable through the corresponding wavelet periodogram sequences.
B.1 Proof of Theorem 2
The proof establishes that SBS remains consistent when applied across wavelet scales, identifying all detectable change-points with the required rates under the stated assumptions.
- Applying SBS to the transformed series yields consistent change-point estimates under (A1), (A4), and (B3)–(B4).
- The estimator recovers the correct number of change-points, with |η̃_q − η_q| < C3ε_T for every q as T → ∞.
- At a single scale, SBS consistently detects all change-points detectable from that scale’s wavelet periodograms and cross-periodograms.
- A suitable finest-scale cutoff ensures all change-points are detectable at some scale, while SBS-MVTS applies SBS across the finest |I*_T| scales.
- SBS-MVTS consistency with the required rates follows from across-scales post-processing.
B.2 Proof of Proposition 1
The proof of Proposition 1 bounds approximation errors between the multivariate LSW model’s second-order quantities, showing the relevant discrepancy vanishes asymptotically.
- The wavelet representation uses a logarithmic scale cutoff JT = log2 T for the modified model.
- Because the wavelet-product support is localized, only indices within distance K2^JT of a change-point contribute to one proof term.
- Under (B1)–(B2), the proof separately bounds the contributing terms using wavelet autocorrelation and jump-magnitude controls.
- The combined error satisfies I + II = o(1), establishing the required asymptotic approximation.
B.3 Proof of Proposition 3
The proof of Proposition 3 transfers change-point detectability and localization guarantees from the original series to the approximating transformed series used by SBS.
- Any change-point in σ^(k)(t/T) induces a change-point in the transformed series within an interval containing the original location.
- The transformed and original series produce CUSUM statistics of the same order at the relevant change-point.
- The maximizer of the transformed CUSUM statistic satisfies |η̂ − η̄| ≤ c0ε_T.
- The minimum-separation condition prevents additional change-points from being detected too close to an already detected one.