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

Abstract

We propose a new, generic and flexible methodology for nonparametric function\nestimation, in which we first estimate the number and locations of any features\nthat may be present in the function, and then estimate the function\nparametrically between each pair of neighbouring detected features. Examples of\nfeatures handled by our methodology include change-points in the\npiecewise-constant signal model, kinks in the piecewise-linear signal model,\nand other similar irregularities, which we also refer to as generalised\nchange-points.\n Our methodology works with only minor modifications across a range of\ngeneralised change-point scenarios, and we achieve such a high degree of\ngenerality by proposing and using a new multiple generalised change-point\ndetection device, termed Narrowest-Over-Threshold (NOT). The key ingredient of\nNOT is its focus on the smallest local sections of the data on which the\nexistence of a feature is suspected. Crucially, this adaptive localisation\ntechnique prevents NOT from considering subsamples containing two or more\nfeatures, a key factor that ensures the general applicability of NOT.\n For selected scenarios, we show the consistency and near-optimality of NOT in\ndetecting the number and locations of generalised change-points. Furthermore,\nwe propose to select NOT's threshold (automatically) via the strengthened\nSchwarz Information Criterion (sSIC) and give theoretical justifications. The\nNOT estimators are easy to implement and rapid to compute: the entire\nthreshold-indexed solution path can be computed in close-to-linear time.\nImportantly, the NOT approach is easy to extend by the user to tailor to their\nown needs. There is no single competitor, but we show that the performance of\nNOT matches or surpasses the state of the art in the scenarios tested. Our\nmethodology is implemented in the R package \\textbf{not}.\n