PaperlayerView exact revision on arXiv

Source-linked AI summary

Changepoint detection for high-dimensional time series with missing data

Yao Xie, Jiaji Huang, Rebecca Willett

arXiv:1208.5062v3stat.MLcs.LG

TL;DR

High-dimensional, incomplete data make conventional change-point detection difficult because accurate distribution estimation is challenging. This paper tracks a time-varying low-dimensional manifold and detects changes through its residuals; its experiments report more effective solar-flare detection than single-subspace tracking, with residuals stable before the change.

  • Problem

    Conventional change-point methods struggle with high-dimensional data and missing observations, where estimating the underlying distribution is difficult.

    Source: §I · p. 1

  • Method

    MOUSSE tracks a changing low-dimensional submanifold online and applies sequential change-point detection to residuals, including with missing data.

    Source: §I · p. 1, C. Contributions and paper organization · p. 2, C. MOUSSE Algorithm · p. 5

  • Results

    In solar-flare detection, MOUSSE detected and localized flares more effectively than single-subspace tracking, with more stable pre-change residuals.

    Source: 1) Solar flare detection · p. 11

  • Takeaways & Limitations

    The approach combines parsimonious multiscale manifold tracking with residual-based detection for high-dimensional streams that may contain missing elements.

    Source: §I · p. 1, §VII · p. 11

Abstract

from arXiv · show

This paper describes a novel approach to change-point detection when the observed high-dimensional data may have missing elements. The performance of classical methods for change-point detection typically scales poorly with the dimensionality of the data, so that a large number of observations are collected after the true change-point before it can be reliably detected. Furthermore, missing components in the observed data handicap conventional approaches. The proposed method addresses these challenges by modeling the dynamic distribution underlying the data as lying close to a time-varying low-dimensional submanifold embedded within the ambient observation space. Specifically, streaming data is used to track a submanifold approximation, measure deviations from this approximation, and calculate a series of statistics of the deviations for detecting when the underlying manifold has changed in a sharp or unexpected manner. The approach described in this paper leverages several recent results in the field of high-dimensional data analysis, including subspace tracking with missing data, multiscale analysis techniques for point clouds, online optimization, and change-point detection performance analysis. Simulations and experiments highlight the robustness and efficacy of the proposed approach in detecting an abrupt change in an otherwise slowly varying low-dimensional manifold.

I. INTRODUCTION

The paper targets online change-point detection in high-dimensional, potentially incomplete streams, where conventional methods struggle to estimate distributions. It proposes multiscale tracking of a changing low-dimensional manifold and uses its residuals for detection.

I. INTRODUCTION

  • Traditional quickest detection methods scale poorly to high-dimensional data because accurate distribution estimation becomes impractical, motivating low-dimensional statistics without restrictive modeling assumptions.The setting also includes partial observations and slowly varying manifolds.Source: §I · p. 1, §II · p. 3
  • MOUSSE uses multiscale online manifold learning to derive univariate detection statistics, including when observation vectors have missing elements.Its multiscale structure is intended to support fast, memory-efficient computation.Source: §I · p. 1

A. Related work

  • Prior manifold methods are often batch, while single-subspace trackers handle incomplete vectors but fit curved manifolds or unions of subsets poorly.GMRA likewise partitions point clouds and builds local low-rank approximations, but is a batch method without a straightforward online extension.Source: §I · p. 1, A. Related work · p. 2

B. Motivating applications

  • Motivating applications include detecting solar flares or surveillance anomalies, stolen-identity spending changes, and network attacks or failures.The paper describes these as settings where normal patterns may evolve while abrupt changes remain of interest.Source: B. Motivating applications · p. 2

C. Contributions and paper organization

  • The contributions are online tracking of a dynamic submanifold with missing data and residual-based sequential generalized likelihood ratio detection, supported by theory and experiments.The paper organizes these topics into problem formulation, tracking, detection, theoretical analysis, and numerical examples.Source: C. Contributions and paper organization · p. 2

II. PROBLEM FORMULATION

  • The problem formulation assumes noisy samples near a slowly varying low-dimensional submanifold, observes only known coordinates, and seeks residual changes after abrupt manifold shifts.Detection should be early after a change while avoiding false alarms for as long as possible when no change occurs.Source: §II · pp. 2–3

III. MULTISCALE ONLINE UNION OF SUBSETS ESTIMATION (MOUSSE)

MOUSSE approximates a changing submanifold with a tree-organized union of low-dimensional subsets. It uses an approximate Mahalanobis distance to assign new observations to subsets, including with missing data.

A. Multiscale union of subsets model

  • MOUSSE represents the submanifold as a tree-organized union of low-dimensional subsets, with leaf nodes supplying the approximation and tree size penalizing model complexity.Parent nodes provide coarser approximations covering the subsets represented by their children.Source: A. Multiscale union of subsets model · pp. 3–4

B. Approximate Mahalanobis distance

  • The approximate Mahalanobis distance combines Euclidean and Mahalanobis distance to give a finite measure for observations near, but not on, the piecewise-linear subsets.Its construction uses projected coordinates and residuals, with a low-rank covariance model and small eigenvalues approximated by δ.Source: B. Approximate Mahalanobis distance · pp. 4–5
  • MOUSSE uses scaled approximate Mahalanobis distance to select the closest subset, then derives a tracking residual from that match.The square root of the scaled distance is used so residuals can be modeled as Gaussian draws.Source: B. Approximate Mahalanobis distance · p. 5

C. MOUSSE Algorithm

Each MOUSSE update finds the closest subset, updates its local tracking state and nearby tree nodes, then adjusts tree complexity to balance fit and model size.

C. MOUSSE Algorithm

  • For each new sample, MOUSSE first finds the closest subset in the current approximation.The closest subset is identified using the distance defined for the model.Source: C. MOUSSE Algorithm · p. 5
  • It updates the closest subset, its ancestors, and its nearest virtual child using online parameter estimates.The updated parameters include the subspace basis, covariance shape, center, and residual-scale parameter.Source: C. MOUSSE Algorithm · p. 5
  • It grows or prunes the tree to balance approximation fit against model complexity.These steps form the third part of the stated update procedure.Source: C. MOUSSE Algorithm · p. 5

D. Update subset parameters

The update procedures favor the nearest subset and its local tree neighborhood, while adapting subspace parameters and tree structure to changing fit error.

D. Update subset parameters

  • Subset updates can scale step size inversely with approximate Mahalanobis distance; the described tracking variants update the basis before adjusting shape parameters.The text holds Λ fixed while updating U, then updates Λ and δ for fixed U.Source: D. Update subset parameters · pp. 5–6
  • The update-nearest approach updates the closest subset, its ancestors, and its virtual children, avoiding the higher computational cost of updating every subset.The update-all alternative remains possible, but the paper focuses on the greedy update-nearest approach.Source: D. Update subset parameters · pp. 5–6
  • Tree changes use average residual against a tolerance: split when a finer child improves penalized distance above tolerance, and merge when the residual is below tolerance and the parent improves it.The split and merge comparisons include a penalty weighted by the number of subsets.Source: D. Update subset parameters · pp. 5–6

1) GROUSE:

The online subspace updates adapt GROUSE and PETRELS to the multiscale subset model, with orthogonality and computational cost shaping the PETRELS variants.

1) GROUSE:

  • GROUSE updates the subspace by stepping along the instantaneous gradient of its cost function, with a step-size scaled by the new sample’s norm.The cost update focuses on the subspace while holding shape parameters fixed.Source: 1) GROUSE · p. 6

2) PETRELS:

  • PETRELS recursively updates the closest subset’s subspace using data assigned to that subset, while holding its shape parameters fixed.The update is obtained by minimizing the cost with respect to U for fixed Λ.Source: 2) PETRELS · p. 6
  • PETRELS-GS restores orthogonality at O(Dd^2) cost but may disrupt subspace continuity; PETRELS-FO preserves continuity with O(Dd) cost.GROUSE also has O(Dd) complexity for complete-data updates.Source: 2) PETRELS · p. 6, 3) Computational complexity · p. 6

3) Computational complexity:

The method adapts its tree to balance approximation fit and complexity, initializes that tree from training data, and applies a GLR test to streaming residuals with an ARL-based threshold.

E. Tree structure update

  • Tree splitting increases approximation resolution but complexity, while merging lowers both; decisions use average residuals plus a penalty proportional to the number of subsets.The tree is adapted when changing curvature is not captured by current subset approximations.Source: E. Tree structure update · p. 7

F. Initialization

  • Initialization recursively bisects training data with k-means until leaf residuals fall below ε, then adds one level of virtual children.Each node’s initial subspace parameters come from the largest covariance eigenvectors and eigenvalues.Source: F. Initialization · p. 7

G. Choice of parameters

  • The forgetting weight α is smaller for rapidly changing manifolds and larger for slowly evolving ones; experiments use α from 0.8 to 0.95.ε depends on manifold smoothness and noise variance, and μ is usually set close to ε.Source: G. Choice of parameters · p. 7

IV. CHANGE-POINT DETECTION

  • When the manifold changes abruptly, bounded small updates and one-level tree changes make MOUSSE lose track, sharply increasing its residuals for detection.During slow variation, the residuals are stationary.Source: §IV · p. 7

A. Generalized likelihood ratio (GLR) procedure

  • The GLR test treats the pre-change residual mean and variance as known but estimates the unknown post-change mean, stopping when its statistic reaches threshold b.It uses the most recent w residuals, and b controls the false-alarm rate through the average run length.Source: A. Generalized likelihood ratio (GLR)… · pp. 7–8

B. Choice of threshold for change-point detection

  • The Gaussian-based asymptotic ARL approximation is reported to remain accurate at finite thresholds and for non-Gaussian residuals, enabling threshold selection for a target ARL without parameter tuning.ARL is the expected time to a false detection when there is no change.Source: B. Choice of threshold for… · p. 8

C. Distribution of et

The paper examines the residual distribution and theoretical properties of MOUSSE, including missing-data projections, then presents numerical examples of tracking and change detection.

C. Distribution of et

  • For D = 100, the residual Q-Q plot supports a Gaussian approximation, which the authors also report yields an accurate theoretical ARL approximation.The ARL approximation is reported as accurate even when residuals are not exactly Gaussian.Source: C. Distribution of et · p. 8, Figure 3 · p. 8

V. PERFORMANCE ANALYSIS

  • A complete convergence proof for MOUSSE, GROUSE, or PETRELS is challenging because the submanifold-approximation space is non-convex.Source: §V · p. 8

A. MOUSSE residuals

  • Prior GMRA approximation results suggest that smooth-submanifold data can be accurately represented by a small number of MOUSSE leaf nodes.The suggested number depends on submanifold curvature.Source: A. MOUSSE residuals · p. 8

B. Optimality and consistency

C. Missing data

  • With a not-large missing-data fraction, MOUSSE’s missing-data projections are close to complete-data projections; accurate β estimation requires |Ω| on the order of max(d log d, D/log(D)).The stated error bound includes a term proportional to distance from the subspace and another due to noise.Source: C. Missing data · pp. 8–9

VI. NUMERICAL EXAMPLES

  • The numerical examples include simulated and real data to demonstrate submanifold tracking and change-point detection, and assess the theoretical ARL approximation.Source: §VI · p. 9

A. Comparison of tracking algorithms

PETRELS-FO is selected for subsequent MOUSSE experiments after outperforming the other tracking algorithms in the comparison. MOUSSE tracks static and slowly varying submanifolds, while its tracking errors increase when the assumed intrinsic dimension is too small.

A. Comparison of tracking algorithms

  • PETRELS-FO performs far better than PETRELS-GS and slightly better than GROUSE, especially with a large fraction of missing data.Its lower computational cost and easier parameter tuning motivate its use in the remaining experiments.Source: A. Comparison of tracking algorithms · p. 9, Figure 4 · p. 9

B. Tracking a static submanifold

C. Tracking a slowly time-varying submanifold

  • As the slowly varying manifold’s curvature changes, MOUSSE adjusts its subset count while maintaining a stable number of leaf nodes and meeting the target residual tolerance ε.Figure 6 shows the number of subsets and residuals over time.Source: C. Tracking a slowly time-varying… · p. 10, Figure 6 · p. 10

D. Choice of intrinsic dimension d

  • MOUSSE tracks well when the assumed intrinsic dimension is at least the true dimension; choosing it too small significantly increases errors and requires a larger tolerance ε.The experiment’s true intrinsic dimension is 2, with MOUSSE tested using d = 1, 2, and 3.Source: D. Choice of intrinsic dimension d · p. 10, Figure 7 · p. 10

E. Change-point detection using MOUSSE

MOUSSE-based GLR detection has shorter expected delays than single-subspace tracking in simulations, and the paper reports detections on solar-flare and transaction data. The conclusion describes its multiscale tracking approach and identifies extensions as open problems.

1) Approximation to ARL:

  • Theoretical and Monte Carlo thresholds for the GLR procedure are reported to be very close for the tested average run lengths.The theoretical approximation assumes Gaussian residuals, while the simulated MOUSSE residuals are described as close to Gaussian.Source: 1) Approximation to ARL · p. 10

2) Comparison of tracking algorithms for MOUSSE:

  • MOUSSE-based change-point detection has much smaller expected detection delays than single-subspace tracking for both tested change magnitudes.The comparison uses Δγ = 0.05 and 0.03, with delays estimated over 10,000 Monte Carlo trials.Source: 2) Comparison of tracking algorithms… · p. 11

1) Solar flare detection:

  • On solar data with 67,744 dimensions, MOUSSE detects and localizes a transient flare more effectively than single-subspace tracking, even with d = 1.With K_t around 10, its residuals are more stable before the change and change significantly when it occurs.Source: 1) Solar flare detection · p. 11

2) Identity theft detection:

  • For one transaction history, the GLR signals an isolated outlier at t = 38 and crosses its threshold at t = 72 as labels change from good to bad near t = 70.After each detection, the GLR is reset, allowing repeated detections of changes in the residual statistics.Source: 2) Identity theft detection · p. 11, Figure 9 · p. 12

VII. CONCLUSIONS

  • The conclusion describes multiscale online tracking of high-dimensional data near a low-dimensional submanifold, using residuals for fast, robust change-point detection.The multiscale structure supports fast updates and flexible piecewise-linear approximations; potential applications include remote sensing, credit monitoring, and network traffic analysis.Source: §VII · p. 11
  • The current algorithm focuses on unions of subsets; sparse covariance selection and non-Gaussian models, inverse problems, and dynamical models remain open problems.The authors also identify mixture tracking and alternative detection statistics as future directions.Source: §VII · pp. 11–12

APPENDIX A OPTIMALITY OF ESTIMATE FOR c

The appendix analyzes an online estimate of c in the complete-data, single-subspace setting and states its asymptotic optimality and unbiasedness under specified conditions.

APPENDIX A OPTIMALITY OF ESTIMATE FOR c

  • The online update c_{t+1} = αc_t + (1 − α)x_t yields c_t = the cost-minimizing estimate in the stated single-subspace, complete-data setting.The derivation identifies the cost-minimizing c at time t as the online estimate of the data mean.Source: Appendix A · p. 12
  • With bounded initialization and 0 ≤ α < 1, the online estimate c_t converges in probability to the minimizer of the stated cost; for i.i.d. samples with mean c⋆, it is asymptotically unbiased.The derivation considers complete data and a single subspace; the covariance is assumed to have low-rank structure.Source: Appendix A · p. 12

APPENDIX B CONSISTENCY OF ESTIMATES OF Λ⋆AND δ⋆

The supplied appendix passage specifies the setting for its projection-estimator result but does not give the full result.

APPENDIX B CONSISTENCY OF ESTIMATES OF Λ⋆AND δ⋆

  • The projection-estimator analysis assumes complete data, a single subspace, and the correct basis U = U⋆.The passage identifies the projection as an unbiased estimator but truncates before specifying what it estimates.Source: Appendix B · p. 12

APPENDIX C PROOF OF THEOREM 1

The proof separates the observed deviation into subspace and orthogonal components, then bounds contributions from sampling and noise under stated conditions.

APPENDIX C PROOF OF THEOREM 1

  • The proof decomposes v_Ω − c_Ω into projected and orthogonal components and bounds them separately.The components are p_Ω = P_Ωp and q_Ω = P_Ωq, where p lies in S and q in S⊥.Source: Appendix C · p. 13
  • Using Markov’s inequality, the noise-power tail is bounded when τ > D/[(1−ℓ)|Ω|]; combining this noise bound with (51) gives the statement in Theorem 1 with probability 1−2ε.Source: Appendix C · p. 13

Related papers

Loading 1208.5062v3…