PaperlayerView exact revision on arXiv

Source-linked AI summary

Narrowest-Over-Threshold Detection of Multiple Change-points and Change-point-like Features

Rafal Baranowski, Yining Chen, Piotr Fryzlewicz

arXiv:1609.00293v2stat.ME

TL;DR

The paper addresses detection of unknown numbers and locations of generalised change-points and related features. It proposes NOT, which searches threshold-exceeding random subsamples and selects the narrowest interval, then supports parametric estimation between detected features. NOT is theoretically consistent in selected scenarios, computationally efficient, and competitive across simulated settings, while extensions beyond the univariate mean and first two moments remain outside the main scope.

  • Problem

    The paper addresses detecting unknown numbers and locations of features such as jumps, kinks, and changes in noise variance in signals with limited general methods beyond canonical change-points.

  • Method

    NOT applies likelihood-derived contrasts to random subsamples, retains threshold-exceeding intervals, and selects the narrowest retained interval to isolate at most one feature.

  • Results

    NOT is consistent in selected theoretical scenarios and is among the most competitive methods for estimating change-point numbers, locations, and signals in most simulations.

  • Takeaways & Limitations

    NOT provides a fast, flexible framework for feature detection and interpretable signal estimation that users can extend with specialised contrasts.

  • Takeaways & Limitations

    The main scenarios focus on univariate changes in the mean or first two moments, while dependent-noise use poses residual and variance-estimation challenges.

Abstract

from arXiv · show

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}.

1 Introduction

The paper introduces NOT, a generic framework for detecting unknown numbers and locations of signal features, then estimating the signal parametrically between detected features. Its narrowest-interval strategy addresses failures of fitting one-feature models over regions containing multiple generalised change-points.

  • Problem: The paper targets features at unknown locations, including piecewise-constant change-points, piecewise-linear derivative change-points, and discontinuities in piecewise-linear signals.It also permits detection of changes in distributional aspects of the noise, such as variance.
  • Method: NOT combines global random subsampling with local selection of the narrowest interval whose feature contrast exceeds a threshold.A tailor-made likelihood-derived contrast identifies a likely feature on each retained interval.
  • Method: The narrowest-interval focus makes the selected interval likely to contain at most one feature, supporting use across multiple generalised change-point scenarios.This adaptive localisation avoids the multiple-feature approximation problem that affects broader intervals.
  • Contributions: The methodology is designed to be generic, computationally efficient, accurate, interpretable, and extensible through user-defined contrast functions.With M = O(log T) subsamples in general, the procedure has complexity O(MT), and the solution path can be computed efficiently.
  • Motivation: Fitting a single triangular change-point model over the full sample can place the estimated change-point between the true change-points, so least-squares searches on broad intervals can fail.The example has true change-points at t = 350 and t = 650 but estimates one at t = 500.
  • Contributions: The paper develops NOT for four structural-change scenarios, derives scenario-specific likelihood-based contrasts, and provides consistency and convergence-rate theory.The implementation is available in the R package not.

2 The framework of NOT

NOT models signals parametrically between unknown feature locations and detects those features by testing randomly drawn local subsamples. Its narrowest-over-threshold selection supports localisation across several structural scenarios, with theoretical consistency, near-optimal rates, and O(T log T) computation in key settings.

  • Model setup: The framework partitions the signal and noise structure into q+1 parametric segments separated by q unknown change-points, with q potentially growing with T.The framework covers constant-variance piecewise-constant, continuous piecewise-linear, discontinuous piecewise-linear, and piecewise-constant mean-and-variance scenarios.
  • Detection procedure: NOT repeatedly draws random subsamples, computes a generalised likelihood-ratio contrast for each possible single feature, and retains contrasts exceeding threshold ζT.The procedure uses M randomly drawn intervals and tailor-made contrasts derived from likelihood theory.
  • Detection procedure: Among significant intervals, NOT selects the shortest one, estimates the feature at its maximum contrast, and recursively searches the left and right subsegments.This narrowest-over-threshold rule focuses detection on local intervals rather than fitting a single feature over the entire sample.
  • Segment estimation: After feature detection, the signal on each segment can be estimated by standard methods such as least squares or maximum likelihood.The same framework can address spline-knot estimation by treating polynomial segments with higher-order derivative changes as a multiple change-point problem.
  • Theory and computation: With finitely many change-points and δT ∼ T, M = O(log T) random intervals yield consistent detection with total computational cost O(T log T).For Scenario (S1), the maximum localisation error is Op(log T), only a logarithmic factor from the minimax Op(1) rate.
  • Theory and computation: In the bounded-signal case of Scenario (S2), NOT achieves Op(T^(2/3)(log T)^(1/3)) localisation, improvable to Op(T^(1/2)(log T)^(1/2)) under additional restrictive assumptions.The first rate differs from Raimondo's Op(T^(2/3)) rate by only a logarithmic factor.

3 NOT with the strengthened Schwarz Information Criterion (sSIC)

The sSIC selects among NOT’s threshold-indexed candidate models, whose entire solution path can be computed efficiently. Under stated spacing and fixed-change-point conditions, the resulting procedure has theoretical guarantees and typically O(MT) computational complexity.

  • Threshold selection: Theoretical threshold guarantees depend on unobserved quantities, motivating data-driven selection from NOT’s threshold-indexed solution path.Each threshold yields a candidate model, so threshold selection is equivalent to model selection.
  • Solution path: The solution path changes only at discrete threshold values, and Algorithm 2 computes it iteratively without repeatedly rerunning Algorithm 1.This avoids naively scanning thresholds and reusing no information between similar candidate solutions.
  • sSIC selection: The sSIC selects the candidate model minimizing an information criterion based on estimated change-points and segment parameters.When α = 1, the criterion reduces to the Schwarz Information Criterion; other criteria could also be used after computing the path.
  • Theory: Under fixed q and spacings of order T, theoretical results establish properties for NOT with sSIC in Scenarios (S1) and (S2).The relevant results use α > 1 and scenario-specific contrast functions, with optimality of location rates discussed separately.
  • Computational complexity: The typical total computational complexity of Algorithms 1 and 2 is O(MT), because interval contrasts cost O(T) on average and the second stage is no larger.The interval calculations are independent and can be parallelized.
  • Computational complexity: Algorithm 2 has O(MT) memory complexity and can handle problems with T in the range of millions.In the reported implementation, execution times scale linearly with both T and M under i.i.d. standard normal data.

4 NOT with dependent or heavy-tailed noise

NOT remains theoretically consistent under stationary short-memory Gaussian noise and appears robust to Gaussian contrast misspecification under non-Gaussian noise. Dependent-noise applications nevertheless require estimating residual and noise-dependence quantities.

  • Dependent noise: NOT remains consistent in Scenarios (S1) and (S2) when i.i.d. Gaussian errors are replaced by stationary short-memory Gaussian processes.The conclusions of Theorems 1 and 2 hold with different constants.
  • Dependent noise: For dependent noise, the smallest permitted threshold depends linearly on σ0(P∞k=−∞|ρk|)1/2.This quantity generalizes the independent-noise threshold proportional to σ0.
  • Practical challenges: Practical dependent-noise use requires pre-estimating residuals, σ0 when unknown, and σ0(P∞k=−∞|ρk|)1/2.The paper describes these estimation problems as difficult in time-series analysis and outlines possible solutions.
  • Heavy-tailed noise: NOT appears relatively robust to noise misspecification, offering reasonable estimates under non-Gaussian noise with Gaussian contrast functions.The paper separately discusses improving performance under heavy-tailed noise.
  • Heavy-tailed noise: A heavy-tailed-noise contrast assigns residuals to two labels, ±1, before applying the contrast function.The construction uses residuals from fitting a no-change-point curve on each interval and is motivated by the lighter tails of the two-point labels.

5 Simulation study

The simulation study evaluates NOT across multiple signal, variance, and noise settings, comparing change-point estimation, signal estimation, localisation accuracy, and computation against competing methods. NOT is generally competitive, fast in complex scenarios, and reasonably robust to noise misspecification, while model mismatch can affect selected change-point counts and accuracy.

  • 5.1 Settings: The study simulates signals M1–M7 under Gaussian, Laplace, Student-t5, and dependent Gaussian AR(1) noise settings.The Gaussian settings include i.i.d. N(0,1) and i.i.d. N(0,2), alongside heavier-tailed and dependent alternatives.
  • 5.2 Competitors: NOT is compared with CRAN implementations of competing methods, although no competitor applies across all Scenarios (S1)–(S5).The comparisons include methods for mean change-points, variance changes, piecewise-linear signals, and piecewise-quadratic signals.
  • 5.3 Results: Performance is assessed using the distribution of estimated-minus-true change-point counts, signal MSE, Hausdorff localisation distance, and computation time over 100 simulated datasets.Except for TF, signal estimates use least-squares fits between consecutive estimated change-points.
  • 5.3 Results: NOT is among the most competitive methods for estimating change-point counts, locations, and signals in most simulated scenarios.The study reports this overall pattern across the evaluated simulation settings rather than for a single signal or metric.
  • 5.3 Results: NOT is particularly fast in Scenarios (S2), (S3), and (S5), giving it a computational advantage over competitors in those settings.The broader methodology limits the number of sampled subsamples, and the solution-path computation is described as having low complexity.
  • 5.4 More on model misspecification and model selection: Under model misspecification, NOT0 overestimates change-point counts, whereas NOT2 often estimates the correct count at high signal-to-noise ratios but can have worse MSE and location accuracy than NOT1.At lower signal-to-noise ratios, NOT2 tends to underestimate counts, although its fitted signal can remain close to the truth; sSIC selects the correct polynomial order especially when the signal-to-noise ratio is high.

6 Real data analysis

The real-data analyses apply NOT to temperature anomalies and UK house-price changes, using piecewise-linear or piecewise-constant models to identify interpretable temporal features. The detected patterns align with several historically discussed periods, including the 2008–2009 financial crisis.

  • Temperature anomalies: The GISS Surface Temperature anomalies data span January 1880 to June 2016 and are defined relative to monthly 1951–1980 baseline averages.These anomaly series are commonly studied for change-point detection.
  • Temperature anomalies: A linear trend with non-abrupt changes motivates applying NOT under the piecewise-linear slope-change scenario.The analysis uses contrast (2.6) and SIC to select the model on the solution path.
  • Temperature anomalies: NOT identifies 8 temperature-anomaly change-points, including dates near 1910, 1945, and 1976 reported in earlier studies.The estimated dates are March 1901, December 1910, July 1915, June 1935, April 1944, December 1946, June 1976, and May 2015.
  • UK house prices: The UK House Price Index analysis examines monthly percentage changes and fits piecewise-constant means and standard deviations between NOT-estimated change-points.The figures cover Hackney, Newham, and Tower Hamlets using contrast (2.8), M = 10000 intervals, and SIC-selected thresholds.
  • UK house prices: NOT detects only a few house-price change-points, unlike Fryzlewicz’s TGUH method, which estimates at least 10 in each series.The smaller number of segments is described as facilitating interpretation.
  • UK house prices: All three boroughs show change-points around March 2008 and September 2009, alongside substantially higher estimated volatility during 2008–2009.The authors suggest these features may relate to the financial crisis and housing-market collapse.

Online supplementary materials for ‘Narrowest-Over-Threshold Detection of Multiple Changepoints and Change-point-like Features’

The supplementary materials document benchmark signals, fast contrast computation, and an efficient binary-tree algorithm for constructing NOT’s entire threshold-indexed solution path. They also provide additional simulations and real-data examples.

  • Supplementary contents: The supplementary materials contain computational details, additional simulations, and an additional oil-price example.They also list the signal configurations used in the simulation studies.
  • Simulation signals: The benchmark signals cover piecewise-constant, piecewise-linear, piecewise-quadratic, and discontinuous piecewise-linear settings with specified sample sizes and change-points.Examples include teeth, blocks, wave1, wave2, mix, vol, quad, and smile.
  • Simulation signals: The remaining benchmark designs include changing variance, quadratic coefficients, and possible jumps in piecewise-linear signals.These configurations define controlled signal and noise settings for evaluating NOT under different scenarios.
  • Computational implementation: For the considered scenarios, contrast values over a fixed interval can be computed in a single pass, giving linear cost in the number of observations.The calculation uses recursively updated inner products and scalar coefficients.
  • Solution path: Algorithm 2 constructs the threshold-indexed solution path using a binary tree whose nodes store detected locations, intervals, and maximum contrast values.Increasing the threshold requires reconstructing only branches containing nodes below the new threshold, reducing work relative to rebuilding from scratch.
  • Solution path: The binary-tree construction for a fixed threshold costs at most O(MK_ζT), where K_ζT is the tree height.The full solution-path complexity is discussed in the supplementary analysis.

B.3 An illustrative example

The illustrative example shows why NOT prioritizes narrow intervals: a large contrast on a long interval containing multiple change-points can locate neither feature accurately, whereas narrow over-threshold intervals isolate individual changes.

  • Contrast localization: On the full interval [1, 1000], the maximum contrast occurs at b = 490, far from both true change-points.The longest interval also has a much larger maximum contrast than the other intervals.
  • Narrowest-over-threshold selection: For ζT ∈ (0.08, 0.83), NOT selects [225, 450] or [500, 750], each containing exactly one change-point, and obtains a nearby candidate.The narrowest-over-threshold estimate is contrasted with selecting the candidate from the largest contrast alone.
  • Contrast localization: When an interval contains two change-points, its contrast maximum can be far from both despite being large.Intervals containing one change-point instead attain their maxima near that change-point.
  • Binary-tree solution path: Algorithm 2 begins with the shortest interval [450, 550] and then recursively builds left and right branches of the segmentation tree.In the example, the fourth solution contains exactly two nodes close to the true change-points.

C Additional simulation results

The additional simulations examine NOT under alternative noise distributions, including Laplace noise and Gaussian AR(1) dependence. These results extend the supplementary evaluation beyond the primary noise settings.

  • Noise robustness: Tables 5–7 summarize results for three different noise distributions used in the additional simulations.The supplied passages identify alternative noise settings rather than reporting their numerical outcomes.
  • Noise robustness: One additional setting uses zero-mean unit-variance Gaussian AR(1) noise with ϕ = 0.3, while another uses Laplace(0, 2^-1/2) noise.These settings test the procedure under heavy-tailed and dependent errors.

D Additional real data example: OPEC Reference Basket oil price

The OPEC oil-price analysis applies NOT to log returns and compares its detected change-points with NMCD, while evaluating residual dependence and simulated-data performance measures.

  • Data and setup: NOT analyses daily OPEC oil-price log returns from 1 January 2003 to 15 July 2016 rather than raw prices.The series is defined as Y_t = 100 log(P_t/P_t−1).
  • Simulation comparisons: Simulation summaries report the estimated-number error, signal mean-square error, Hausdorff distance, and computation time over 100 simulated data sets.The comparisons include Gaussian, Laplace, and Gaussian AR(1) noise settings across competing methods.
  • Detected change-points: Both NOT and NMCD detect 7 change-points, with nearby locations for 6 of NOT’s 7 detections.NMCD misses a nearby point around 29 April 2003, while it identifies two points in early 2016 where NOT identifies one.
  • Detected change-points: The analysis compares estimated change-point locations using Figure 10 and exact detections listed in Table 8.Figure 10 shows the price series and method-specific change-point markers; Table 8 lists exact locations and some coincident events.

E Proofs

The proofs analyze how NOT’s contrast behaves around isolated change-points in piecewise-constant and piecewise-linear signals, establishing localization properties under scenario-specific assumptions.

  • Piecewise-constant case: For piecewise-constant signals, the contrast is maximized at the true change-point within an interval containing exactly one change-point.The lemmas compare the contrast at the true location with candidate locations on either side.
  • Piecewise-linear continuous case: For piecewise-linear continuous signals, analogous lemmas characterize contrast differences and localization around a slope change-point.The arguments use distances to the change-point, left and right interval lengths, and the change magnitude.
  • Piecewise-linear continuous case: The piecewise-linear proofs use projection decompositions and bounds on residual sums of squares for fitting a single kink.The construction compares a true kink with a candidate kink inside an interval containing one change-point.
  • Proof qualifications: The constants in the rate bounds are not sharp because the lemmas are used to establish rate-type results.The proof notes that the case on the opposite side of the change-point follows by symmetry.

E.2 Proof of Theorem 1

The proof of Theorem 1 controls stochastic contrasts, constructs suitable random intervals around each change-point, and uses NOT’s narrowest-over-threshold rule to obtain localization and termination.

  • Proof strategy: The proof separates uniform stochastic control, candidate-location comparison, interval construction, single-change-point localization, and algorithm termination into five steps.These steps control contrasts, compare candidates with their noiseless analogues, and show that selected intervals isolate one change-point.
  • Interval isolation: Narrowest-over-threshold selection ensures the chosen interval cannot contain more change-points than a sufficiently short qualifying interval constructed around each target.This is the key argument for reducing the multiple-change-point problem to isolated single-change-point analyses.
  • Termination: After all change-points are detected, remaining intervals either contain none or place any change-points too close to their endpoints, so the algorithm stops.The proof concludes that no further detections occur.
  • Proof qualifications: The Bonferroni-based threshold constant is sufficient for consistency and rate results but is not claimed to be sharp.The proof notes that alternative bounds may improve this constant.
  • Piecewise-constant localization: For piecewise-constant signals, the proof obtains the localization bound |b*−τ_j| ≤ C3 log T/(Δf_j)^2.The bound follows after comparing noisy and noiseless contrasts uniformly over candidate locations.

E.3 Proof of Theorem 2

The proof of Theorem 2 repeats the interval-isolation and localization strategy for the piecewise-linear continuous scenario, yielding a change-point error rate and termination of NOT.

  • Proof strategy: Theorem 2’s proof proceeds analogously to Theorem 1 through events controlling stochastic contrasts and random-interval coverage.The proof defines the relevant events and assumes they hold for the main argument.
  • Proof qualifications: The proof does not refine several constants because its main purpose is to establish the rate.The text explicitly notes that the constants could be further refined.
  • Interval isolation: The selected narrowest-over-threshold interval is shown to contain exactly one change-point before its location is localized.The argument establishes non-emptiness of qualifying intervals and excludes intervals containing multiple change-points.
  • Localization rate: The piecewise-linear localization rate is |b*−τ_j| ≤ C3(Δf_j)^−2/3(log T)^1/3.The proof defines this quantity as the target error bound for candidate locations sufficiently far from the true change-point.
  • Detection and termination: The proof shows that each change-point is detected without duplication and that the algorithm terminates after all change-points are found.Once all change-points are detected, the remaining intervals cannot trigger further detections under the proof conditions.

E.4 Proof of Theorem 3

The proof shows that sSIC selects the correct number of change-points with probability tending to one, while the estimated locations achieve a logarithmic localization rate. It establishes these results by separately excluding underfitted and overfitted candidates.

  • Localization: A good candidate on the NOT solution path has the correct number of change-points and location errors bounded by C′ log T with arbitrarily high probability.The proof conditions on the existence of such a candidate for the remaining analysis.
  • Model selection: sSIC consistently estimates the number of change-points: P(ˆq = q) → 1 as T → ∞.The proof treats underestimation and overestimation separately.
  • Model selection: Underfitted candidates are rejected with probability tending to one, so P(ˆq < q) → 0.
  • Model selection: Overfitted candidates are rejected with probability tending to one, so P(ˆq > q) → 0.The argument compares overfitted candidates with a saturated oracle model.
  • Localization: The selected change-point locations satisfy P(max_j=1,...,q |ˆτ_j − τ_j| ≤ C log T) → 1.

E.5 Proof of Theorem 4

The proof extends the consistency analysis to piecewise-linear signals with finitely many kinks. It establishes correct kink-number selection and logarithmic localization under the stated assumptions, while also treating dependent noise with bounded autocorrelation effects.

  • Kink localization: The proof strengthens the localization analysis for signals with finitely many kinks whose spacings are O(T).
  • Kink-number consistency: The proof targets P(ˆq = q) → 1 by showing separately that underestimation and overestimation probabilities vanish.
  • Kink-number consistency: For large enough T, P(ˆq < q) → 0 for candidates estimating too few kinks.
  • Kink-number consistency: For large enough T, P(ˆq > q) → 0 for candidates estimating too many kinks.The proof uses a saturated-oracle comparison and shows the relevant sSIC difference is positive.
  • Kink localization: The selected estimator places each estimated kink within a δT/6 neighborhood of its corresponding true kink and has no other estimated kink in the surrounding interval.
  • Dependent noise: Under dependent noise, the largest eigenvalue of the autocorrelation matrix is bounded above by a constant P independent of T.This follows from the assumed bound on the sum of absolute autocorrelations.
Loading 1609.00293v2…