PaperlayerView exact revision on arXiv

Source-linked AI summary

High-dimensional changepoint estimation via sparse projection

Tengyao Wang, Richard J. Samworth

arXiv:1606.06246v2stat.MEmath.ST

TL;DR

The paper studies how to estimate changepoints in high-dimensional time series when mean changes occur in unknown sparse coordinate subsets. It proposes inspect, which derives a CUSUM-based sparse projection and applies univariate changepoint estimation, achieving finite-sample guarantees and strong performance across varied settings. The method is intended for offline estimation and has limitations tied to sparse-projection computation and model specification.

  • Problem

    Estimating the number and locations of changepoints is challenging when high-dimensional mean changes occur in an unknown sparse subset of coordinates.

  • Method

    Inspect obtains a projection direction from a convex relaxation of sparse singular-vector estimation on the CUSUM-transformed data, then applies univariate estimation and Wild Binary Segmentation.

  • Results

    Under appropriate conditions, inspect recovers the correct changepoint count and estimates locations accurately with high probability; its single-changepoint rate is within a doubly logarithmic factor of minimax optimal.

  • Takeaways & Limitations

    Numerical studies indicate that inspect performs extremely well across a wide variety of settings for high-dimensional changepoint estimation.

  • Takeaways & Limitations

    The classical binary-segmentation variant is sensitive to model misspecification, while the online changepoint problem is beyond the paper’s scope.

Abstract

from arXiv · show

Changepoints are a very common feature of Big Data that arrive in the form of a data stream. In this paper, we study high-dimensional time series in which, at certain time points, the mean structure changes in a sparse subset of the coordinates. The challenge is to borrow strength across the coordinates in order to detect smaller changes than could be observed in any individual component series. We propose a two-stage procedure called `inspect' for estimation of the changepoints: first, we argue that a good projection direction can be obtained as the leading left singular vector of the matrix that solves a convex optimisation problem derived from the CUSUM transformation of the time series. We then apply an existing univariate changepoint estimation algorithm to the projected series. Our theory provides strong guarantees on both the number of estimated changepoints and the rates of convergence of their locations, and our numerical studies validate its highly competitive empirical performance for a wide range of data generating mechanisms. Software implementing the methodology is available in the R package `InspectChangepoint'.

1 Introduction

The paper addresses high-dimensional changepoint estimation when mean changes affect an unknown sparse subset of coordinates. It introduces inspect, which projects the data using a CUSUM-based direction before applying univariate changepoint estimation, with theoretical and numerical support.

  • Motivation: High-dimensional time series can exhibit changepoints in sparse, unknown subsets of coordinates, making their number and locations challenging to estimate.Such changepoints can partition data into stationary segments and may themselves be practically important.
  • Method: Inspect first seeks a projection direction aligned with the vector of mean changes, then applies an existing univariate changepoint algorithm to the projected series.For multiple changepoints, the single-changepoint procedure is combined with Wild Binary Segmentation.
  • Method: At the population level, the mean-change vector is the leading left singular vector of the CUSUM-transformed mean matrix, motivating the projection construction.The data-driven direction comes from a convex relaxation of the otherwise combinatorial sparse singular-vector problem.
  • Illustration: In a simulated 2000 × 1000 dataset with changepoints at 500, 1000 and 1500, inspect detected all three changes using sparse mean shifts across 40 coordinates.The squared ℓ2 norms of the mean-change vectors were 0.4, 0.9 and 1.6, respectively.
  • Illustration: The detected changepoints were very close to their true locations, and only those three locations produced sufficiently large projected CUSUM statistics.The figure illustrates thresholding after running Wild Binary Segmentation to completion for display purposes.
  • Theory and evidence: Finite-sample theory guarantees, under appropriate conditions, recovery of the correct changepoint count and specified location accuracy with high probability.In the single-changepoint case, the location rate is within a doubly logarithmic factor of the minimax optimal rate; numerical studies cover varied settings.

2 Problem description

The paper formulates high-dimensional changepoint estimation for independent vector observations whose mean vectors are piecewise constant over time. Signal strength depends on mean-change magnitudes and segment lengths, while noise depends on variance and dimensionality.

  • Model: The observations are combined into a p × n matrix, with independent columns and a piecewise-constant mean structure containing ν + 1 segments.There are ν changepoints separating the stationary segments.
  • Sparsity: Mean changes are assumed to be sparse, with a sparsity level k typically much smaller than the ambient dimension p.The methodology is designed to aggregate signals across an unknown sparse subset of coordinates.
  • Scope: The method does not require prior knowledge of the sparsity level and can also be applied in non-sparse settings.Its best performance is expected when signals are spread across an unknown sparse coordinate subset.
  • Estimation target: The goal is to estimate the changepoint set when p may be comparable to or larger than the series length n.The problem’s signal depends on mean-change magnitudes and stationary-segment lengths, whereas noise is related to variance σ2 and dimensionality p.
  • Theoretical framework: The finite-sample framework assumes specified conditions on changepoint locations and mean-change magnitudes to establish consistency and convergence rates.The procedure is described through distribution classes indexed by sample size, dimension, sparsity, changepoint count, signal, spacing and variance.

3 Data-driven projection estimator for a single changepoint

The single-changepoint procedure estimates a sparse projection from the CUSUM-transformed data, then locates the change in the projected series. Convex relaxations make the projection computable, while theory establishes consistency and near-minimax localization rates under stated conditions.

  • Projection target: The oracle projection direction is v = θ/∥θ∥2, which maximizes the magnitude of the projected mean difference between the two segments.Because θ is unknown, the method estimates a sparse direction from the CUSUM transformation.
  • Procedure: The method applies a CUSUM transformation, estimates a sparse leading left singular vector, and locates the changepoint by maximizing the projected one-dimensional CUSUM.The projection aggregates the rows before applying an existing univariate changepoint procedure.
  • Computational relaxation: The ideal sparse singular-vector optimization is NP-hard, so inspect uses a convex relaxation based on nuclear-norm and sparsity constraints.The convex problem can be solved with ADMM; a further relaxation enables faster soft-thresholding at some loss in statistical efficiency.
  • Theory: Under the theorem’s conditions, the estimator recovers the correct changepoint count and localizes the single changepoint at a rate within a doubly logarithmic factor of minimax.The finite-sample guarantees hold with high probability, and once the signal condition is satisfied the final rate does not depend on τ.
  • Theory: If a+b+c/2 < 1/2, the asymptotic single-changepoint estimator is consistent with rate ρ_n = o(n^(-1+2a+δ)) for any δ > 0.This regime assumes log p = O(log n), σ constant, ϑ ≍ n^-a, τ ≍ n^-b, and k ≍ n^c.

4 Estimating multiple changepoints

For multiple changepoints, inspect is embedded in wild binary segmentation, which searches random time windows and recursively segments around selected candidates. Under stated conditions, it consistently estimates all changepoints with explicit convergence rates.

  • Multiple-changepoint procedure: Wild binary segmentation runs the single-changepoint estimator on random time windows, selects the candidate with the largest projected CUSUM statistic, and recurses on both subsegments.Candidates above a threshold are admitted and the procedure continues using windows contained within the resulting subsegments.
  • Multiple-changepoint procedure: The multiple-changepoint algorithm uses regularization λ, Monte Carlo window count Q, window-spacing parameter β, and threshold ξ to control recursive segmentation.Theorem 5 supplies parameter choices yielding theoretical guarantees for consistent estimation.
  • Motivation: Classical binary segmentation can lose power when multiple changepoints offset one another in CUSUM calculations, motivating the random-window strategy.Offsetting signals can create smaller peaks that are more easily contaminated by noise.
  • Theory: If ρ < β/2 ≤ τ/C and Cρkτ^2 ≤ 1, Theorem 5 guarantees consistent estimation of all changepoints for the sample-splitting variant under its stated assumptions.The theorem assumes independent X and X′ and nτ ≥ 14.
  • Theory: If a+b+c/2 < 1/2 and 2a+5b < 1, Algorithm 4′ consistently estimates all changepoints with rate ρ_n = o(n^(-(1−2a−4b)+δ)) for any δ > 0.The asymptotic regime assumes σ is constant, ϑ ≍ n^-a, τ ≍ n^-b, k ≍ n^c, and log p = O(log n).
  • Theory: The multiple-changepoint consistency result also implies convergence in other natural metrics, including Hausdorff and L1-Wasserstein distances.These implications hold with probability tending to 1 under the stated consistency result.

5 Numerical studies

The numerical studies evaluate inspect across tuning choices, sparsity levels, competing methods, and model misspecifications. Inspect is highly competitive for single changepoints, remains effective beyond sparse settings, and is robust to several deviations from the baseline model.

  • Tuning and implementation: λ = σ√(2^-1 log(p log n)) is recommended in practice, and Figure 2 shows this choice is sensible in the illustrated setting.The implementation estimates noise levels separately for each component using scaled median absolute deviations of first-order differences.
  • Simulation design: The simulations compare inspect with dc, sbs, scan, agg2 and agg∞ across single- and multiple-changepoint settings.The study varies n, p, sparsity k, signal strength, and changepoint configurations.
  • Single changepoint estimation: Inspect performs very close to the oracle estimator when k is small, with oracle root mean squared errors of 10.0, 8.1 and 7.8 for the three reported sample sizes.The oracle estimator’s performance depends on n, z, ϑ and σ2, but not on k or p.
  • Single changepoint estimation: Inspect has extremely competitive single-changepoint performance and remains relatively effective when k = p, especially at larger signal strengths.Figure 3 visualizes estimated-location densities for inspect and three competing methods in two parameter settings.
  • Model misspecification: Inspect is robust to temporal and spatial dependence structures, non-Gaussian noise, and other forms of model misspecification in the reported experiments.Table 3 reports root mean squared errors under these alternatives.

6 Extensions: temporal or spatial dependence

The extensions adapt inspect to temporal and spatial dependence while retaining the sparse-projection framework. The spatial version estimates a precision matrix and can match the independent-data convergence rate when dependence is not too strong.

  • Extension setting: The extension studies more realistic streaming settings with temporal or spatial dependence, focusing theoretically on the single-changepoint case.The mean structure is retained from the main model.
  • Temporal dependence: Under temporal dependence, the noise is modeled as a centered stationary Gaussian process with diagonal lag-covariance matrices, while the oracle direction remains unchanged.The temporal setup assumes component series evolve independently across coordinates.
  • Spatial dependence: For spatial dependence, the oracle projection direction is modified using the precision matrix Θ = Σ^-1.An estimator of Θ is used to transform the leading singular-vector estimate into an estimate of the oracle direction.
  • Spatial dependence: When spatial dependence is not too strong and Θ is reasonably estimated, the extended inspect procedure attains the same convergence rate as under independence.The rate deteriorates as dependence approaches the boundary of its allowed range.
  • Numerical comparison: In simulations, Algorithm 5 improves on vanilla inspect across all considered λ values by accounting for spatial dependence.Figure 6 compares the two procedures under local and spatial dependence structures.
  • Spatial dependence: Algorithm 5 uses sample splitting, separate CUSUM transformations, convex optimization, projection, and precision-matrix estimation for spatially dependent data.The procedure then applies the resulting projected series within the changepoint pipeline.

7 Proofs of main results

The proofs establish guarantees by controlling projection-direction error and then analyzing the projected univariate CUSUM estimator. The argument extends from a single changepoint to recursive multiple-changepoint identification.

  • Single changepoint proof: The proof begins by controlling the angle between the estimated projection direction and the normalized vector of mean changes.This direction is the optimal projection direction for the theoretical analysis.
  • Single changepoint proof: After projection, the transformed series has a one-dimensional mean structure with a changepoint, and the estimator selects the location maximizing the absolute projected CUSUM statistic.The proof represents the projected CUSUM as signal plus error.
  • Single changepoint proof: The location proof compares the projected signal at the true and estimated maximizers and bounds the resulting error through events controlling noise and projection quality.These bounds yield a high-probability localization result under the theorem’s conditions.
  • Multiple changepoint proof: For multiple changepoints, the proof analyzes every wild-binary-segmentation call and shows its interval endpoints remain near true changepoints.A detected candidate is identified to a true changepoint when its distance is at most nρ.
  • Multiple changepoint proof: The recursion distinguishes intervals containing no changepoint from intervals containing at least one internal changepoint using the projected CUSUM maximum and threshold ξ = λ.In the latter case, a candidate changepoint is detected and the argument continues on the two resulting subintervals.

Online supplementary material for ‘High-dimensional changepoint

The online supplement contains additional theoretical results and auxiliary lemmas used to prove the main paper’s theorems.

  • Supplement scope: The supplement presents additional theoretical results referenced in the main text.It also includes auxiliary results needed for the proofs of the main theorems.
  • Supplement scope: Its subsequent subsections provide auxiliary results used in the proofs of the main theorems.

8 Additional theoretical results

The additional results establish theoretical guarantees for sparse projection estimation, minimax near-optimality, and extensions to locally or globally spatially dependent data.

  • Sparse projection theory: The computationally inefficient k-sparse leading left singular-vector estimator provides a theoretical analogue of the main projection result.The result concerns the estimator that directly optimises over sparse leading singular vectors.
  • Sparse projection theory: The population oracle projection direction equals the normalised sparse mean-change vector, and the estimated direction is analysed through projected signal and noise components.The proof represents the mean CUSUM matrix as A = θγ^⊤, yielding v = θ/∥θ∥2.
  • Minimax rates: The inspect algorithm attains the minimax optimal single-changepoint estimation rate up to a factor of log log n.This conclusion follows by combining the minimax lower bound with the corresponding upper bound.
  • Minimax rates: When ϑ/σ < 2(nτ)^-1/2, consistent changepoint estimation is impossible; for large constant signal-to-noise ratio, exact location estimation is possible with high probability.The intermediate regime 2(nτ)^-1/2 ≤ ϑ/σ ≤ 1 is described as challenging but feasible.
  • Spatial dependence: Modified inspect guarantees are developed for both local and global spatial dependence, with tuning and error bounds depending on the dependence structure.For local dependence, the covariance is specified by Σ_i,j = ρ^|i−j|; the displayed bounds include terms involving p, n, ρ, and m.

9 Auxiliary results

These auxiliary results establish the matrix-analytic, probabilistic, and dependence-related ingredients used to support inspect’s theoretical guarantees.

  • Matrix analysis: The nuclear norm is characterized through singular values and is invariant under orthogonal transformations.This characterization supports the optimization analysis for the projection matrix.
  • Matrix analysis: A curvature lemma provides a lower bound as a matrix moves away from the leading singular-vector maximizer.The bound relies on separation δ between the first and second singular values.
  • Matrix analysis: Proposition 14 controls errors in estimated leading singular vectors when the perturbation is bounded entrywise and the singular-value gap is positive.The result applies under structural conditions involving sparse leading singular vectors and a feasible matrix set.
  • CUSUM control: Bounds on the CUSUM mean profile quantify its norms and its decay away from the true changepoint.The profile is parameterized by τ = n^-1 min(z, n − z), and its maximum occurs at t = z.
  • Probabilistic control: Probability lemmas control Gaussian noise maxima and the decay of univariate CUSUM statistics from their peaks.The auxiliary arguments use Gaussian tail bounds, martingale inequalities, Brownian bridges, and Ornstein–Uhlenbeck processes.
  • Dependence: The final auxiliary results support theoretical guarantees for a modified inspect algorithm under spatial dependence.They include perturbation bounds involving operator-norm error, singular-vector angle, and the smallest singular value.
Loading 1606.06246v2…