Narrowest-Over-Threshold Detection of Multiple Change-points and Change-point-like Features
arXiv:1609.00293 · doi:10.1111/rssb.12322
Abstract
We propose a new, generic and flexible methodology for nonparametric function estimation, in which we first estimate the number and locations of any features that may be present in the function, and then estimate the function parametrically between each pair of neighbouring detected features. Examples of features handled by our methodology include change-points in the piecewise-constant signal model, kinks in the piecewise-linear signal model, and other similar irregularities, which we also refer to as generalised change-points. Our methodology works with only minor modifications across a range of generalised change-point scenarios, and we achieve such a high degree of generality by proposing and using a new multiple generalised change-point detection device, termed Narrowest-Over-Threshold (NOT). The key ingredient of NOT is its focus on the smallest local sections of the data on which the existence of a feature is suspected. Crucially, this adaptive localisation technique prevents NOT from considering subsamples containing two or more features, a key factor that ensures the general applicability of NOT. For selected scenarios, we show the consistency and near-optimality of NOT in detecting the number and locations of generalised change-points. Furthermore, we propose to select NOT's threshold (automatically) via the strengthened Schwarz Information Criterion (sSIC) and give theoretical justifications. The NOT estimators are easy to implement and rapid to compute: the entire threshold-indexed solution path can be computed in close-to-linear time. Importantly, the NOT approach is easy to extend by the user to tailor to their own needs. There is no single competitor, but we show that the performance of NOT matches or surpasses the state of the art in the scenarios tested. Our methodology is implemented in the R package \textbf{not}.
arXiv comment62 pages, 10 figures, 8 tables
References in corpus (6)
- Optimal detection of changepoints with a linear computational cost
- Nonparametric maximum likelihood approach to multiple change-point problems
- A pruned dynamic programming algorithm to recover the best segmentations with to change-points
- Change Points via Probabilistically Pruned Objectives
- Detecting changes in slope with an penalty
- Nuisance Parameters Free Changepoint Detection in Non-stationary Series
Cited by in corpus (28)
- Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
- Detecting multiple generalized change-points by isolating single ones
- Automatic Change-Point Detection in Time Series via Deep Learning
- Optimal Change Point Detection and Localization in Sparse Dynamic Networks
- Time Series Analysis of COVID-19 Infection Curve: A Change-Point Perspective
- A review on minimax rates in change point detection and localisation
- Univariate Mean Change Point Detection: Penalization, CUSUM and Optimality
- Robust multiscale estimation of time-average variance for time series segmentation
- Smoothing splines for discontinuous signals
- Hybrid Modeling of Regional COVID-19 Transmission Dynamics in the U.S
- Multiscale Autoregression on Adaptively Detected Timescales
- Trend and Variance Adaptive Bayesian Changepoint Analysis & Local Outlier Scoring
- Consistency of a range of penalised cost approaches for detecting multiple changepoints
- Valid Post-Detection Inference for Change Points Identified Using Trend Filtering
- On a phase transition in general order spline regression
- Detection and inference of changes in high-dimensional linear regression with non-sparse structures
- Seeded intervals and noise level estimation in change point detection: A discussion of Fryzlewicz (2020)
- Improving Power by Conditioning on Less in Post-selection Inference for Changepoints
- Detection and Estimation of Local Signals
- On detecting weak changes in the mean of CHARN models
- Data-adaptive structural change-point detection via isolation
- Degrees-of-freedom penalized piecewise regression
- Short Communication: Detecting Possibly Frequent Change-points: Wild Binary Segmentation 2
- Optimal Change-Point Detection with Training Sequences in the Large and Moderate Deviations Regimes
- Detecting linear trend changes in data sequences
- Discussion of 'Detecting possibly frequent change-points: Wild Binary Segmentation 2 and steepest-drop model selection'
- Change-in-Slope Optimal Partitioning Algorithm in a Finite-Size Parameter Space
- A distribution free test for changes in the trend function of locally stationary processes