Optimal detection of changepoints with a linear computational cost

Abstract

We consider the problem of detecting multiple changepoints in large data sets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example in genetics as we analyse larger regions of the genome, or in finance as we observe time-series over longer periods. We consider the common approach of detecting changepoints through minimising a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalised likelihood and minimum description length. We introduce a new method for finding the minimum of such cost functions and hence the optimal number and location of changepoints that has a computational cost which, under mild conditions, is linear in the number of observations. This compares favourably with existing methods for the same problem whose computational cost can be quadratic or even cubic. In simulation studies we show that our new method can be orders of magnitude faster than these alternative exact methods. We also compare with the Binary Segmentation algorithm for identifying changepoints, showing that the exactness of our approach can lead to substantial improvements in the accuracy of the inferred segmentation of the data.

25 pages, 4 figures, To appear in Journal of the American Statistical Association

Cited by in corpus (186)

• Selective review of offline change point detection methods
• Wild binary segmentation for multiple change-point detection
• Weak SINDy For Partial Differential Equations
• What is Gab? A Bastion of Free Speech or an Alt-Right Echo Chamber?
• Narrowest-Over-Threshold Detection of Multiple Change-points and Change-point-like Features
• A Kernel Multiple Change-point Algorithm via Model Selection
• Nonparametric maximum likelihood approach to multiple change-point problems
• A Survey on Concept Drift in Process Mining
• Jump-sparse and sparse recovery using Potts functionals
• Virtual Machine Warmup Blows Hot and Cold
• Forecasting asylum-related migration flows with machine learning and data at scale
• Privacy Policies over Time: Curation and Analysis of a Million-Document Dataset
• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
• Model selection for hybrid dynamical systems via sparse regression
• SiFall: Practical Online Fall Detection with RF Sensing
• An atomic Boltzmann machine capable of on-chip learning
• Visual Drift Detection for Sequence Data Analysis of Business Processes
• Characterization of anomalous diffusion classical statistics powered by deep learning (CONDOR)
• Detecting multiple generalized change-points by isolating single ones
• FDR-Control in Multiscale Change-point Segmentation
• A Class of Nonconvex Penalties Preserving Overall Convexity in Optimization-Based Mean Filtering
• ClaSP -- Parameter-free Time Series Segmentation
• Mobility patterns of the Portuguese population during the COVID-19 pandemic
• Automatic Change-Point Detection in Time Series via Deep Learning
• An Iterative 5G Positioning and Synchronization Algorithm in NLOS Environments with Multi-Bounce Paths
• Towards effective assessment of steady state performance in Java software: Are we there yet?
• Healthcare Cost Prediction: Leveraging Fine-grain Temporal Patterns
• Computationally efficient change point detection for high-dimensional regression
• High-Dimensional Changepoint Detection via a Geometrically Inspired Mapping
• Time Series Segmentation through Automatic Feature Learning
• Large-Margin Metric Learning for Partitioning Problems
• Changepoint Detection: An Analysis of the Central England Temperature Series
• Optimal Covariance Change Point Localization in High Dimension
• The use of scaling properties to detect relevant changes in financial time series: a new visual warning tool
• Mumford-Shah and Potts Regularization for Manifold-Valued Data with Applications to DTI and Q-Ball Imaging
• Efficient penalty search for multiple changepoint problems
• WATCH: Wasserstein Change Point Detection for High-Dimensional Time Series Data
• Changepoint analysis of historical battle deaths
• A linear time method for the detection of point and collective anomalies
• Optimal nonparametric change point detection and localization
• Bayesian Detection of Image Boundaries
• Multiscale Change-point Segmentation: Beyond Step Functions
• ruptures: change point detection in Python
• Localizing Changes in High-Dimensional Vector Autoregressive Processes
• Multiple abrupt phase transitions in urban transport congestion
• Label-free detection of single nanoparticles with disordered nanoisland surface plasmon sensor
• The Devil Is in the Details: An Efficient Convolutional Neural Network for Transport Mode Detection
• Automated Issue Assignment: Results and Insights from an Industrial Case
• Predicting Covid-19 EMS Incidents from Daily Hospitalization Trends
• A robust approach for estimating change-points in the mean of an AR(1) process
• Multi-sequence segmentation via score and higher-criticism tests
• A log-linear time algorithm for constrained changepoint detection
• The Essential Histogram
• Computing Valid p-value for Optimal Changepoint by Selective Inference using Dynamic Programming
• Moderating New Waves of Online Hate with Chain-of-Thought Reasoning in Large Language Models
• AI-driven Java Performance Testing: Balancing Result Quality with Testing Time
• Change Point Detection for Nonparametric Regression under Strongly Mixing Process
• Data segmentation algorithms: Univariate mean change and beyond
• Multiple Change-point Detection: a Selective Overview
• Online Neural Networks for Change-Point Detection
• Statistical Inference in Hidden Markov Models using $k$-segment Constraints
• Multiple Changepoint Estimation in High-Dimensional Gaussian Graphical Models
• A review on minimax rates in change point detection and localisation
• A deep X-ray view of the Class I YSO Elias 29 with XMM-Newton and NuSTAR
• Smoothing for signals with discontinuities using higher order Mumford-Shah models
• Bayesian detection of piecewise linear trends in replicated time-series with application to growth data modelling
• Modelling Time-Varying First and Second-Order Structure of Time Series via Wavelets and Differencing
• Unsupervised Detection of Behavioural Drifts with Dynamic Clustering and Trajectory Analysis
• Against the Others! Detecting Moral Outrage inSocial Media Networks
• Univariate Mean Change Point Detection: Penalization, CUSUM and Optimality
• Online Structural Change-point Detection of High-dimensional Streaming Data via Dynamic Sparse Subspace Learning
• Localizing Changes in High-Dimensional Regression Models
• Spline Regression with Automatic Knot Selection
• A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data
• Fully Adaptive Time-Varying Wave-Shape Model: Applications in Biomedical Signal Processing
• A Bayesian binary algorithm for RMS-based acoustic signal segmentation
• Multiscale Jump Testing and Estimation Under Complex Temporal Dynamics
• Unsupervised non-parametric change point detection in quasi-periodic signals
• Intelligent sampling for multiple change-points in exceedingly long time series with rate guarantees
• Sequential change point tests based on U-statistics
• InDiD: Instant Disorder Detection via Representation Learning
• Multiple Testing of Local Extrema for Detection of Change Points
• Change Points via Probabilistically Pruned Objectives
• From BGP to RTT and Beyond: Matching BGP Routing Changes and Network Delay Variations with an Eye on Traceroute Paths
• A computationally efficient nonparametric approach for changepoint detection
• Effect of COVID-19 on noise pollution change in Dublin, Ireland
• Nonparametric data segmentation in multivariate time series via joint characteristic functions
• Selective linear segmentation for detecting relevant parameter changes
• Latent Neural Stochastic Differential Equations for Change Point Detection
• anomaly : Detection of Anomalous Structure in Time Series Data
• Unveiling the Face-Dependent Ice Growth Kinetics: Insights from Molecular Dynamics on the Basal and Prism Surfaces
• Smoothing splines for discontinuous signals
• Trend and Variance Adaptive Bayesian Changepoint Analysis & Local Outlier Scoring
• Comprehensive Process Drift Detection with Visual Analytics
• Pesticide concentration monitoring: investigating spatio-temporal patterns in left censored data
• Pruning and Nonparametric Multiple Change Point Detection
• Detection of Pedestrian Turning Motions to Enhance Indoor Map Matching Performance
• INTEGRAL/SPI data segmentation to retrieve source intensity variations
• Detecting changes in slope with an $L_0$ penalty
• Tree-Cut for Probabilistic Image Segmentation
• Automatic detection of long-duration transients in Fermi-GBM data
• Efficacy of Statistical and Artificial Intelligence-based False Information Cyberattack Detection Models for Connected Vehicles
• High-pass Filter Periodogram: An Improved Power Spectral Density Estimator for Unevenly Sampled Data
• Moving sum data segmentation for stochastics processes based on invariance
• Autocovariance estimation in regression with a discontinuous signal and $m$-dependent errors: A difference-based approach
• Detection of gamma-ray transients with wild binary segmentation
• Multiple Changepoint Detection with Partial Information on Changepoint Times
• On a phase transition in general order spline regression
• Inference for Multiple Change-points in Linear and Non-linear Time Series Models
• Linear time dynamic programming for the exact path of optimal models selected from a finite set
• Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise
• Enhancing Forecasting Accuracy in Dynamic Environments via PELT-Driven Drift Detection and Model Adaptation
• Forecasting and Event Detection in Internet Resource Dynamics using Time Series Models
• Geometric-Based Pruning Rules For Change Point Detection in Multiple Independent Time Series
• Seeded intervals and noise level estimation in change point detection: A discussion of Fryzlewicz (2020)
• Penalty Learning for Optimal Partitioning using Multilayer Perceptron
• One Video to Steal Them All: 3D-Printing IP Theft through Optical Side-Channels
• Improving Power by Conditioning on Less in Post-selection Inference for Changepoints
• Scalable Bayesian change point detection with spike and slab priors
• Estimation of VaR with jump process: application in corn and soybean markets
• What is the Fourier Transform of a Spatial Point Process?
• Degrees-of-freedom penalized piecewise regression
• Multiple change-point detection for Poisson point processes
• A Kernel-Based Approach for Accurate Steady-State Detection in Performance Time Series
• Noise-robust multi-fidelity surrogate modelling for parametric partial differential equations
• Jump Interval-Learning for Individualized Decision Making
• MT4G: A Tool for Reliable Auto-Discovery of NVIDIA and AMD GPU Compute and Memory Topologies
• Multiple Change Point Detection in Structured VAR Models: the VARDetect R Package
• Emulating complex dynamical simulators with random Fourier features
• Inference in generalized bilinear models
• Estimation of high-dimensional change-points under a group sparsity structure
• A computationally efficient, high-dimensional multiple changepoint procedure with application to global terrorism incidence
• Sequential (Quickest) Change Detection: Classical Results and New Directions
• Bayesian Changepoint Analysis
• Elites Tweet? Characterizing the Twitter Verified User Network
• Change Surfaces for Expressive Multidimensional Changepoints and Counterfactual Prediction
• Parallelisation of a Common Changepoint Detection Method
• On Optimal Multiple Changepoint Algorithms for Large Data
• Towards Understanding the Information Ecosystem Through the Lens of Multiple Web Communities
• Detecting multiple change points: a PULSE criterion
• Detecting Changes in Time Series Data using Volatility Filters
• Estimation of multiple change points under a generalised Ornstein-Uhlenbeck framework
• New efficient algorithms for multiple change-point detection with kernels
• Statistical Modelling of Computer Network Traffic Event Times
• Dynamic Networks with Multi-scale Temporal Structure
• Empirical Bayesian analysis of simultaneous changepoints in multiple data sequences
• Non-parametric change-point detection using string matching algorithms
• Data-adaptive structural change-point detection via isolation
• A breakpoint detection in the mean model with heterogeneous variance on fixed time-intervals
• Real-time on-device nod and shake recognition
• Change Point Detection by Cross-Entropy Maximization
• Detecting unusual trading patterns on cryptocurrency exchanges by means of complexity measures
• Process Knowledge Driven Change Point Detection for Automated Calibration of Discrete Event Simulation Models Using Machine Learning
• Screening and merging algorithm for the detection of copy-number alterations
• Differentiable Segmentation of Sequences
• On Posterior consistency of Bayesian Changepoint models
• Lagged Exact Bayesian Online Changepoint Detection with Parameter Estimation
• Nonparametric Detection of Multiple Location-Scale Change Points via Wild Binary Segmentation
• Supplementary Notes: Segment Parameter Labelling in MCMC Change Detection
• A Generic Algorithm for Sleep-Wake Cycle Detection using Unlabeled Actigraphy Data
• A novel regularized approach for functional data clustering: An application to milking kinetics in dairy goats
• One-to-One Matching of RTT and Path Changes
• Determination of a structural break in a mean-reverting process
• Coupled Supply and Demand Forecasting in Platform Accommodation Markets
• Detecting Change Signs with Differential MDL Change Statistics for COVID-19 Pandemic Analysis
• Most recent changepoint detection in Panel data
• Changepoint Analysis of Topic Proportions in Temporal Text Data
• Multi-regime analysis for computer vision-based traffic surveillance using a change-point detection algorithm
• Tracing the impacts of Mount Pinatubo eruption on regional climate using spatially-varying changepoint detection
• Fast high-fidelity baseband reset of a latched state for quantum dot qubit readout
• Evaluation of time series models under non-stationarity with application to the comparison of regional climate models
• Ms.FPOP: An Exact and Fast Segmentation Algorithm With a Multiscale Penalty
• A Non-Iterative Quantile Change Detection Method in Mixture Model with Heavy-Tailed Components
• Scalable Bayesian Multiple Changepoint Detection via Auxiliary Uniformization
• Probabilistic sequential matrix factorization
• Tree-Projected Gradient Descent for Estimating Gradient-Sparse Parameters on Graphs
• Nonparametric Multiple Change Point Detection for Non-Stationary Times Series
• A new segmentation method for the homogenisation of GNSS-derived IWV time-series
• Modeling a Nonlinear Biophysical Trend Followed by Long-Memory Equilibrium with Unknown Change Point
• Predictive maintenance on event logs: Application on an ATM fleet
• Castor: Contextual IoT Time Series Data and Model Management at Scale
• Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry
• Change-in-Slope Optimal Partitioning Algorithm in a Finite-Size Parameter Space
• Time-varying ${\ell }_0$ optimization for Spike Inference from Multi-Trial Calcium Recordings
• Trends of continental, zonal and seasonal land temperatures in the 20th century
• Adversarially robust change point detection