Wild binary segmentation for multiple change-point detection

Abstract

We propose a new technique, called wild binary segmentation (WBS), for consistent estimation of the number and locations of multiple change-points in data. We assume that the number of change-points can increase to infinity with the sample size. Due to a certain random localisation mechanism, WBS works even for very short spacings between the change-points and/or very small jump magnitudes, unlike standard binary segmentation. On the other hand, despite its use of localisation, WBS does not require the choice of a window or span parameter, and does not lead to a significant increase in computational complexity. WBS is also easy to code. We propose two stopping criteria for WBS: one based on thresholding and the other based on what we term the `strengthened Schwarz information criterion'. We provide default recommended values of the parameters of the procedure and show that it offers very good practical performance in comparison with the state of the art. The WBS methodology is implemented in the R package wbs, available on CRAN. In addition, we provide a new proof of consistency of binary segmentation with improved rates of convergence, as well as a corresponding result for WBS.

Published in at http://dx.doi.org/10.1214/14-AOS1245 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (17)

• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Optimal detection of changepoints with a linear computational cost
• Wild binary segmentation for multiple change-point detection
• An Algorithm for Optimal Partitioning of Data on an Interval
• Properties and refinements of the fused lasso
• Consistencies and rates of convergence of jump-penalized least squares estimators
• Multiscale and multilevel technique for consistent segmentation of nonstationary time series
• Multiscale interpretation of taut string estimation and its connection to Unbalanced Haar wavelets

Cited by in corpus (47)

• Selective review of offline change point detection methods
• Wild binary segmentation for multiple change-point detection
• Multiple-change-point detection for high dimensional time series via sparsified binary segmentation
• Change-point detection in panel data via double CUSUM statistic
• Simultaneous multiple change-point and factor analysis for high-dimensional time series
• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
• The first six months of the Advanced LIGO's and Advanced Virgo's third observing run with GRANDMA
• Detecting multiple generalized change-points by isolating single ones
• FDR-Control in Multiscale Change-point Segmentation
• Finite sample change point inference and identification for high-dimensional mean vectors
• Automatic Change-Point Detection in Time Series via Deep Learning
• Oracle Estimation of a Change Point in High Dimensional Quantile Regression
• High-Dimensional Changepoint Detection via a Geometrically Inspired Mapping
• A Note on Kernel Methods for Multiscale Systems with Critical Transitions
• WATCH: Wasserstein Change Point Detection for High-Dimensional Time Series Data
• Multiscale Change-point Segmentation: Beyond Step Functions
• Change Point Detection for Nonparametric Regression under Strongly Mixing Process
• Detecting Multiple Change Points Using Adaptive Regression Splines with Application to Neural Recordings
• Online Neural Networks for Change-Point Detection
• Bayesian detection of piecewise linear trends in replicated time-series with application to growth data modelling
• Unsupervised Detection of Behavioural Drifts with Dynamic Clustering and Trajectory Analysis
• A test for second-order stationarity of time series based on unsystematic sub-samples
• Robust multiscale estimation of time-average variance for time series segmentation
• Multi-scale detection of rate changes in spike trains with weak dependencies
• Latent Neural Stochastic Differential Equations for Change Point Detection
• Selective linear segmentation for detecting relevant parameter changes
• Estimation of dynamic networks for high-dimensional nonstationary time series
• Smoothing splines for discontinuous signals
• Nonparametric data segmentation in multivariate time series via joint characteristic functions
• Structural Change in (Economic) Time Series
• Change point detection in high dimensional data with U-statistics
• SSAAM: Sentiment Signal-based Asset Allocation Method with Causality Information
• Automatic detection of long-duration transients in Fermi-GBM data
• Detection and inference of changes in high-dimensional linear regression with non-sparse structures
• Detection of gamma-ray transients with wild binary segmentation
• High-pass Filter Periodogram: An Improved Power Spectral Density Estimator for Unevenly Sampled Data
• Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise
• Improving Power by Conditioning on Less in Post-selection Inference for Changepoints
• Change-Point Detection for Object-valued Time Series
• Data-adaptive structural change-point detection via isolation
• Degrees-of-freedom penalized piecewise regression
• Spectral Change Point Estimation for High Dimensional Time Series by Sparse Tensor Decomposition
• Likelihood-based Inference for Random Networks with Changepoints
• Asymptotic Distribution-free Change-point Detection for Modern Data Based on a New Ranking Scheme
• Testing for jumps in processes with integral fractional part and jump-robust inference on the Hurst exponent
• Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry
• Quantifying uncertainty in spikes estimated from calcium imaging data