Changepoint detection for high-dimensional time series with missing data

Abstract

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.

References in corpus (6)

• PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations
• Rodeo: Sparse, greedy nonparametric regression
• Anomaly Detection in Time Series of Graphs using Fusion of Graph Invariants
• Manifold-Based Signal Recovery and Parameter Estimation from Compressive Measurements
• Tangent-based manifold approximation with locally linear models
• Nearly Optimal Change-Point Detection with an Application to Cybersecurity

Cited by in corpus (19)

• Real-Time Nonparametric Anomaly Detection in High-Dimensional Settings
• Poisson Matrix Recovery and Completion
• Multi-Sensor Sequential Change Detection with Unknown Change Propagation Pattern
• Two-sample Test using Projected Wasserstein Distance
• The Role of Principal Angles in Subspace Classification
• Scalable SUM-Shrinkage Schemes for Distributed Monitoring Large-Scale Data Streams
• Maximum entropy low-rank matrix recovery
• Change Points via Probabilistically Pruned Objectives
• Change-Point Detection in Dynamic Networks with Missing Links
• Detecting and Adapting to Irregular Distribution Shifts in Bayesian Online Learning
• Low-Rank Methods in Event Detection and Subsampled Point-to-Subspace Proximity Tests
• Online Subspace Tracking for Damage Propagation Modeling and Predictive Analytics: Big Data Perspective
• Personalized Tucker Decomposition: Modeling Commonality and Peculiarity on Tensor Data
• Sequential (Quickest) Change Detection: Classical Results and New Directions
• Subspace Change-Point Detection via Low-Rank Matrix Factorisation
• Online network change point detection with missing values and temporal dependence
• Bayesian Methods for Multiple Change-Point Detection with Reduced Communication
• Online High-Dimensional Change-Point Detection using Topological Data Analysis
• Fast Algorithm for Low-rank matrix recovery in Poisson noise