# Data segmentation algorithms: Univariate mean change and beyond

Haeran Cho1 and Claudia Kirch2

###### Abstract

Data segmentation a.k.a. multiple change point analysis has received
considerable attention due to its importance in time series analysis and
signal processing, with applications in a variety of fields including natural
and social sciences, medicine, engineering and finance.

The goal of this survey article is twofold: In the first part, we review the
existing literature on the _canonical data segmentation problem_ which aims at
detecting and localising multiple change points in the mean of univariate time
series. We provide an overview of popular methodologies on their computational
complexity and theoretical properties. In particular, our theoretical
discussion focuses on the _separation rate_ relating to which change points
are detectable by a given procedure, and the _localisation rate_ quantifying
the precision of corresponding change point estimators, and we distinguish
between whether a _homogeneous_ or _multiscale_ viewpoint has been adopted in
their derivation. We further highlight that the latter viewpoint provides the
most general setting for investigating the optimality of data segmentation
algorithms.

Arguably, the canonical segmentation problem has been the most popular
framework to propose new data segmentation algorithms and study their
efficiency in the last decades. In the second part of this survey, we motivate
the importance of attaining an in-depth understanding of strengths and
weaknesses of methodologies for the change point problem in a simpler,
univariate setting, as a stepping stone for the development of methodologies
for more complex problems. We illustrate this with a range of examples
showcasing the connections between complex distributional changes and those in
the mean. We also discuss extensions towards high-dimensional change point
problems where we demonstrate that the challenges arising from high
dimensionality are orthogonal to those in dealing with multiple change points.

11footnotetext: School of Mathematics, University of Bristol, UK. Email:
<EMAIL_ADDRESS>
Supported by the Leverhulme Trust Research Project Grant
(RPG-2019-390).22footnotetext: Department of Mathematics, Otto-von-Guericke
University; Center for Behavioral Brain Sciences (CBBS); Magdeburg, Germany.
Email<EMAIL_ADDRESS>
##  1 Introduction

Change point analysis has a long tradition in statistics dating back to 1950s
(see Page [148]) and has been a very active field of research ever since due
to its importance in time series analysis, signal processing and many other
applications where data is routinely collected over time in naturally
nonstationary environments. This popularity can partly be explained by the
fact that the assumption of piecewise stationarity underlying change point
analysis, is one of the simplest forms of departure from stationarity while at
the same time, it is found to be reasonable for many applications. There are
also other types of non-stationarities such as unit roots or local
stationarity that have been studied extensively in the literature which,
however, will not be discussed in this article.

Research in change point analysis has predominantly focused on the following
two directions: One line of research is on the development of sequential or
online methodologies based on optimal stopping (see e.g. the recent books by
Tartakovsky et al. [172] and Tartakovsky [171]) which is being actively
studied to date but will not be part of this review. The second direction
addresses the problem of change point detection in a posteriori or offline
settings. Much of the research in the last century dealt with change point
testing against the at-most-one-change (AMOC) alternative (see e.g. the books
by Csörgö and Horváth [51] and Chen and Gupta [38]). Based on such tests, the
location of a single change point can be estimated with the optimal
localisation properties, typically by scanning for the point where the
corresponding statistic attains its maximum. More recent papers tackle change
point problems in complex situations (see the review papers by Aue and Horváth
[15] and Horváth and Rice [89] and also Section 4 below), both sequentially
and retrospectively, and this review paper focuses on the latter.

In retrospective change point analysis, it is often more realistic to allow
for multiple change points, where the goal is to estimate both the total
number and locations of the change points, a.k.a. data segmentation. While
there already exist early papers showing the consistency of various change
point procedures that make use of e.g. binary segmentation (i.e. iteratively
testing for a change point and partitioning the data into two, [182]), or
information criteria [125, 190], the problem of detecting multiple change
points in data sequences experienced renewed interest in the statistical
literature during the last 10 years. This was driven by several factors
including the emergence of scientific problems requiring high-precision and
high-speed segmentation algorithms: Such examples can be found in genomics
[35, 128, 144, 145], astronomy [71], neurophysiology [140], climatology [156],
cyber-security [1] and finance [41], to name but a few. Accordingly, there has
been a surge of interest for computationally fast and statistically efficient
methods for data segmentation, and most effort in this direction has been
devoted to the problem of detecting multiple change points in the mean of
univariate data. In this article, we also take this as an important starting
point for developing change point methodologies in more complex situations. We
first review the methods for detection and localisation of multiple change
points in the mean of univariate data, which we refer to as the _canonical
segmentation problem_ , complementing the articles reviewing and comparing
different change point detection algorithms such as [2, 61, 68, 178].

As noted by Brodsky and Darkhovsky [31] (see also the discussion in Section
4.1 below), more complex change point problems that allow changes in
stochastic properties other than the mean, can be reduced to the (possibly
multivariate) canonical segmentation problem after applying a suitable
transformation to the input data that reveals the changes as those in the mean
of the transformed data. Also, the challenges due to high dimensionality of
the data, which is another important area of active research (see Section 4.2
below), are orthogonal to those arising from the presence of multiple change
points over time. Thus we argue that the suite of algorithms developed for the
canonical segmentation problem serve as a foundation for developing
methodologies for more complex change point problems.

The rest of the paper is organised as follows. Section 2 describes the
canonical segmentation problem including its aim and theoretical benchmarks,
and Section 3 reviews the state-of-the-art methodologies developed for this
purpose. Section 4 provides an overview of the existing literature on more
complex change point problems beyond mean changes and finite dimensionality,
and discuss how the data segmentation algorithms described in Section 3 can be
adapted for such problems.

##  2 Multiple change point detection in the mean of univariate data

We regard the following change point model

$\displaystyle X_{t}$
$\displaystyle=f_{t}+\varepsilon_{t}=f_{0}+\sum_{j=1}^{q_{n}}d_{j}\cdot\mathbb{I}_{t\geq\theta_{j}+1}+\varepsilon_{t},\quad\mathsf{E}(\varepsilon_{t})=0\text{
and }\mathsf{Var}(\varepsilon_{t})=\sigma^{2},\quad t=1,\ldots,n,$ (1)

as the canonical change point model, where we denote by $q_{n}$ the total
number of change points in the mean of $\\{X_{t}\\}_{t=1}^{n}$, by
$\theta_{j}=\theta_{j,n},\,j=1,\ldots,q_{n}$, their locations, by
$d_{j}=d_{j,n}$ the (signed) magnitude of change and by
$\delta_{j}=\delta_{j,n}=\min(\theta_{j}-\theta_{j-1},\theta_{j+1}-\theta_{j})$
the minimum distance from $\theta_{j}$ to its neighbouring change points, with
the notational convention that $\theta_{0}=0$ and $\theta_{q_{n}+1}=n$. In
data segmentation, the goal is to consistently estimate the number and the
locations of the change points, and we review the methodologies proposed for
this purpose in Section 3.

In contrast, in the corresponding testing problems, the aim is to test
$H_{0}:\,q_{n}=0$ against $H_{1}:\,q_{n}\geq 1$; in the AMOC setting, the
alternative hypothesis is given by $H_{1}:\,q_{n}=1$. There exist a wide
variety of procedures proposed for change point testing, not only against the
alternative of mean shifts but also allowing for more complicated structural
breaks (see Section 4.1 for such examples). There are also a few methods that
sequentially test for an increasing number of change points, i.e.
$H_{0}:\,q_{n}=m$ against $H_{1}:\,q_{n}=m+1$ for given $m$ [21, 136]. These
tests can be used as a pre-processing step to determine whether the data is
sufficiently close to stationary, or whether a multiple change point detection
methodology is required to segment the data into (approximately) stationary
stretches. They can also serve as a basis for developing a data segmentation
methodology, with the simplest example being the binary segmentation
algorithm, see Section 3.2 below.

We assume that $\max_{1\leq j\leq q_{n}}|d_{j}|=O(1)$ as well as $\min_{1\leq
j\leq q_{n}}\delta_{j}\to\infty$, separating the change point detection
problem under (1) from that of outlier detection. Indeed, one of the main
differences between the two problems is that in outlier detection, an increase
in sample size does not benefit the performance of an outlier detection
procedure beyond that it helps getting more precise estimators for the
quantiles and, even so, the size of the outlier is required to be larger than
these quantiles for its detection. On the other hand, in change point
detection, the increased sample size (which corresponds to
$\delta_{j}\to\infty$ under (1)) allows for the detection of local changes
where $d_{j}\to 0$; therefore, looking for outliers in the differenced time
series $\\{X_{t}-X_{t-1}\\}_{t=2}^{n}$ cannot provide an adequate solution to
the change point problem.

Generally, the detectability of change points is determined by an interplay
between the magnitude of changes and their distance to neighbouring change
points: Large changes are detectable even if they are close to the adjacent
change points while for smaller changes, they should be sufficiently distanced
away from the neighbouring change points to be detectable. When large frequent
changes and small changes over long stretches are simultaneously present in
the same time series, it calls for a multiscale methodology that adapts to
such situations and detects all change points. This gives rise to the
distinction between a homogeneous change point scenario where the magnitude of
changes and the spacing between change points are on the same scale for all
change points, and the multiscale scenario where this is not the case. The
difficulty of the canonical segmentation problem for a given time series under
(1), is gauged by the detection lower bound $\Delta_{n}$ relating the
magnitude of the change $d_{j}$ to the minimum distance to neighbouring change
points $\delta_{j}$, and different formulations of the detection lower bound
reflect these different scenarios, see Definition 2.1 (a) for the precise
statement. When $\Delta_{n}$ diverges faster than the _separation rate_
associated with a given methodology, changes are detectable with asymptotic
power one and their locations can be estimated with accuracy.

Frequently, a methodology is deemed consistent in multiple change point
detection with the _localisation rate_ $\rho_{n}$, when it returns
$\widehat{\Theta}=\\{\widehat{\theta}_{j},\,1\leq
j\leq\widehat{q}:\,\widehat{\theta}_{1}<\ldots<\widehat{\theta}_{\widehat{q}}\\}$
satisfying

$\displaystyle\widehat{q}=q_{n}\quad\text{and}\quad\max_{1\leq j\leq
q_{n}}w_{j}|\widehat{\theta}_{j}\cdot\mathbb{I}_{j\leq
q_{n}}-\theta_{j}|\leq\rho_{n}$ (2)

with probability tending to one, for some $\rho_{n}/n\to 0$. The quantity
$w_{j}$ denotes the difficulty associated with localising each change point
$\theta_{j}$, which can also be formulated within the homogeneous or
multiscale scenarios.

Definition 2.1, taken from Cho and Kirch [45], distinguishes multiscale
formulations of detection lower bound and localisation rate from their non-
multiscale, homogeneous counterparts.

######  Definition 2.1.

  1. (a)

Detection lower bound:

    1. (i)

Homogeneous change points: $\Delta_{n}=\min_{1\leq j\leq
q_{n}}d_{j}^{2}\cdot\min_{1\leq j\leq q_{n}}\delta_{j}$.

    2. (ii)

Finite mixture of homogeneous change points: There are $N<\infty$ disjoint
subsets of change points with their indices given by
$\mathcal{J}_{k},\,k=1,\ldots,N$, such that
$\bigcup_{k=1}^{N}\mathcal{J}_{k}=\\{1,\ldots,q_{n}\\}$, whereby change points
within each subset are homogeneous as defined in (a)(i) and
$\Delta_{n}=\min_{1\leq k\leq
N}(\min_{j\in\mathcal{J}_{k}}d_{j}^{2}\cdot\min_{j\in\mathcal{J}_{k}}\delta_{j}$).
A special case is when there are finitely many changes with $N=q_{n}$.

    3. (iii)

Multiscale change points: $\Delta_{n}=\min_{1\leq j\leq
q_{n}}d_{j}^{2}\,\delta_{j}$.

  2. (b)

Localisation rate: We distinguish between a homogeneous localisation rate
where the estimation error for the $j$-th change point,
$|\widehat{\theta}_{j}-\theta_{j}|$, is weighted globally with
$w_{j}=\min_{1\leq j\leq q_{n}}d_{j}^{2}$, and a multiscale localisation rate
where it is weighted locally with $w_{j}=d_{j}^{2}$.

In the AMOC situation where $q_{n}\leq 1$, all scenarios in Definition 2.1 (a)
coincide and reduce to the assumption
$d_{1}^{2}\min(\theta_{1},n-\theta_{1})\to\infty$ which is commonly found in
the change point testing literature, see Section 1.5 of Csörgö and Horváth
[51]. However, when $q_{n}>1$ (and possibly diverging with $n$), they truly
reflect different scenarios: Proceeding from (i) to (iii) enlarges the
associated parameter space, and thus (iii) provides the most general setting
in which to investigate the detection power of a segmentation procedure. While
most of the literature deals with the homogeneous setting (see Section 3.3),
it is often too restrictive and does not permit large frequent jumps alternate
with small jumps over long segments – a situation naturally embedded in the
multiscale setting. In Definition 2.1 (b), the multiscale localisation rate
relates the difficulty in accurate localisation of each change point to the
size of the corresponding jump.

Propositions 2.1 and 2.2 state the benchmarks for the minimax optimal
separation and localisation rates, which have been established under the
special case where $\\{\varepsilon_{t}\\}_{t=1}^{n}$ are i.i.d. (sub-)Gaussian
random variables. To the best of our knowledge, there do not exist equivalent
results on the detection lower bound or the localisation rate (when
$q_{n}\to\infty$) beyond the case of i.i.d. sub-Gaussianity. For the AMOC
alternative, it is well known that the minimax optimal localisation rate is
given by $O_{P}(1)$ (see Korostelev [119]), i.e. $\rho_{n}\to\infty$
arbitrarily slowly in (2). This rate extends beyond Gaussianity and
independence when there are a finite number of change points, see Corollary
4.4 of Cho and Kirch [45].

######  Proposition 2.1 (Proposition 1 of Arias-Castro et al. [10], lower
bound on the minimax separation rate).

Under (1), let $H_{0,n}:\,q_{n}=0$ and $H_{1,n}$ describe the setting where
$q_{n}=2$, $d_{n}:=d_{1}=-d_{2}$ and $\delta_{n}:=\theta_{2}-\theta_{1}$ with
$n^{-1}\delta_{n}\to 0$. Then, $H_{0,n}$ and $H_{1,n}$ are asymptotically
inseparable if
$|d_{n}|\sqrt{\delta_{n}}\leq\sqrt{2\log(n/\delta_{n})}-\nu_{n}$ where
$\nu_{n}\to\infty$.

######  Proposition 2.2 (Proposition 6 of Fromont et al. [73], lower bound on
the minimax localisation rate for possibly an unbounded number of change
points).

Under (1) with $q_{n}\geq 2$, let $|d_{j}|=:d_{n}$ for all $j=1,\ldots,q_{n}$,
and denote by

$\displaystyle\Xi=\left\\{(\theta_{1},\ldots,\theta_{q_{n}}):\,0\equiv\theta_{0}<\theta_{1}<\ldots<\theta_{q_{n}}<\theta_{q_{n}+1}\equiv
n,\quad\text{and}\right.$ $\displaystyle\left.d_{n}^{2}\min_{1\leq j\leq
q_{n}}(\theta_{j+1}-\theta_{j-1})>c\log(q_{n})\right\\}$

for some $c>0$, the parameter space for the locations of change points. Then,
for some $C>0$,

$\displaystyle\inf_{\mathcal{K}\in\mathbb{N}^{q_{n}}}\sup_{\Theta\in\Xi}\mathsf{E}_{\Theta}\\{d_{H}(\mathcal{K},\Theta)\\}\geq
Cd_{n}^{-2}\log(q_{n})$

where
$d_{H}(\mathcal{K},\Theta)=\max\\{\max_{k\in\mathcal{K}}\min_{\theta\in\Theta}|k-\theta|,\max_{\theta\in\Theta}\min_{k\in\mathcal{K}}|\theta-k|\\}$
denotes the Hausdorff distance.

##  3 Review of data segmentation methodologies

Broadly, algorithms for the canonical segmentation problem can be categorised
into two: One line of research casts the problem as that of globally
optimising an objective function, which imposes a penalty on the model
complexity given e.g. by the number of change points; the other is closely
related to the change point testing literature, whereby the test for detecting
a single change point is applied locally for detection and estimation of
multiple change points. We briefly mention that there exist methods based on
hidden Markov models where the main focus lies in modelling such phenomena,
with algorithms for estimating the sequence of hidden states [79, 177]. There
are also methods allowing for Bayesian inference under change point models
[25, 60, 66, 159, 189], see Eckley et al. [61] for further references.

In what follows, we review the literature on the canonical segmentation
problem under (1) according to the above categorisation, providing brief
descriptions of representative methodologies and their computational
complexity as well as theoretical properties in relation to the benchmark
provided in Section 2.

###  3.1 Global optimisation methods

####  3.1.1 $\ell_{0}$-penalisation

Information criteria have popularly been adopted in change point problems.
Under (1), the Schwarz criterion [164, SC] takes the form

$\displaystyle\mbox{SC}(\mathcal{A})=\frac{n}{2}\log\left(\frac{\mbox{RSS}(\mathcal{A})}{n}\right)+p_{n}(\mathcal{A})\quad\text{where}$
(3)
$\displaystyle\mbox{RSS}(\mathcal{A})=\sum_{j=0}^{m}\sum_{t=k_{j}+1}^{k_{j+1}}(X_{t}-\bar{X}_{k_{j}:k_{j+1}})^{2}\quad\text{with}\quad\bar{X}_{a:b}=\frac{1}{b-a}\sum_{t=a+1}^{b}X_{t}.$
(4)

The function $p_{n}(\mathcal{A})$ denotes the penalty imposed on the
complexity of a model determined by a set of change point candidates
$\mathcal{A}=\\{k_{j},\,1\leq j\leq
m:\,k_{1}<\ldots<k_{m}\\}\subset\mathcal{I}_{1}:=\\{1,\ldots,n-1\\}$ (with
$k_{0}=0$ and $k_{m+1}=n$); a popular choice is
$p_{n}(\mathcal{A})=\lambda_{n}\;|\mathcal{A}|$ where $\lambda_{n}$ is a
tuning parameter. For some integer $N\leq n$, we denote a collection of all
subsets of $\mathcal{I}_{1}$ with their cardinality bounded by $N$, by
$\mathfrak{A}[N]=\left\\{\mathcal{A}\subset\mathcal{I}_{1}:\,|\mathcal{A}|\leq
N\right\\}$. Then, minimising $\mbox{SC}(\mathcal{A})$ over
$\mathcal{A}\in\mathfrak{A}[N]$ returns a set of change point estimators,
$\widehat{\Theta}(\mathfrak{A}[N])=\min_{\mathcal{A}\in\mathfrak{A}(N)}\mbox{SC}(\mathcal{A})$.

With the penalty linear in the number of candidate change points as
$p_{n}(\mathcal{A})=(1+\epsilon)\log(n)\cdot|\mathcal{A}|$, the consistency of
SC in estimating the total number of change points has been established under
i.i.d. Gaussianity, in Yao [190] (with $\epsilon=0$) and Lee [125] (with a
small constant $\epsilon>0$), in the setting where both $q_{n}$ and $N$ are
fixed with $N>q_{n}$. This result is complemented by Yao and Au [192], where
the consistency of the least squares estimators of $\theta_{j},$ $1\leq j\leq
q_{n}$, is established and their distribution is derived when $q_{n}$ is fixed
and known. Penalties depending on the spacing between the change points as
well as the total number $|\mathcal{A}|$, are considered in Chen et al. [37],
Pan and Chen [149] and Zhang and Siegmund [194], and the application of the
Akaike information criterion to the change point problem is studied in
Ninomiya [143].

Boysen et al. [30] consider the minimisation of the Potts functional

$\displaystyle\widehat{\Theta}(\mathfrak{A})=\arg\min_{\mathcal{A}\in\mathfrak{A}}P_{0}(\mathcal{A}),\quad\text{where}\quad
P_{0}(\mathcal{A})=\frac{1}{n}\mbox{RSS}(\mathcal{A})+p_{n}(\mathcal{A})$ (5)

with $p_{n}(\mathcal{A})=\lambda_{n}|\mathcal{A}|$, over
$\mathcal{A}\in\mathfrak{A}[n-1]=:\mathfrak{A}$, i.e. without any bound on the
cardinality of $\mathcal{A}$ other than the trivial one. Under i.i.d. sub-
Gaussianity, they show the consistency of $\widehat{\Theta}(\mathfrak{A})$
both in estimating the total number and the locations of change points,
provided that $\lambda_{n}\to 0$ and $n\lambda_{n}/\log(n)\to\infty$. Lavielle
and Moulines [123] establish the asymptotic consistency of the minimiser of
the Potts functional under general conditions on $\\{\varepsilon_{t}\\}$,
given that a suitable upper bound on the number of change points $N$ is
available. Wang et al. [185] extend the results of Boysen et al. [30] to the
settings where $q_{n}\to\infty$, $\min_{1\leq j\leq q_{n}}|d_{j}|\to 0$ and
$n^{-1}\min_{1\leq j\leq q_{n}}\delta_{j}\to 0$ as $n\to\infty$, with the
penalty $p_{n}(\mathcal{A})=\log^{1+\epsilon}(n)\cdot|\mathcal{A}|$ for some
small $\epsilon>0$. By considering a location-dependent penalty
$p_{n}(\mathcal{A})=n^{-1}L\\{\lambda|\mathcal{A}|+2\sum_{j=0}^{m}\log(n/(k_{j+1}-k_{j}))\\}$
with some tuning parameters $L,\lambda>0$, Fromont et al. [73] show that the
minimisation of $P_{0}(\mathcal{A})$ achieves minimax optimality in both
detection lower bound and change point localisation, matching the rates
provided in Propositions 2.1–2.2.

There exist dynamic programming algorithms which solve the
$\ell_{0}$-penalised least squares estimation problem in (5). The segment
neighbourhood approach [19] requires an upper bound on the number of change
points, say $N$, and solves the constrained minimisation problems for a
varying number of change points, attaining the computational complexity of
$O(Nn^{2})$. The optimal partitioning [105] approach, by recursively searching
for the optimal partition conditioning on the latest change point estimator,
achieves the computational complexity of $O(n^{2})$ for a given choice of the
penalty. There are several methods which aim at speeding up the dynamic
programming algorithms by pruning the search space, such as the pruned exact
linear time method [110], the functional pruning technique [157] and their
extensions [135]. Haynes et al. [85] provide a methodology for finding the
solution path for a range of penalty parameters
$\lambda\in[\lambda_{\min},\lambda_{\max}]$, when the penalty increases
linearly in the size of $\mathcal{A}$ as
$p_{n}(\mathcal{A})=\lambda|\mathcal{A}|$, while Lebarbier [124] proposes the
slope heuristic method that examines how the segmentation result varies with
such $\lambda$. Tickle et al. [176] investigate the parallelisation of dynamic
programming-based methods for fast computation when $n$ is very large.
Imposing an autoregressive (AR) structure of order one on
$\\{\varepsilon_{t}\\}$, Chakar et al. [34] propose an adaptation of (3) and
provide an algorithm for approximating its global minimiser. Further allowing
for random walk-like fluctuations, Romano et al. [162] provides an efficient
dynamic programming algorithm that returns an exact solution of the
minimisation problem.

Finally, we mention that the objective function based on the minimum
description length principle [83, 161] imposes an $\ell_{0}$-type penalty on
the model complexity, and has successfully been applied to piecewise
parametric modelling [17, 52, 53] in combination with the genetic algorithm to
traverse the parameter space and solve the optimisation problem.

####  3.1.2 $\ell_{1}$-penalisation

While efficient algorithms exist for the optimisation of $\ell_{0}$-penalised
objective functions, the computational complexity typically scales
quadratically in $n$. Relaxing the $\ell_{0}$-penalty in (5) to an
$\ell_{1}$-penalty (a.k.a. total variation penalty) gives rise to

$\displaystyle P_{1}(\mathbf{g})$
$\displaystyle=\frac{1}{n}\sum_{t=1}^{n}(X_{t}-g_{t})^{2}+\lambda_{n}\sum_{t=1}^{n-1}|g_{t+1}-g_{t}|,\quad\mathbf{g}=(g_{1},\ldots,g_{n})^{\top},$
(6)

which is closely related to the fused Lasso, originally introduced in
Tibshirani et al. [174] to take into account the ordering of the features in
the data. The locations of change points are estimated by the locations of
jumps in
$\widehat{\mathbf{g}}=\arg\min_{\mathbf{g}\in\mathbb{R}^{n}}P_{1}(\mathbf{g})$.
Harchaoui and Lévy-Leduc [84] show that adopting the least angle regression
proposed by Efron et al. [62] in the context of $\ell_{1}$-penalised linear
regression, the computational complexity of solving for $\widehat{\mathbf{g}}$
is $O(N^{3}+Nn\log(n))$, where $N$ denotes the maximal number of change point
candidates to be considered and needs to be specified. The properties of the
$\ell_{1}$-penalised least squares estimator $\widehat{\mathbf{g}}$, both in
its $\ell_{2}$-error in estimating the mean and change point localisation, has
been studied in Rinaldo [160] and Harchaoui and Lévy-Leduc [84] under i.i.d.
(sub-)Gaussianity. Lin et al. [130] provide a near-minimax optimal rate (up to
$\log\log(n)$) for the $\ell_{2}$-error when the change points are sparse, but
also show that $\widehat{\mathbf{g}}$ tends to over-estimate the number of
change points and requires further post-processing for consistent estimation
of $q_{n}$.

####  3.1.3 Multiscale change point segmentation methods

Li et al. [129] define a class of multiscale change point segmentation (MCPS)
methods, which include the simultaneous multiscale change point estimators
controlling for the family-wise error rate [72, SMUCE] and the false discovery
rate [128, FDRseg] in estimating the number of change points. They solve a
(non-convex) optimisation problem, which searches for the most parsimonious
candidate estimator of the piecewise constant function over the acceptance
region of a suitable multiscale test. More specifically, the optimisation
problem is given by

$\displaystyle\min_{g\in S[0,1)}\\#J(g)\quad\text{subject
to}\quad\max_{\begin{subarray}{c}I\in\mathcal{M}\\\ g\equiv\gamma_{I}\text{ on
}I\end{subarray}}\left\\{\frac{1}{\sqrt{|I|}}\left|\sum_{t/n\in
I}(X_{t}-\gamma_{I})\right|-s_{I}\right\\}\leq\eta,$ (7)

where $\\#J(g)$ denotes the number of jumps in $g\in S[0,1)$, the space of
right-continuous step functions on $[0,1)$ (whose change points lie on the
grid $\\{i/n\\}_{i=0}^{n-1}$), $\mathcal{M}$ a multiscale system of sub-
intervals of $[0,1)$ fulfilling a set of requirements, $s_{I}$ a scale penalty
and $\eta$ a threshold controlling the over-estimation probability.

Frick et al. [72] establish the near-minimax optimality of SMUCE as given in
Propositions 2.1–2.2, under the exponential family regression model with the
parameter varying over time in a piecewise constant manner, and discuss an
efficient implementation of the optimisation problem in (7) via dynamic
programming. For the canonical segmentation problem, Pein et al. [150] and
Dette et al. [58] address the issues arising from heteroscedasticity and
serial dependence in $\\{\varepsilon_{t}\\}_{t=1}^{n}$, respectively.

####  3.1.4 Model selection-based segmentation

Arlot and Celisse [11] investigate the use of cross-validation for the change
point problem under (1). With $\mbox{RSS}(\mathcal{A})$ defined in (4) serving
as the empirical risk measure of a change point model $\mathcal{A}$, the
proposed method adopts the leave-one-out or $K$-fold cross-validation methods
for final model selection, in place of imposing a penalty on the model
complexity as the class of methods discussed in Sections 3.1.1 and 3.1.2. The
paper provides a dynamic programming approach to efficiently compute the
procedure and studies its theoretical performance in terms of the
$\ell_{2}$-error.

###  3.2 Local testing methods

The methodologies belonging to this class generally proceed in two stages:
First, the data is scanned for candidate change point estimators, from which
the final estimators are selected via a model selection method.

In the first step, candidate generation is achieved by multiscale scanning of
the data for change points using the following weighted cumulative sum (CUSUM)
statistics computed on the segment $\\{X_{t},\,s<t\leq e\\}$:

$\displaystyle\mathcal{T}_{s,k,e}(X)=\sqrt{\frac{(k-s)(e-k)}{e-s}}\left(\bar{X}_{s:k}-\bar{X}_{k:e}\right)\quad\text{where}\quad\bar{X}_{a:b}=\frac{1}{b-a}\sum_{t=a+1}^{b}X_{t},$

for $0\leq s<k<e\leq n$. In the AMOC setting, it is well-known that the
location of the maximum of the CUSUM statistics given by
$k_{\circ}=\arg\max_{0<k<n}|\mathcal{T}_{0,k,n}(X)|$, is a consistent minimax
optimal estimator for the change point. This motivates taking the maximiser of
the CUSUM statistics as a change point candidate within the local interval
$(s,e)$ provided that $\max_{s<k<e}|\mathcal{T}_{s,k,e}(X)|$ is large enough.

A variety of methods adopt $\mathcal{T}_{s,k,e}(X)$ in order to scan the data
for change points with a method-specific search space
$\mathcal{S}\subset\mathcal{I}_{3}:=\\{(s,k,e):\,0\leq s<k\leq n\\}$, which is
either fixed, random or data-dependent. The construction of the search space
aims at isolating change points for their detection and localisation: Ideally,
for each change point, $\mathcal{S}$ contains at least one interval which is
as large as possible for the detection of even a small change, while
containing only a single change point for its localisation and thus avoiding
the contamination by multiple change points (further discussion on this point
is found in Section 3.2.1). Once candidate change point estimators are
identified, it remains to determine the final set of estimators which is
achieved by a model selection (pruning) methodology, such as thresholding or
information criteria.

In Sections 3.2.1–3.2.3, we discuss candidate generation strategies which scan
the data using $\mathcal{T}_{s,k,e}(X)$ with different search spaces
$(s,k,e)\in\mathcal{S}$. Then in Section 3.2.4, we describe popular model
selection methodologies applied to the thus-generated candidate change point
estimators.

####  3.2.1 Binary segmentation algorithm and its extensions

Binary segmentation (BS) algorithm [165, 182] is a generic method for multiple
change point estimation which recursively partitions the data into two. For
multiple change point detection under (1), it identifies a candidate estimator
$k_{1}$ from scanning the CUSUM statistic $|\mathcal{T}_{0,k,n}(X)|,\,1\leq
k<n$, as its maximiser. If the maximum CUSUM (max-CUSUM) statistic
$\mathcal{T}_{0,n}^{\max}=\max_{1\leq k<n}|\mathcal{T}_{0,k,n}(X)|$ is
sufficiently large, the data is partitioned into $\\{X_{t}\\}_{t=1}^{k_{1}}$
and $\\{X_{t}\\}_{t=k_{1}+1}^{n}$, and the scanning and maximisation of the
CUSUM statistics is repeated over each partition separately until a stopping
criterion is met. The search space of BS is stochastic, as the search space at
the $i$-th iteration with $i\geq 2$ depends on the change points detected at
earlier iterations, and its complexity is typically $O(n\log(n))$. Venkatraman
[179] established the consistency of BS while allowing the number of change
points, $q_{n}$, to diverge with $n$.

The CUSUM statistic coincides with the likelihood ratio statistic for testing
the null hypothesis of no change point ($H_{0}:\,q_{n}=0$) against the AMOC
alternative ($H_{1}:\,q_{n}=1$) under i.i.d. Gaussian errors, and thus is
particularly well-adopted for the detection and localisation of a single
change point. On the other hand, in the presence of multiple change points, BS
often performs poorly in estimating the locations of the change points as the
search space may include intervals contaminated by more than one change
points. The CUSUM-based test still attains good power when applied to such
intervals, but the statistic may be unsuitable for locating the change points
due to this contamination. Figure 1 provides an illustration where, while
$|\mathcal{T}_{0,k,n}(X)|,\,1\leq k<n$, attain large values near the two
change points, their precise locations are not well pointed out by the
statistic. In such a situation, procedures that aim at isolating each change
point for its detection and localisation, such as the moving sum procedure
(see Section 3.2.2), perform better in locating the change points although
they tend to lack power by comparison when used solely for testing.

Figure 1: Top: A realisation $\\{X_{t}\\}_{t=1}^{n}$ from (1) with
$f_{t}=2\cdot\mathbb{I}_{t\geq 141}+2\cdot\mathbb{I}_{t\geq 161}$,
$\varepsilon_{t}\sim_{\mbox{\scriptsize{iid}}}\mathcal{N}(0,1)$ and $n=300$
and the piecewise constant signal $f_{t}$ (bold). Bottom:
$|\mathcal{T}_{0,k,n}(X)|,\,1\leq k<n$ (solid), and
$|\mathcal{T}_{k-G,k,k+G}(X)|,\,k\in\mathcal{S}_{\text{M}}(G)$ with a boundary
correction and $G=15$ (broken, see Section 3.2.2 for further details), plotted
with the vertical dotted lines denoting the locations of $\theta_{j},\,j=1,2$.

The wild binary segmentation (WBS) algorithm proposed in Fryzlewicz [74] sets
out to remedy the limitation of BS by scanning the data over a random grid
$\mathcal{R}_{n}\subset\mathcal{I}_{2}:=\\{(s,e):\,0\leq s<e\leq n\\}$, which
amounts to examining
$\mathcal{T}_{s,k,e}(X),\,(s,k,e)\in\mathcal{S}_{\text{W}}(\mathcal{R}_{n})$
with

$\displaystyle\mathcal{S}_{\text{W}}(\mathcal{R}_{n})=\left\\{(s,k,e):\,k=s+1,\ldots,e,\,(s,e)\in\mathcal{R}_{n}\right\\}.$

As in BS, WBS recursively identifies candidate change point estimators and
partitions the data into two, but the search is performed over the randomly
drawn background intervals and thus its computational complexity is determined
by the choice of $\mathcal{R}_{n}$ as $O(n|\mathcal{R}_{n}|)$. In order to
ensure that each change point is considered on its own within a large enough
interval for its detection and estimation, WBS requires that a sufficiently
large number of background intervals are drawn; more precisely,
$|\mathcal{R}_{n}|$ is required to increase as the minimum distance between
the change points, $\delta_{n}:=\min_{1\leq j\leq q_{n}}\delta_{j}$, decreases
such that $(n/\delta_{n})^{-2}|\mathcal{R}_{n}|\to\infty$. Fryzlewicz [74]
refines the theoretical analysis of Venkatraman [179], and shows that WBS
outperforms BS in terms of both the separation and the localisation rates.

There exist several modifications and extensions of WBS. Wang et al. [185]
consider WBS with the lengths of the background intervals in $\mathcal{R}_{n}$
bounded from above by $\delta_{n}$, which ensures that each background
interval contains a single change point at most, leading to an improvement of
the localisation rate. Baranowski et al. [23] propose a change point-like
feature detection method termed the narrowest-over-threshold (NOT) where, at
each recursive iteration, the shortest interval $(s,e]$ over which the
associated max-CUSUM statistic, $\max_{s<k<e}|\mathcal{T}_{s,k,e}(X)|$,
exceeds a given threshold is selected, rather than the interval returning the
largest max-CUSUM. Fryzlewicz [76] proposes WBS2, which iteratively draws
random intervals and produces a complete solution path, i.e. an ordered
sequence of $\mathcal{I}_{1}=\\{1,\ldots,n-1\\}$ according to their importance
measured by the associated CUSUM statistics. Kovács et al. [120] investigate
the seeded binary segmentation (SBS), which generates the search grid
$\mathcal{R}_{n}$ in a deterministic fashion. In Lu et al. [133], a sampling
strategy is investigated in combination with BS and WBS for handling very
large $n$.

In all above, the theoretical investigation is focused on the case of
uncorrelated data, while Cho and Fryzlewicz [44] discuss the usefulness of the
WBS-like strategy in separating the effects of change points and time series
fluctuations in the presence of serial correlations. Finally, we mention the
circular binary segmentation proposed in Venkatraman and Olshen [180] for the
analysis of array CGH data, where the test statistics are tailored for
detecting changes of epidemic nature, where
$f_{\theta_{2j+1}}=f_{\theta_{2j+2}+1}$ for $j=0,\ldots,\lfloor
q_{n}/2\rfloor$ under (1).

####  3.2.2 Moving sum procedures

The moving sum (MOSUM) procedure has been adopted for simultaneously detecting
and locating multiple change points [47, 63, 102]. For the canonical
segmentation problem it scans the data for change points using the statistics
$\mathcal{T}_{s,k,e}(X)$ over a fixed grid
$(s,k,e)\in\mathcal{S}_{\text{M}}(G)$, which is fully determined by the choice
of a bandwidth $G=G_{n}$ as

$\displaystyle\mathcal{S}_{\text{M}}(G)=\left\\{(s,k,e):\,s=k-G,\,e=k+G,\,k=G,\ldots,n-G\right\\}.$
(8)

The search space is of cardinality $|S_{\text{M}}(G)|=O(n)$ since for every
time point $k$, only the local interval $(s,e)=(k-G,k+G)$ is considered; we
sometimes denote that $k\in\mathcal{S}_{\text{M}}(G)$ where there is no
confusion. Eichinger and Kirch [63] propose two criteria for the simultaneous
localisation of the change points whereby each estimator is obtained as a
local maximiser of $|\mathcal{T}_{s,k,e}(X)|,\,k\in\mathcal{S}_{\text{M}}(G)$,
over a sufficiently large interval relative to $G$, at which the MOSUM
statistic exceeds a theoretically motivated threshold.

Messer et al. [140, 141] consider a multiscale extension of the MOSUM
procedure with the search space

$\displaystyle\mathcal{S}_{\text{M}}(\mathcal{G})=\left\\{(s,k,e):\,s=k-G_{h},\,e=k+G_{h},\,k=G_{h},\ldots,n-G_{h};\,h=1,\ldots,H\right\\}$

where $\mathcal{G}=\\{G_{1},\ldots,G_{H}\\}$ denotes a set of bandwidths. The
screening and ranking procedure of Niu and Zhang [144] also adopt a multiscale
MOSUM procedure for candidate generation.

The use of asymmetric bandwidths $\mathbf{G}=(G_{\ell},G_{r})$ with
$\mathcal{S}_{\text{M}}(\mathbf{G})=\\{(s,k,e):\,s=k-G_{\ell},\,e=k+G_{r},\,k=G_{\ell},\ldots,n-G_{r}\\}$
has been investigated by Meier et al. [139]. Cho and Kirch [45] propose the
following scheme for asymmetric bandwidth selection based on the Fibonacci
series $\\{F_{m}\\}$ constructed as $F_{m}=F_{m-1}+F_{m-2},\,m\geq 2$ with
$F_{0}=F_{1}=1$: The set of asymmetric bandwidths is determined as

$\displaystyle\mathcal{H}_{n}=\left\\{(G_{\ell},G_{r}):\,G_{\ell/r}=G_{\min}\cdot
F_{\ell/r},\,1\leq\ell,r\leq
H_{n},\quad\text{and}\quad\frac{\max(G_{\ell},G_{r})}{\min(G_{\ell},G_{r})}\leq
C_{\text{asym}}\right\\},$

with $H_{n}$ chosen such that $G_{H_{n}}<\lfloor n/\log(n)\rfloor$ for some
minimum allowable bandwidth $G_{\min}$ and a fixed constant
$C_{\text{asym}}\geq 1$. The latter constant controls the unbalancedness of
the asymmetric bandwidth $(G_{\ell},G_{r})$ such that the computational
complexity of the multiscale MOSUM procedure involving
$T_{s,k,e}(X),\,(s,k,e)\in\mathcal{S}_{\text{M}}(\mathcal{H}_{n})$ is
$O(n\log(n))$.

The multiscale application of the MOSUM procedure necessitates a pruning
procedure for the removal of conflicting estimators detected for the identical
change points at multiple bandwidths, as well as possibly spurious estimators
detected at small bandwidths.

####  3.2.3 Bottom-up and sequential approaches

There exist data segmentation methods that set out to isolate each change
point by considering the data from finer to coarser scales. Fryzlewicz [75]
propose a method based on the tail-greedy unbalanced Haar (TGUH) transform,
which performs a bottom-up data decomposition using the unbalanced Haar
wavelet basis. Starting from the finest grid
$\mathcal{S}^{(0)}=\\{1,2,\ldots,n-1\\}$, it identifies the regions (defined
by the adjacent elements of the grid) to be merged as where the corresponding
statistics $\left|\mathcal{T}_{s,k,e}(X)\right|$ computed over
$(s,k,e)=(k^{(0)}_{i-1},k^{(0)}_{i},k^{(0)}_{i+1}),\,k^{(0)}_{i}\in\mathcal{S}^{(0)}$
(with $k^{(\ell)}_{0}=0$ and $k^{(\ell)}_{|\mathcal{S}^{(\ell)}|+1}=n$ for all
$\ell\geq 0$) are small, and accordingly update the search grid. Repeatedly
applying the above steps until all $|\mathcal{T}_{s,k,e}(X)|$ are large enough
over
$(s,k,e)=(k^{(\ell)}_{i-1},k^{(\ell)}_{i},k^{(\ell)}_{i+1}),\,k^{(\ell)}_{i}\in\mathcal{S}^{(\ell)}$
for some $\ell$, we obtain an ordering of change point candidates with an
implicit tree-like structure on which model selection is performed. By
greedily selecting the regions to be merged, which is managed by a parameter
controlling their proportion out of the remaining regions, TGUH achieves a
computational complexity of $O(n\log^{2}(n))$. A similar idea of bottom-up
change point analysis has also been explored in the reverse segmentation
proposed by Chan and Chen [35], and the backward procedure of Shin et al.
[167].

The pseudo-sequential procedure of Venkatraman [179] adapts an online change
point detection algorithm to the offline data segmentation problem. The
Isolate-Detect (IDetect) proposed in Anastasiou and Fryzlewicz [4] operates in
a similar vein, sequentially searching for change points from both ends. More
specifically, it scans
$\mathcal{T}_{s,k,e}(X),\,(s,k,e)\in\mathcal{S}_{L}(\ell,r)\cup\mathcal{S}_{R}(\ell,r)$,
where $\mathcal{S}_{L}(\ell,r)$ and $\mathcal{S}_{R}(\ell,r)$ denote the
search spaces containing the intervals expanded from the left to the right,
and those expanded from the right to the left, respectively, for given
$0\leq\ell<r\leq n$, as

$\displaystyle\mathcal{S}_{L}(\ell,r)$
$\displaystyle=\left\\{(s,k,e):\,\ell=s<k<e\leq r\text{ with
}e=m\lambda_{n},\,m\in\mathbb{N}\right\\},$
$\displaystyle\mathcal{S}_{R}(\ell,r)$
$\displaystyle=\left\\{(s,k,e):\,\ell\leq s<k<e=r\text{ with
}s=n-m\lambda_{n},\,m\in\mathbb{N}\right\\},$

where $\lambda_{n}$ denotes a parameter satisfying
$\lambda_{n}\leq\delta_{n}=\min_{1\leq j\leq q_{n}}\delta_{j}$. Starting with
$(\ell,r)=(0,n)$, it iteratively updates $(\ell,r)$ with the previously
detected change point estimators. The choice of $\lambda_{n}$ involves
balancing between the computational complexity $O(n^{2}\lambda_{n}^{-1})$, and
the change point localisation property (smaller $\lambda_{n}$ providing better
guarantee of isolating each change point for their detection and
localisation).

####  3.2.4 Model selection

The methods outlined in Sections 3.2.1–3.2.3 produce a set of candidate change
point estimators $\mathcal{C}$ from scanning the data at multiple scales; some
return a subset of $\mathcal{I}_{1}=\\{1,\ldots,n-1\\}$, while the others
generate a (complete) solution path ordering the elements of $\mathcal{I}_{1}$
according to their importance. For the estimation of the total number and the
locations of the change points, it remains to select the final model from the
set of candidate estimators.

Closely related to the change point testing literature, thresholding is
popularly adopted for model selection in change point detection. Eichinger and
Kirch [63] derive the (distributional) limit behaviour of the MOSUM test
statistic $\max_{k\in\mathcal{S}_{\text{M}}(G)}|\mathcal{T}_{s,k,e}(X)|$ under
the null hypothesis of no change, under general conditions allowing for heavy
tails and serial dependence in $\\{\varepsilon_{t}\\}$ with the bandwidth $G$
satisfying $G\to\infty$ while $G/n\to 0$; the result is extended for the
asymmetric MOSUM statistic in Meier et al. [139]. Messer et al. [140, 141]
approximate the MOSUM statistic by a Gaussian process when $G$ grows linearly
with $n$. With such asymptotic null distributions at hand, we can derive a
theoretically motivated threshold at a chosen significance level and control
for the family-wise error rate.

For methods such as BS, WBS and their extensions, the test statistics
associated with change point estimators are dependent on the previously
detected ones, and thus it is challenging to investigate their asymptotic null
distributions. Instead, the thresholds are often given by a range depending on
$n$, the level of noise and other typically unknown quantities such as
$\min_{j}|d_{j}|$ and $\min_{j}\delta_{j}$, see [4, 23, 74, 75, 179, 185].
Fang et al. [65] provide a detailed analysis of the tail probability of
$\max_{(s,k,e)\in\mathcal{I}_{3}}|\mathcal{T}_{s,k,e}(X)|$ under i.i.d
Gaussianity, which enables the selection of the threshold at a prescribed
significance level.

For a critical value or a threshold to be useful, we need to estimate the
level of noise given by the error variance
$\sigma^{2}=\mathsf{Var}(\varepsilon_{t})$ under independence or the long-run
variance
$\tau^{2}=\mathsf{Var}(\varepsilon_{t})+2\sum_{h=1}^{\infty}\mathsf{Cov}(\varepsilon_{0},\varepsilon_{h})$
when serial dependence is permitted. Several estimators exist for both
$\sigma^{2}$ and $\tau^{2}$ under the model (1) [20, 58, 173], but the
difficulty associated with the estimation of the latter has been well-
documented particularly in the presence of multiple change points [152], and
the former also becomes challenging to estimate when frequent change points
are present. As a remedy, Fryzlewicz [76] proposes the ‘steepest drop to low
levels’ (SDLL) model selection methodology applicable with a complete solution
path ordering $\mathcal{I}_{1}=\\{1,\ldots,n-1\\}$, with thresholding adopted
as a secondary criterion.

Information criteria such as those discussed in Section 3.1.1, have frequently
been adopted for final model selection in combination with the methods
belonging to the local testing category. Fryzlewicz [74] propose to minimise
the strengthened SC, defined in (3) with the penalty function
$p_{n}(\mathcal{A})=\log^{1+\epsilon}(n)\cdot|\mathcal{A}|$ for some small
$\epsilon>0$, along a solution path
$\\{k_{1}\\}\subset\\{k_{1},k_{2}\\}\subset\ldots\subset\\{k_{1},\ldots,k_{N}\\}\subset\mathcal{I}_{1}$
returned by WBS with some pre-determined $N>q_{n}$; the subset that minimises
the criterion is chosen as the final model. A similar approach is also taken
by [4, 23, 144].

Alternatively, Cho and Kirch [45] propose a top-down pruning methodology based
on SC, which searches for the final model $\widehat{\Theta}$ from a set of
candidate change point estimators, say $\mathcal{C}$, according to the
following rules: (i) Adding further estimator to $\widehat{\Theta}$
monotonically increases SC, and (ii) among all subsets satisfying (i),
$\widehat{\Theta}$ attains the minimal cardinality and (if there exist ties)
the minimum SC. This approach gains computationally compared to minimising the
SC exhaustively among all the $2^{|\mathcal{C}|}$ subsets of $\mathcal{C}$,
and achieves consistency in multiple change point estimation under general
assumptions permitting dependence and heavy tails in $\\{\varepsilon_{t}\\}$.
A localised version of the pruning method attaining linear complexity is
proposed for further computational consideration, and it is shown to match the
minimax optimal multiscale separation and localisation rates when applied to
the candidates generated by a multiscale MOSUM procedure. Cho and Fryzlewicz
[44] explore the top-down approach under a parametric modelling assumption on
$\\{\varepsilon_{t}\\}$, which effectively avoids the difficult task of
evaluating the information criterion at a model under-specifying the number of
change points.

Messer et al. [140, 141] consider a bottom-up merging method for the
multiscale MOSUM procedure: Accepting all the estimators from the smallest
bandwidth, it proceeds to coarser scales and only accepts a change point
estimator if its detection interval does not contain any estimators that are
already accepted. A similar strategy, named the local segmentation, has also
been considered in Chan and Chen [35], which permits asymmetric bandwidths.

###  3.3 An overview of change point detection methodologies

Table 1: Comparison of change point detection methodologies on their detection
lower bound and the separation and localisation rates derived under i.i.d.
(sub-)Gaussianity, where $d_{n}=\min_{1\leq j\leq q_{n}}|d_{j}|$ and
$\delta_{n}=\min_{1\leq j\leq q_{n}}\delta_{j}$. Also, we provide the
computational complexity of different methods with $N$ denoting the maximum
allowable number of change points where relevant, and list their software
implementations. The results reported here for BS and WBS are taken from [43,
188].

|  | Detection lower bound | Localisation | Computational |
---|---|---|---|---|---
|  | $\Delta_{n}$ | Separation rate | $w_{j}$ | Rate | complexity | Implementations
$\ell_{0}$- | [73] | $\min_{j}d_{j}^{2}\delta_{j}$ | $\log(n/\delta_{n})$ | $d_{j}^{2}$ | $\log(q_{n})$ | $O(n^{2})$ | [111, 49, 158]
penalisation | [185] | $d_{n}^{2}\delta_{n}$ | $\log(n)$ | $d_{j}^{2}$ | $\log(n)$ | $O(n^{2})$ |
$\ell_{1}$- | [84] | – | – | 1 | $\log^{2}(n)$ | $O(N^{3}+$ | –
penalisation | [130] | – | – | $d_{n}^{2}$ | $\log(n)\log\log(n)$ | $Nn\log(n))$ |
MCPS | [72] | $d_{n}^{2}\delta_{n}$ | $\log(n/\delta_{n})$ | $d_{n}^{2}$ | $\log(n)$ | $O(n^{2})$ | [151, 127]
| [129] | $d_{n}^{2}\delta_{n}$ | $q_{n}\log(n)$ | $d_{n}^{2}$ | $q_{n}\log(n)$ | – |
BS | [74] | $d_{n}^{2}\delta_{n}$ | $n^{3}\delta_{n}^{-5/2}\log(n)$ | $d_{n}^{2}$ | $(n/\delta_{n})^{5}\log(n)$ | $O(n\log(n))$ | [111]
WBS | [74] | $d_{n}^{2}\delta_{n}$ | $(n/\delta_{n})^{4}\log(n)$ | $d_{j}^{2}$ | $(n/\delta_{n})^{4}\log(n)$ | $O(n|\mathcal{R}_{n}|)$ | [5]
| [185] | $d_{n}^{2}\delta_{n}$ | $\log(n)$ | $d_{j}^{2}$ | $\log(n)$ | with |
NOT | [23] | $d_{n}^{2}\delta_{n}$ | $\log(n)$ | $d_{j}^{2}$ | $\log(n)$ | $(n/\delta_{n})^{2}/|\mathcal{R}_{n}|\to 0$ |
MOSUM | [63] | $d_{n}^{2}\delta_{n}$ | $\log(n/\delta_{n})$ | $d_{j}^{2}$ | $\log(q_{n})$ | $O(n)$ | [138]
| [45] | $\min_{j}d_{j}^{2}\delta_{j}$ | $\log(n)$ | $d_{j}^{2}$ | $\log(q_{n})$ | $O(n\log(n))$ |
| [35] | $d_{n}^{2}\delta_{n}$ | $\log(n/\delta_{n})$ | $d_{j}^{2}$ | $\log(n)$ | $O(n\log(n))$ |
IDetect | [4] | $d_{n}^{2}\delta_{n}$ | $\log(n)$ | $d_{j}^{2}$ | $\log(n)$ | $O(n^{2}/\delta_{n})$ | [5, 3]
TGUH | [75] | $d_{n}^{2}\delta_{n}$ | $\log^{2}(n)$ | $d_{n}^{2}$ | $\log^{2}(n)$ | $O(n\log^{2}(n))$ |

Table 1 provides a comprehensive overview of change point methodologies
discussed in Sections 3.1–3.2, which expands upon Table 1 of Cho and Kirch
[45]. They are compared on their theoretical properties such as how the
detection lower bound is formulated, their separation and localisation rates
under i.i.d. (sub)-Gaussianity (according to Definition 2.1 and (2)) and
computational complexity, and their software implementations are listed where
available.

####  3.3.1 Numerical performance

We briefly discuss the practical performance of the representative change
point methods in Table 1, based on the numerical experiments conducted in [45]
using their respective implementations listed in the table; see also Fearnhead
and Rigaill [67] for an extensive comparison of data segmentation algorithms
based on their numerical performance, and the vignette accompanying the R
package breakfast [5] comparing various CUSUM-based candidate generation and
model selection methods.

We emphasize that different algorithms excel at different performance
criteria, and their performance vary with different test signals. For
instance, dynamic programming algorithms for minimising the
$\ell_{0}$-penalised cost functions, such as [110] and [135] (implemented in
[111] and [158], respectively), take a fraction of a second in processing long
data sequences ($n\geq 2\times 10^{4}$), followed by the multiscale MOSUM
procedure with bottom-up merging [35, 140]; the SDLL model selection method of
[76] is well-suited to detect a large number of frequent change points; FDRseg
[128] shows favourable performance for relatively short test signals; TGUH
[75] tends to incur few false positives even when change points are sparse
while $n$ is large. Between those methods that employ information criteria for
model selection, the localised pruning proposed in [45] outperforms the
sequential minimisation along the solution path considered in [74] in terms of
correctly estimating the number of change points. Overall, the localised
pruning methodology shows well-rounded performance in combination of either
MOSUM- or CUSUM-based candidate generating procedures on a variety of test
signals with both sparse and dense change points.

These observations apply to the case of i.i.d. Gaussian errors. Most of the
methods considered above are not easily extended to cope with heavy-tailed or
serially correlated $\\{\varepsilon_{t}\\}$, as their tuning parameters are
specifically tailored for the i.i.d. (sub-)Gaussian setting. The localised
pruning, on the other hand, provides a framework for selecting a
theoretically-motivated penalty in the SC that is well-justified in the
numerical experiments where $\\{\varepsilon_{t}\\}$ are generated as i.i.d.
random variables following $t_{5}$-distributions, or AR($1$) processes with
both strong and weak autocorrelations.

###  3.4 Inference for the multiple change point problem

In this section, we review the literature on inference for multiple change
points in the context of the canonical segmentation problem. For a review of
the literature in the case of a single change point, see Jandhyala et al.
[106].

In order to quantify the uncertainty in the detection of multiple change
points, MCPS methods (see Section 3.1.3) such as SMUCE [72] and FDRseg [128]
allow for controlling the probability of over-estimating the number of change
points in terms of family-wise error rate or false discovery rate. Eichinger
and Kirch [63] provide the asymptotic null distribution of the test statistic
of the single-scale MOSUM procedure, namely that of
$\max_{(s,k,e)\in\mathcal{S}_{\text{M}}(G)}|\mathcal{T}_{s,k,e}(X)|$ (see (8))
when there is no change point present, under general assumptions permitting
heavy tails and serial dependence in $\\{\varepsilon_{t}\\}$. Using this
distribution, we can test whether or not there exists a mean shift within the
$G$-environment at each time point $k$, where the thus-obtained $p$-value
controls the family-wise error rate by construction. There also exist
resampling methods for change point tests in the i.i.d. setting which generate
better small sample approximations of the p-values, see Antoch and Hušková [8]
and also Hušková [94] for a survey. For the case of i.i.d. Gaussian errors,
Fang et al. [65] give the approximation of the tail probability of
$\max_{0\leq s<k<e\leq n}|\mathcal{T}_{s,k,e}(X)|$ (maximum of the CUSUM
statistics over all possible triplets $(s,k,e)$) under the null hypothesis of
no change points, which in turn provides an approximation of the probability
of a false positive error.

Post-selection inference methods exist for the change point problem when
$\\{\varepsilon_{t}\\}$ are i.i.d. Gaussian, where the interest lies in
testing for the equality of the mean around estimated change point locations
conditional on their estimation process, see e.g. Hyun et al. [104] and Jewell
et al. [107]. Thanks to the conditioning sets being polyhedral in the case of
BS and its variants, or via efficient characterisation of the conditioning set
afforded by the functional pruning technique [135] for minimising the
$\ell_{0}$-penalised objective functions (Section 3.1.1), the corresponding
$p$-values can be computed from truncated normal distributions; however, their
interpretation is involved and this approach requires further correction for
multiple testing. Fryzlewicz [77] considers an alternative framework called
post-inference selection under which the interest lies in identifying
intervals containing at least one change points at a given global significance
level without locating them.

In a more classical sense, there are also a few methods for quantifying the
uncertainty about the locations of change points. Eichinger and Kirch [63]
derive the asymptotic distribution of the MOSUM-based change point estimators
in the case of local changes (i.e. $d_{j}\to 0$), and Cho and Kirch [46] show
that the corresponding limit for the fixed change case (i.e. $d_{j}$ constant)
depends on the unknown distribution of $\\{\varepsilon_{t}\\}$, extending
similar observations made in the AMOC setting for CUSUM-based estimators [7,
9]. This motivates constructing bootstrap confidence intervals around change
points, as proposed by [7, 9] in the case of i.i.d. errors and by [96, 97] in
time series settings, all for the AMOC problem. Meier et al. [139] outline the
bootstrap construction of pointwise and uniform confidence intervals for
multiple change points based on the MOSUM procedure, and Cho and Kirch [46]
show its theoretical validity for both local and fixed changes in the presence
of i.i.d. (not necessarily Gaussian) $\\{\varepsilon_{t}\\}$.

In addition, MCPS [72, 128] provide a confidence set for all candidate signals
from which confidence intervals around the change points can be obtained.
Using the inverse relation between confidence intervals and hypothesis tests,
[65] describe how approximate confidence regions can be generated.

##  4 Extensions to more complex problems

In this section, we discuss several avenues for extending the methodologies
from Section 3 to more complex change point problems beyond that of detecting
change points in the mean of univariate data sequence under (1), which include
high-dimensional change point analysis. While some literature in these
directions already exists, it is far scarcer than the literature on the
canonical data segmentation problem. We argue that a thorough understanding on
theoretical and computational performance of different data segmentation
methods for the simpler problem in the univariate setting, forms the basis for
the methodological development in more complex situations.

In Section 4.1, we discuss that many tests for changes in the stochastic
properties other than the mean (mostly in the AMOC scenario), are closely
related to those proposed for detecting a change in the mean of univariate
data. Therefore, data segmentation algorithms that have proven useful for the
canonical segmentation problem can be adapted for complex change point
detection problems in combination with such tests. These combined
methodologies are expected to deliver satisfactory or even optimal
performance, although they require more sophisticated mathematical analysis
which in turn necessitates an in-depth understanding of both parts to be
combined.

In Section 4.2, we give a brief overview of the state-of-the-art methodologies
for high-dimensional change point problems. Focusing on the problem of change
point detection in the mean of high-dimensional panel data, we show that the
challenges in dealing with high dimensionality are orthogonal to those arising
from the presence of multiple change points.

###  4.1 Extensions beyond detecting mean changes under Gaussianity

First we provide a brief review of the existing literature on the detection of
multiple change points in stochastic properties other than the mean, in
univariate or multivariate data sequences. Under parametric models for linear
and non-linear time series, $\ell_{0}$\- [17, 53, 54] and
$\ell_{1}$-penalisation [26, 36] methods, the MOSUM procedure based on
likelihood ratio statistic [193] and BS [78] have been adopted for detecting
change points in the parameters that vary over time in a piecewise constant
manner. Data segmentation under piecewise polynomial (mostly linear) models
have been addressed in [23, 69, 134, 175], also adopting the algorithms
discussed in Section 3. For nonparametric change point analysis, BS [137], WBS
[147] and $\ell_{0}$-penalisation [12, 80, 196] have been combined with
various methods for measuring distributional changes, and some computational
efforts have been made to improve the dynamic programming algorithms for the
methods in the latter category [33, 86]. In the time series setting, methods
based on local periodograms [154] and wavelet transform [41] have been
developed in combination with the MOSUM procedure and BS, respectively.

As seen in the above, data segmentation problems beyond that of mean change
point detection require a methodology appropriate for revealing and measuring
the time-varying characteristics of the data, which is of separate concern
from handling multiple change points. We can tackle complex data segmentation
problems by combining suitable methodologies addressing the two different
aspects. This in turn requires an in-depth understanding of both strengths and
weaknesses of the procedures for the canonical data segmentation problem as
discussed in Section 3, in addition to understanding how extensions beyond
detecting mean changes are achieved. We will use the remainder of this section
to focus on the latter aspect and provide a short overview of the techniques
developed mainly in the AMOC setting.

The _effective dimensionality_ of data segmentation problems is given by the
number of unknown parameters such that even for univariate observations, the
effective dimensionality of a given problem can be large, see e.g. Kirch and
Kamgaing [113] for an example for testing for parameter stability in non-
linear autoregressive models by means of a semiparametric approach based on
neural networks, which involves a large number of parameters. To make the
problem even more difficult, statistics for revealing changes (e.g. obtained
after a suitable data transformation) are often not independent even if the
observed data is. Bücher et al. [32] consider a test for detecting changes in
the serial dependence using a copula approach, and discuss how the result from
such a test can be combined with those from change point tests for
distributional changes (all based on resampling methodology) even though these
tests are dependent. Kirch et al. [116] describe in detail how testing for
changes in moderately large linear vector autoregressive processes becomes a
high-dimensional problem, and provide discussions on how to resolve the
complications arising from the high dimensionality. This shows that techniques
for high-dimensional change point analysis as discussed later in Section 4.2,
are also of relevance for data segmentation under complex time series models.

#### Data transformation

Some complex change point problems can be reduced to that of detecting changes
in the mean by adopting a suitable data transformation where typically, the
dimensionality of the transformed data is larger (sometimes much larger) than
that of the original observation sequence. For example, the problem of
detecting changes in the covariance of $p$-dimensional data
$\mathbf{X}_{t}=(X_{1t},\ldots,X_{pt})^{\top}$ (under the assumption of a
constant mean), can be transformed to that of detecting changes in the mean of
$p(p+1)/2$-dimensional data by considering the vector consisting of cross-
products, i.e. $\mathbb{X}_{t}=(X_{it}X_{jt}:\,1\leq i\leq j\leq p)^{\top}$.
Clearly, the effective dimensionality is quadratic in the dimension of the
original data. Also, the components of $\mathbb{X}_{t}$ are not independent
and the dependence is not negligible. Such a transformation has been adopted
for change point analysis in the covariance structure of multivariate [16],
functional [170] and high-dimensional [169] data, and Cho and Fryzlewicz [42]
propose a similarly motivated wavelet transform for the segmentation of high-
dimensional time series in the second-order structure.

#### Generalised method of moments

The above approach is applicable only if the parameters of interest, which are
subject to change over time, can be expressed as the expected values of an
appropriately transformed data, i.e. as some moments. For most parametric
models, however, this is not the case. For example, suppose that $\\{X_{t}\\}$
follows a (centered) linear AR model of order one, i.e.

$\displaystyle X_{t}=\alpha X_{t-1}+e_{t},\quad
e_{t}\sim\text{WN}(0,\sigma^{2}),\quad t=1,\ldots,n.$ (9)

Then, the AR parameter $\alpha$ cannot be written as any moment after a simple
data transformation. However, it can be written as a generalised moment,
namely the quotient $\mathsf{E}(X_{t}X_{t-1})/\mathsf{E}(X_{t}^{2})$, as given
by the well-known Yule-Walker equation and moreover, can be estimated
(locally) from the data by using the method of moments. This observation gives
rise to the following two approaches for change point analysis.

The Wald approach compares directly the distance between the estimators
obtained from different stretches of the data: At location $k$, we evaluate
$d(\widehat{\beta}_{0:k},\widehat{\beta}_{k:n})$ where $d$ is some measure of
distance, and $\widehat{\beta}_{a:b}$ denotes the estimator for the parameter
of interest $\beta$ obtained from the data stretch $\\{X_{t},\,a<t\leq b\\}$.
The Wald approach leads to good performance if the parameters are identifiable
and the local estimators can be obtained without resorting to numerical
algorithms. On the other hand, its application may not be appropriate when
there exist many (local) optima of the objective function for parameter
estimation. Such a situation arises e.g. for neural networks, where different
parameters describing the same or very similar regression functions might be
far from each other in the parameter space. Further, this is particularly
problematic if the estimators can only be obtained numerically. Even when the
objective function does not have multiple local maxima, if it is relatively
flat around the true parameter, it can be misleading to gauge the distance
between the estimators of the parameters instead of the processes that they
describe.

A score-type approach is more robust in this respect and is closely related to
the CUSUM statistic described in Section 3.2. In contrast to simple data
transformations as described previously, the transformations adopted in the
score-type approach often involve the (local) parameter estimators. Let us
illustrate this by re-visiting the example of a linear AR(1) time series (9)
in the AMOC situation, where the score-type statistic is given by

$\displaystyle\frac{1}{\sqrt{n}}\max_{2\leq
k<n}\left|\sum_{t=2}^{k}X_{t-1}(X_{t}-\widehat{\alpha}_{0:n}X_{t-1})\right|,$
(10)

where $\widehat{\alpha}_{0:n}$ denotes an estimator of the AR parameter based
on the _full_ data set. Some authors suggest to use partial sums of estimated
residuals; however, the thus-constructed test has power only against some
alternatives, namely those leading to changes in the mean of estimated
residuals (see e.g. [116]). The statistic in (10) bears clear resemblance to
the CUSUM statistic for mean change detection (written below with slightly
different location-dependent weights from Section 3.2 for better comparison):

$\displaystyle\frac{1}{\sqrt{n}}\max_{1\leq
k<n}\left|\sum_{t=1}^{k}(X_{t}-\bar{X}_{0:n})\right|.$

Here, $\bar{X}_{0:n}$ can be regarded as an estimator of the unknown mean
based on the full sample, analogously to $\widehat{\alpha}_{0:n}$ being the
global estimator of $\alpha$.

There are many other examples where the score-type statistics are adopted for
change point analysis, including the tests based on likelihood ratio or
classical $M$-estimators (see the next subsection on robust change point
analysis) and those for changes in linear (auto)regression [103, 116],
integer-valued time series such as Poisson autoregressive processes [112] and
even regression models based on neural networks [113]. In all of the above,
the test statistics are based on partial sums

$\displaystyle\frac{1}{\sqrt{n}}\max_{1\leq
k<n}\left\|\sum_{t=1}^{k}F(\mathbf{Y}_{t},\widehat{\beta}_{0:n})\right\|\quad\text{where}\quad\sum_{t=1}^{n}F(\mathbf{Y}_{t},\widehat{\beta}_{0:n})=0,$

where $F$ is a suitable estimating function and $\widehat{\beta}_{0:n}$ the
global estimator based on the full sample from this estimating function. The
norm $\|\cdot\|$ often involves the unknown covariance matrix of
$F(\mathbf{Y}_{t},\beta)$ or an appropriate estimator thereof. In many
instances, $\mathbf{Y}_{t}$ is not the original observation sequence; e.g. in
the above AR($1$) example, $\mathbf{Y}_{t}$ contains lagged observations. This
shows that effectively, one is looking for mean changes in the pseudo-data
$F(\mathbf{Y}_{t},\widehat{\beta}_{0:n})$, whose dimension is equal to the
number of unknown parameters. For linear models, the Wald and the score-type
statistics are equivalent in the AMOC setting, see Kirch and Kamgaing [112].
In non-linear situations, this does not hold in small samples but does so
asymptotically in well-behaved situations.

The Wald approach can be extended to multiple change point detection e.g. in
combination with the MOSUM procedure by comparing the distance between local
estimators over moving windows. Alternatively, the corresponding moving sum
score statistic with a local estimator can be used. However, both suffer from
the problem of having to calculate $O(n)$ local estimators which, as noted
above, brings in further numerical challenges when there does not exist an
analytic solution to the estimating function. Using a slightly modified score-
type statistic replacing the local estimator with a global _inspection
parameter_ , say $\widetilde{\beta}$ (which may be data-dependent), alleviates
this issue but typically, there is no guarantee that all changes are
detectable as changes in the mean of $F(\mathbf{Y}_{t},\widetilde{\beta})$.
Reckrühm [155] shows that even so, at least one change is made detectable
therein, which naturally leads to adopting several of such inspection
parameters. Some first results have been obtained by Reckrühm [155] and Kirch
and Reckrühm [115], on the combined methodology of the MOSUM procedure and the
use of estimating functions for the detection of multiple change points in
general settings.

#### Robust change point analysis

The framework of generalised method of moments also prominently includes
robust tests for changes in the mean or regression parameters (often known as
$M$-estimation in this context). Selecting a suitable estimating function $F$
(related to what is known as a score function), one can obtain not only more
robust estimators of the parameters of interest but also more robust methods
to test for their changes. For example, under the mean change model as in (1)
with $q_{n}\leq 1$, choosing
$F(X,\beta)=\mathbb{I}_{\\{X>\beta\\}}-\mathbb{I}_{\\{X<\beta\\}}$ (with
$\beta$ corresponding to $f_{0}=\mathsf{E}(X_{t})$ when there exists no change
point) results in $\widehat{\beta}_{0:n}$ that coincides with the median where
$\sum_{t=1}^{n}F(X_{t},\widehat{\beta}_{0:n})=0$. Such an approach is also
known as $L_{1}$-procedure and discussed e.g. in Hušková [91] for detecting
changes in linear regression. Theoretical investigation into change point
detection procedures based on $M$-estimation can be found in [6, 91, 92, 93,
101] under the i.i.d. assumption, and in [98, 153] for dependent data. A more
detailed survey of the literature on this topic, including references on
a-posteriori as well as sequential change point testing, is given in [95]. The
paper includes some discussions on rank-based tests as well, which is an
alternative approach to achieve robustness in change point testing. One such
an example is the generalisation of the Wilcoxon rank sum test to the change
point setting which is a special case of a (non-degenerate) $U$-statistic.
$U$-statistics are adopted for the estimation of a range of different
parameters far beyond the mean, and also used in testing for the stability of
the corresponding parameters. Importantly, they involve a data transformation
that translates the problem at hand into that of mean change point testing. To
elaborate, the Hoeffding decomposition is an important tool to prove
asymptotic results for $U$-statistics and shows equality between the original
statistic and a sum of i.i.d. random variables (obtained from the Hajék
projection) plus an asymptotically negligible remainder. Change point tests
based on $U$-statistics were first proposed in the i.i.d. setting [50, 70, 81]
and then generalised to weakly [57] and even long-range dependent data [29,
56]. Extensions based on $U$-quantiles are also available [55, 181]. Some
first results for the data segmentation problem based on $U$-statistics
already exist [59, 146], and Fearnhead and Rigaill [67] investigate the
minimisation of penalised costs based on $M$-estimation via dynamic
programming for change point analysis in the presence of outliers.

#### Asymptotic embeddings

Another extension is based on asymptotic results for partial sum processes
such as functional central limit theorems or (strong) invariance principles
[28, 82, 87, 117, 118, 121, 168]. Most importantly, such results enable the
investigation into change point analysis of stochastic processes including
multivariate Wiener processes with drift, renewal processes or integrated
diffusion processes. A univariate version of such a model was introduced by
Horváth and Steinebach [90] for change point testing against the AMOC
alternative, and has been extended to multiple change point problems in Kühn
[122] where the consistency is established for the estimator of the number of
change points based on the SC described in Section 3.1.1. For the specific
example of univariate renewal processes, Messer et al. [141] propose a
multiscale MOSUM procedure with bandwidths linear in sample size (see Sections
3.2.2 and 3.2.4). Kirch and Klein [114] investigate a MOSUM procedure in the
general multivariate framework adopting both linear and sub-linear bandwidths
and derive localisation rates for the change point estimators that are shown
to be minimax optimal when there are a finite number of change points; when
there are an unbounded number of change points, this remains to be valid for
Wiener processes with drift. Beyond such settings, minimax optimality in the
localisation rate has not been established to the best of our knowledge (see
also Section 2).

#### Nonparametric change point analysis

Truly nonparametric change point tests do not have obvious connections to the
canonical mean change point detection problem. These tests often involve
appropriately weighted integrals over differences of the estimators of the
nonparametric quantity of interest, such as those based on functionals of two-
sample rank-based test statistics [191], empirical characteristic function
[99, 100], and kernel estimators of nonparametric conditional mean functions
[142] among others. In principle, local test methods for the canonical data
segmentation problem discussed in Section 3.2, such as (W)BS or the MOSUM
procedure, can be adapted to accommodate such tests, since they are based on
localised applications of tests designed for the AMOC setting. Application of
the global optimisation approaches to nonparametric settings is more involved,
although some attempts exist [196].

###  4.2 High-dimensional change point analysis

Recent years have seen a surge of interest in the development of change point
methodologies for high-dimensional data including functional and panel data
and networks, with many papers addressing the problem of change point testing
in the mean of panel data, see e.g. Sections 7 and 8 of the review paper by
Horváth and Rice [89]. In this section, our aim is to show that the challenge
due to high dimensionality of the data is orthogonal to that due to the
presence of multiple change points in the following sense:

  1. (i)

As argued in Section 2, the goal of the canonical data segmentation problem is
to achieve consistency in multiple change point detection even in difficult
situations arising from the multiscale nature of the change points (see
Definition 2.1 (a)). In particular, the interplay between the spacing between
change points,
$\delta_{j}=\min(\theta_{j}-\theta_{j-1},\theta_{j+1}-\theta_{j})$, and the
magnitude of changes, $|d_{j}|$, in their detectability is well-understood
under (1). Accordingly, the methodological challenge lies in isolating each
change point within an interval that is long enough for its detection and
localisation.

  2. (ii)

In high-dimensional change point problems, the main question is how to boost
the signal (on each change) across large dimensions. Adopting a minimax-
viewpoint, this is closely related to the choice of the norm adopted for
measuring the cross-sectional size of the change, which is highly relevant in
high-dimensional settings since, unlike in univariate or even multivariate
situations, standard norms are no longer equivalent.

Clearly, these two aspects, multiple change point detection and high-
dimensional change point analysis, merit separate attention when developing a
methodology that is most suitable for the problem at hand. There already exist
papers addressing the problem of multiple change point detection in high-
dimensional settings through combining the data segmentation algorithms for
the canonical data segmentation problem with methods for cross-sectional
aggregation of information on changes. We provide an incomplete review of the
literature below.

The application of the BS algorithm has been investigated in panel data
segmentation problems based on first- [40] and second-order [42] properties,
as well as under a factor model [24]. The WBS algorithm has been adopted for
multiple change point detection in the mean [188] and the covariance [186] of
high-dimensional panel data in combination with data-driven projections, and
also adopted in regression settings [183]. Chu and Chen [48] and Liu and Chen
[132] propose graph-based change point tests for non-Euclidean and possibly
high-dimensional data, and the latter paper heuristically discusses their
extensions to data segmentation problems in combination with BS and WBS. Chen
et al. [39] adopt the MOSUM procedure for panel data segmentation in the mean,
and a MOSUM-type screening strategy has also been adopted in Zhao et al. [195]
for change point detection in dynamic networks. The $\ell_{0}$-penalisation
method has been adopted in parametric settings such as regression [109, 126]
and vector autoregressive [184] models and the $\ell_{1}$-penalisation method,
together with an information criterion-based model selection, has been applied
to high-dimensional time series segmentation under vector autoregressive
models [22, 163].

We further elaborate on the issue discussed in (ii) above by focusing on the
problem that has seen the most development, namely the problem of detecting
changes in the mean of panel data under the following model:

$\displaystyle
X_{it}=f_{it}+\varepsilon_{it}=f_{i0}+\sum_{j=1}^{q_{n}}d_{ij}\cdot\mathbb{I}_{t\geq\theta_{j}+1}+\varepsilon_{it},\quad
i=1,\ldots,p,\,t=1,\ldots,n.$ (11)

It extends the canonical model (1) to the panel data setting with the vector
$\mathbf{d}_{j}=(d_{ij},\ldots,d_{p})^{\top}$ denoting the change in the mean
of $\mathbf{X}_{t}=(X_{1t},\ldots,X_{pt})^{\top}$ at $t=\theta_{j}$, and
$\bm{\varepsilon}_{t}=(\varepsilon_{1t},\ldots,\varepsilon_{pt})^{\top}$ is
assumed to satisfy $\mathsf{E}(\bm{\varepsilon}_{t})=\mathbf{0}$ and
$\mathsf{Cov}(\bm{\varepsilon}_{t})=\bm{\Sigma}$. Unlike in the multivariate
setting, the dimensionality of the data $p=p_{n}$ depends on the sample size
$n$ and is even allowed to increase faster than $n$.

Detectability of a change point depends on the magnitude of the corresponding
change, and selecting a norm for measuring the magnitude of $\mathbf{d}_{j}$
effectively corresponds to modelling the (cross-sectional) type of a change
for which the proposed change point methodology is particularly tailored.
High-dimensional efficiency of change point tests, as proposed in Aston and
Kirch [14], relates to the separation rate between detectable and undetectable
changes. The norms associated with the high-dimensional efficiency of
different methods proposed in the existing literature indeed vary: Methods
designed for detecting sparse changes (where
$\|\mathbf{d}_{j}\|_{0}:=\sum_{i=1}^{p}\mathbb{I}_{|d_{ij}|>0}\ll p$) such as
those proposed in Jirak [108], Cho and Fryzlewicz [42], Wang and Samworth
[188], Chen et al. [39] and the scan statistic of Enikeeva and Harchaoui [64],
are associated with the $\ell_{\infty}$-norm (sometimes implicitly so via
$\|\mathbf{d}_{j}\|/\sqrt{\|\mathbf{d}_{j}\|_{0}}$), while the methods from
Horváth and Hušková [88], Wang et al. [187] and the linear statistic of
Enikeeva and Harchaoui [64] are associated with the $\ell_{2}$-norm, see Table
2 for a summary which extends Table 1 of Cho [40].

Table 2: Comparison of high-dimensional change point detection methods for the problem (11) on their high-dimensional efficiency [14] when $q_{n}=1$, $\min(\theta_{1},n-\theta_{1})\geq cn$ for some $c\in(0,1/2]$ and $\bm{\Sigma}$ is diagonal with all the variances of the same order, i.e. $0<\sigma^{2}_{\min}\leq\mathsf{Var}(\varepsilon_{it})\leq\sigma^{2}_{\max}<\infty$ for all $i=1,\ldots,p$. The efficiency, denoted by $\mathcal{E}(\mathbf{d}_{1})$, indicates that the corresponding procedure has asymptotic power one if $\sqrt{n}\mathcal{E}(\mathbf{d}_{1})\to\infty$. By $L_{n,p}$, we denote a term logarithmic in $n$ and/or $p$ which varies from one instance to another. [14]: oracle | ${\|\mathbf{d}_{1}\|}$ |  [14]: random | ${p^{-1/2}\|\mathbf{d}_{1}\|}$
---|---|---|---
[88, 187] | ${p^{-1/4}\|\mathbf{d}_{1}\|}$ | [42, 108, 39] | ${L_{n,p}^{-1}\|\mathbf{d}_{1}\|_{\infty}}$
[64]: linear | ${(p^{1/4}L_{n,p})^{-1}\|\mathbf{d}_{1}\|}$ |  [64]: scan, [188] | ${(\|\mathbf{d}_{1}\|_{0}L_{n,p})^{-1/2}\|\mathbf{d}_{1}\|}$

Minimax optimality is also linked to the choice of norm, in the sense that
minimax optimality of a given procedure with respect to a norm indicates that
the procedure is optimal in the worst possible case defined by that particular
norm. On the other hand, this does not provide much information as to how the
procedure performs in the worst case scenarios defined with different norms.
For example, the test proposed by Horváth and Hušková [88] is minimax optimal
with respect to the $\ell_{2}$-norm, when the panel is spatially independent
and all variances are of the same order (in the sense described in Table 2),
see the discussion below Theorem 2.1 of [14]. The test statistic proposed
therein increases the signal-to-noise ratio (while controlling for the size)
by summing up squared change point statistics; as more cross-sectional
components are considered, the signal increases according to the squared
$\ell_{2}$-norm, i.e. linear in the number of components with a change,
whereas the noise only increases as $\sqrt{p}$ due to the central limit
theorem applicable under the spatial independence assumption. However, it does
not adapt to the sparsity of change or match the minimax optimal rate with
respect to the $\ell_{\infty}$-norm; we refer to Liu et al. [131] where the
authors show the presence of a phase transition boundary for the sparsity in
the minimax rate of the high-dimensional change testing problem under (11)
(i.e. $q_{n}\leq 1$).

The difficulty in high-dimensional data analysis is that spurious low-
dimensional signals appear simply by chance, another flavour of the curse of
dimensionality which needs to be accounted for in any data science problem.
Under (11) with a single change point, the direction of a change,
$\mathbf{d}_{1}$, is a one-dimensional object such that the projection of
$\mathbf{X}_{t}$ with respect to the ‘oracle’ projection vector
$\mathbf{p}_{\text{o}}=\bm{\Sigma}^{-1}\mathbf{d}_{1}$ yields the optimal
signal-to-noise ratio, see Proposition 3.3 of [14]. In practice, however,
neither $\mathbf{d}_{1}$ nor $\bm{\Sigma}$ are known, and maximising over all
possible projections $\mathbf{p}\in\mathbb{R}^{p}$ will lead to too large a
noise level due to the above observation. Random projections (independent of
the data) have been considered as an alternative, see Steland [169] addressing
the problem of change point testing in the covariance structure. However, this
is at the cost of the loss of detection power as illustrated by the high-
dimensional efficiency of such random projections, see Table 2 which shows
that a random projection is a magnitude of $p^{-1/2}$ worse than oracle
efficiency when $\bm{\Sigma}$ is a diagonal matrix, and also Theorem 3.5 of
[14].

Data-driven projections such as those proposed in [39, 42, 64, 188] can keep
the increased noise level at bay, by effectively working under the sparsity
assumption on $\mathbf{d}_{j}$ and consequently considering only a subset of
all possible projections. This comes at the cost of decreased high-dimensional
efficiency when the sparsity assumption is not met, compared to the oracle
projection with respect to $\mathbf{p}_{\text{o}}$ or the $\ell_{2}$-norm
minimax optimal procedures such as [88, 187].

Compared to the panel data setting, change point analysis in functional data
is benefited by the additional structure implied by the assumption of
observing a random function, which helps lifting part of the curse of
dimensionality. Some approaches [13, 27] to the problem of detecting changes
in the mean function are based on dimension reduction e.g. via functional
principal component analysis. Another line of research proposes ‘fully
functional’ procedures [18, 166] in the sense that they do not employ any
dimension reduction. Stoehr et al. [170] propose a compromise between the two
approaches in the context of change point detection in the covariance
structure.

##  5 Conclusions

In this paper, we first review and compare different approaches to the
canonical segmentation problem where the aim is to estimate the number and the
locations of multiple change points in the mean of univariate data. In Section
3.3, we provide an overview of representative methodologies comparing them
according to the theoretical framework given in Section 2, and briefly comment
on their numerical performance based on comparative simulation studies on a
range of test signals.

In the second part of the paper, we give a survey on topics such as change
point analysis beyond the detection of mean changes under Gaussianity (Section
4.1), and high-dimensional change point analysis (Section 4.2). In Section
4.1, we argue that change point tests developed for more complex problems are
closely related to the mean change point problem and make the connection
transparent. As discussed in Section 2, some of the methods for the canonical
data segmentation problem are based on localised applications of the tests for
the AMOC alternative, and thus can be applied to more complex change point
problems in combination with corresponding tests. Clearly, theoretical
underpinnings of the combined methodology depend on those of the individual
components. In Section 4.2, we show that in high-dimensional change point
analysis, challenges arising from the high dimensionality are orthogonal to
those arising from the presence of multiple change points and, based on in-
depth understanding of the component problems, methods addressing individual
aspects can be combined to best address the given problems. Finally, combining
the elements from the three fields opens up a new avenue for future research,
namely the development of statistical methodologies for complex, high-
dimensional data segmentation problems.

## References

  * Adams and Heard [2016] Niall M Adams and Nicholas Heard.  _Dynamic Networks and Cyber-security_ , volume 1.  World Scientific, 2016.
  * Aminikhanghahi and Cook [2017] Samaneh Aminikhanghahi and Diane J Cook.  A survey of methods for time series change point detection.  _Knowledge and Information Systems_ , 51:339–367, 2017\.
  * Anastasiou and Fryzlewicz [2018] Andreas Anastasiou and Piotr Fryzlewicz.  _IDetect: Detecting multiple generalized change-points by isolating single ones_ , 2018.  URL https://CRAN.R-project.org/package=IDetect.  R package version 1.0.
  * Anastasiou and Fryzlewicz [2021] Andreas Anastasiou and Piotr Fryzlewicz.  Detecting multiple generalized change-points by isolating single ones.  _Metrika_ , pages 1–34, 2021.
  * Anastasiou et al. [2021] Andreas Anastasiou, Yining Chen, Haeran Cho, and Piotr Fryzlewicz.  _breakfast: Methods for Fast Multiple Change-Point Detection and Estimation_ , 2021.  URL https://CRAN.R-project.org/package=breakfast.  R package version 2.2.
  * Antoch and Hušková [1994] Jaromír Antoch and Marie Hušková.  Procedures for the detection of multiple changes in series of independent observations.  In _Asymptotic Statistics_ , pages 3–20. Springer, 1994.
  * Antoch and Hušková [1999] Jaromir Antoch and Marie Hušková.  Estimators of changes.  In _Asymptotics, Nonparametrics, and Time Series_ , pages 557–561. CRC Press, 1999.
  * Antoch and Hušková [2001] Jaromır Antoch and Marie Hušková.  Permutation tests in change point analysis.  _Statistics & Probability Letters_, 53(1):37–46, 2001.
  * Antoch et al. [1995] Jaromir Antoch, Marie Hušková, and Noël Veraverbeke.  Change-point problem and bootstrap.  _Journal of Nonparametric Statistics_ , 5(2):123–144, 1995.
  * Arias-Castro et al. [2011] Ery Arias-Castro, Emmanuel J Candes, and Arnaud Durand.  Detection of an anomalous cluster in a network.  _The Annals of Statistics_ , 39:278–304, 2011.
  * Arlot and Celisse [2011] Sylvain Arlot and Alain Celisse.  Segmentation of the mean of heteroscedastic data via cross-validation.  _Statistics and Computing_ , 21(4):613–632, 2011\.
  * Arlot et al. [2019] Sylvain Arlot, Alain Celisse, and Zaid Harchaoui.  A kernel multiple change-point algorithm via model selection.  _Journal of Machine Learning Research_ , 20(162), 2019.
  * Aston and Kirch [2012] John AD Aston and Claudia Kirch.  Detecting and estimating changes in dependent functional data.  _Journal of Multivariate Analysis_ , 109:204–220, 2012\.
  * Aston and Kirch [2018] John AD Aston and Claudia Kirch.  High dimensional efficiency with applications to change point tests.  _Electronic Journal of Statistics_ , 12:1901–1947, 2018\.
  * Aue and Horváth [2013] Alexander Aue and Lajos Horváth.  Structural breaks in time series.  _Journal of Time Series Analysis_ , 34:1–16, 2013.
  * Aue et al. [2009] Alexander Aue, Siegfried Hörmann, Lajos Horváth, and Matthew Reimherr.  Break detection in the covariance structure of multivariate time series models.  _The Annals of Statistics_ , 37:4046–4087, 2009.
  * Aue et al. [2014] Alexander Aue, Rex CY Cheung, Thomas CM Lee, and Ming Zhong.  Segmented model selection in quantile regression using the minimum description length principle.  _Journal of the American Statistical Association_ , 109:1241–1256, 2014.
  * Aue et al. [2018] Alexander Aue, Gregory Rice, and Ozan Sönmez.  Detecting and dating structural breaks in functional data without dimension reduction.  _Journal of the Royal Statistical Society, Series B_ , 80:509–529, 2018.
  * Auger and Lawrence [1989] Ivan E Auger and Charles E Lawrence.  Algorithms for the optimal identification of segment neighborhoods.  _Bulletin of Mathematical Biology_ , 51:39–54, 1989.
  * Axt and Fried [2020] Ieva Axt and Roland Fried.  On variance estimation under shifts in the mean.  _ASta Advanced in Statistical Analysis_ , 104:417–457, 2020\.
  * Bai and Perron [1998] Jushan Bai and Pierre Perron.  Estimating and testing linear models with multiple structural changes.  _Econometrica_ , pages 47–78, 1998.
  * Bai et al. [2020] Peiliang Bai, Abolfazl Safikhani, and George Michailidis.  Multiple change points detection in low rank and sparse high dimensional vector autoregressive models.  _IEEE Transactions on Signal Processing_ , 68:3074–3089, 2020.
  * Baranowski et al. [2019] Rafal Baranowski, Yining Chen, and Piotr Fryzlewicz.  Narrowest-over-threshold detection of multiple change-points and change-point-like features.  _Journal of the Royal Statistical Society, Series B_ , 81:649–672, 2019.
  * Barigozzi et al. [2018] Matteo Barigozzi, Haeran Cho, and Piotr Fryzlewicz.  Simultaneous multiple change-point and factor analysis for high-dimensional time series.  _Journal of Econometrics_ , 206:187–225, 2018.
  * Barry and Hartigan [1993] Daniel Barry and John A Hartigan.  A Bayesian analysis for change point problems.  _Journal of the American Statistical Association_ , 88:309–319, 1993.
  * Behrendt and Schweikert [2021] Simon Behrendt and Karsten Schweikert.  A note on adaptive group Lasso for structural break time series.  _Econometrics and Statistics_ , 17:156–172, 2021.
  * Berkes et al. [2009] István Berkes, Robertas Gabrys, Lajos Horváth, and Piotr Kokoszka.  Detecting changes in the mean of functional observations.  _Journal of the Royal Statistical Society, Series B_ , 71:927–946, 2009.
  * Berkes et al. [2014] István Berkes, Weidong Liu, and Wei Biao Wu.  Komlós–Major–Tusnády approximation under dependence.  _The Annals of Probability_ , 42:794–817, 2014.
  * Betken [2016] Annika Betken.  Testing for change-points in long-range dependent time series by means of a self-normalized wilcoxon test.  _Journal of Time Series Analysis_ , 37(6):785–809, 2016.
  * Boysen et al. [2009] Leif Boysen, Angela Kempe, Volkmar Liebscher, Axel Munk, and Olaf Wittich.  Consistencies and rates of convergence of jump-penalized least squares estimators.  _The Annals of Statistics_ , 37:157–183, 2009.
  * Brodsky and Darkhovsky [2000] B. E. Brodsky and B. S. Darkhovsky.  _Nonparametric Statistical Diagnosis: Problems and Methods_ , volume 509.  Springer Science & Business Media, 2000.
  * Bücher et al. [2019] Axel Bücher, Jean-David Fermanian, and Ivan Kojadinovic.  Combining cumulative sum change-point detection tests for assessing the stationarity of univariate time series.  _Journal of Time Series Analysis_ , 40(1):124–150, 2019.
  * Celisse et al. [2018] Alain Celisse, Guillemette Marot, Morgane Pierre-Jean, and GJ Rigaill.  New efficient algorithms for multiple change-point detection with reproducing kernels.  _Computational Statistics & Data Analysis_, 128:200–220, 2018.
  * Chakar et al. [2017] Souhil Chakar, E Lebarbier, Céline Lévy-Leduc, and Stéphane Robin.  A robust approach for estimating change-points in the mean of an AR(1) process.  _Bernoulli_ , 23(2):1408–1447, 2017.
  * Chan and Chen [2017] Hock Peng Chan and Hao Chen.  Multi-sequence segmentation via score and higher-criticism tests.  _arXiv preprint, arXiv:1706.07586_ , 2017.
  * Chan et al. [2014] Ngai Hang Chan, Chun Yip Yau, and Rong-Mao Zhang.  Group Lasso for structural break time series.  _Journal of the American Statistical Association_ , 109:590–599, 2014.
  * Chen et al. [2006] Jiahua Chen, AK Gupta, and Jianmin Pan.  Information criterion and change point problem for regular models.  _Sankhyā: The Indian Journal of Statistics_ , 68:252–282, 2006.
  * Chen and Gupta [2011] Jie Chen and Arjun K Gupta.  _Parametric statistical change point analysis: with applications to genetics, medicine, and finance_.  Springer Science & Business Media, 2nd edition, 2011.
  * Chen et al. [2021] Likai Chen, Weining Wang, and Weibiao Wu.  Inference of break-points in high-dimensional time series.  _Journal of the American Statistical Association (to appear)_ , 2021\.
  * Cho [2016] Haeran Cho.  Change-point detection in panel data via double CUSUM statistic.  _Electronic Journal of Statistics_ , 10:2000–2038, 2016\.
  * Cho and Fryzlewicz [2012] Haeran Cho and Piotr Fryzlewicz.  Multiscale and multilevel technique for consistent segmentation of nonstationary time series.  _Statistica Sinica_ , 22:207–229, 2012.
  * Cho and Fryzlewicz [2015a] Haeran Cho and Piotr Fryzlewicz.  Multiple change-point detection for high-dimensional time series via sparsified binary segmentation.  _Journal of the Royal Statistical Society, Series B_ , 77:475–507, 2015a.
  * Cho and Fryzlewicz [2015b] Haeran Cho and Piotr Fryzlewicz.  Corrections on ‘multiple change-point detection for high-dimensional time series via sparsified binary segmentation’.  https://people.maths.bris.ac.uk/~mahrc/papers/sbs_correction.pdf, 2015b.
  * Cho and Fryzlewicz [2020] Haeran Cho and Piotr Fryzlewicz.  Multiple change point detection under serial dependence: Wild energy maximisation and gappy Schwarz criterion.  _arXiv preprint arXiv:2011.13884_ , 2020.
  * Cho and Kirch [2020] Haeran Cho and Claudia Kirch.  Two-stage data segmentation permitting multiscale change points, heavy tails and dependence.  _arXiv preprint arXiv:1910.12486_ , 2020.
  * Cho and Kirch [2021] Haeran Cho and Claudia Kirch.  Bootstrap confidence intervals for multiple change points based on moving sum procedures.  _arXiv preprint arXiv:2106.12844_ , 2021.
  * Chu et al. [1995] Chia-Shang J Chu, Kurt Hornik, and Chung-Ming Kaun.  MOSUM tests for parameter constancy.  _Biometrika_ , 82:603–617, 1995.
  * Chu and Chen [2019] Lynna Chu and Hao Chen.  Asymptotic distribution-free change-point detection for multivariate and non-Euclidean data.  _The Annals of Statistics_ , 47:382–414, 2019.
  * Cleynen et al. [2016] Alice Cleynen, Guillem Rigaill, and Michel Koskas.  _Segmentor3IsBack: A fast segmentation algorithm_ , 2016.  URL https://CRAN.R-project.org/package=Segmentor3IsBack.  R package version 2.0.
  * Csörgő and Horváth [1989] Miklós Csörgő and Lajos Horváth.  Invariance principles for changepoint problems.  In _Multivariate statistics and probability_ , pages 151–168. Elsevier, 1989.
  * Csörgö and Horváth [1997] Miklós Csörgö and Lajos Horváth.  _Limit Theorems in Change-point Analysis_ , volume 18.  John Wiley & Sons Inc, 1997.
  * Davis and Yau [2013] Richard A Davis and Chun Yip Yau.  Consistency of minimum description length model selection for piecewise stationary time series models.  _Electronic Journal of Statistics_ , 7:381–411, 2013.
  * Davis et al. [2006] Richard A Davis, Thomas C M Lee, and Gabriel A Rodriguez-Yam.  Structural break estimation for nonstationary time series models.  _Journal of the American Statistical Association_ , 101:223–239, 2006.
  * Davis et al. [2008] Richard A Davis, Thomas CM Lee, and Gabriel A Rodriguez-Yam.  Break detection for a class of nonlinear time series models.  _Journal of Time Series Analysis_ , 29:834–867, 2008.
  * Dehling et al. [2020] H Dehling, R Fried, and M Wendler.  A robust method for shift detection in time series.  _Biometrika_ , 107(3):647–660, 2020.
  * Dehling et al. [2013] Herold Dehling, Aeneas Rooch, and Murad S Taqqu.  Non-parametric change-point tests for long-range dependent data.  _Scandinavian Journal of Statistics_ , 40(1):153–173, 2013.
  * Dehling et al. [2015] Herold Dehling, Roland Fried, Isabel Garcia, and Martin Wendler.  Change-point detection under dependence based on two-sample U-statistics.  In _Asymptotic Laws and Methods in Stochastics_ , pages 195–220. Springer, 2015.
  * Dette et al. [2020] Holger Dette, Theresa Schüler, and Mathias Vetter.  Multiscale change point detection for dependent data.  _Scandinavian Journal of Statistics_ , 47:1243–1274, 2020\.
  * Döring [2010] Maik Döring.  Multiple change-point estimation with U-statistics.  _Journal of Statistical Planning and Inference_ , 140(7):2003–2017, 2010.
  * Du et al. [2016] Chao Du, Chu-Lan Michael Kao, and SC Kou.  Stepwise signal extraction via marginal likelihood.  _Journal of the American Statistical Association_ , 111:314–330, 2016.
  * Eckley et al. [2011] Idris A Eckley, Paul Fearnhead, and Rebecca Killick.  Analysis of changepoint models.  In David Barber, A. Taylan Cemgil, and Silvia Chiappa, editors, _Bayesian Time Series Models_ , pages 205–224. Cambridge University Press, 2011.
  * Efron et al. [2004] Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani.  Least angle regression.  _The Annals of Statistics_ , 32:407–499, 2004.
  * Eichinger and Kirch [2018] Birte Eichinger and Claudia Kirch.  A MOSUM procedure for the estimation of multiple random change points.  _Bernoulli_ , 24:526–564, 2018.
  * Enikeeva and Harchaoui [2019] Farida Enikeeva and Zaid Harchaoui.  High-dimensional change-point detection under sparse alternatives.  _The Annals of Statistics_ , 47:2051–2079, 2019.
  * Fang et al. [2020] Xiao Fang, Jian Li, and David Siegmund.  Segmentation and estimation of change-point models: false positive control and confidence regions.  _The Annals of Statistics_ , 48:1615–1647, 2020.
  * Fearnhead [2006] Paul Fearnhead.  Exact and efficient Bayesian inference for multiple changepoint problems.  _Statistics and Computing_ , 16:203–213, 2006.
  * Fearnhead and Rigaill [2019] Paul Fearnhead and Guillem Rigaill.  Changepoint detection in the presence of outliers.  _Journal of the American Statistical Association_ , 114:169–183, 2019.
  * Fearnhead and Rigaill [2020] Paul Fearnhead and Guillem Rigaill.  Relating and comparing methods for detecting changes in mean.  _Stat_ , page e291, 2020.
  * Fearnhead et al. [2019] Paul Fearnhead, Robert Maidstone, and Adam Letchford.  Detecting changes in slope with an $l_{0}$ penalty.  _Journal of Computational and Graphical Statistics_ , 28:265–275, 2019.
  * Ferger [1994] Dietmar Ferger.  On the power of nonparametric changepoint-tests.  _Metrika_ , 41(1):277–292, 1994.
  * Fisch et al. [2018] Alexander Tristan Maximilian Fisch, Idris Arthur Eckley, and Paul Fearnhead.  A linear time method for the detection of point and collective anomalies.  _arXiv preprint arXiv:1806.01947_ , 2018.
  * Frick et al. [2014] Klaus Frick, Axel Munk, and Hannes Sieling.  Multiscale change point inference.  _Journal of the Royal Statistical Society, Series B_ , 76:495–580, 2014.
  * Fromont et al. [2020] M. Fromont, M. Lerasle, and N. Verzelen.  Optimal change point detection and localization.  _arXiv preprint arXiv:2010.11470_ , 2020.
  * Fryzlewicz [2014] Piotr Fryzlewicz.  Wild binary segmentation for multiple change-point detection.  _The Annals of Statistics_ , 42:2243–2281, 2014.
  * Fryzlewicz [2018] Piotr Fryzlewicz.  Tail-greedy bottom-up data decompositions and fast multiple change-point detection.  _The Annals of Statistics_ , pages 3390–3421, 2018.
  * Fryzlewicz [2020a] Piotr Fryzlewicz.  Detecting possibly frequent change-points: Wild Binary Segmentation 2 and steepest-drop model selection.  _Journal of the Korean Statistical Society_ , 49:1–44, 2020a.
  * Fryzlewicz [2020b] Piotr Fryzlewicz.  Narrowest significance pursuit: inference for multiple change-points in linear models.  _arXiv preprint arXiv:2009.05431_ , 2020b.
  * Fryzlewicz and Subba Rao [2014] Piotr Fryzlewicz and Suhasini Subba Rao.  Multiple-change-point detection for auto-regressive conditional heteroscedastic processes.  _Journal of the Royal Statistical Society, Series B_ , 76:903–924, 2014.
  * Fuh [2004] Cheng-Der Fuh.  Asymptotic operating characteristics of an optimal change point detection in hidden Markov models.  _The Annals of Statistics_ , 32:2305–2339, 2004.
  * Garreau and Arlot [2018] Damien Garreau and Sylvain Arlot.  Consistent change-point detection with kernels.  _Electronic Journal of Statistics_ , 12:4440–4486, 2018\.
  * Gombay [2001] Edit Gombay.  U-statistics for change under alternatives.  _Journal of Multivariate Analysis_ , 78(1):139–158, 2001.
  * Górecki et al. [2018] Tomasz Górecki, Lajos Horváth, and Piotr Kokoszka.  Change point detection in heteroscedastic time series.  _Econometrics and Statistics_ , 7:63–88, 2018.
  * Grunwald [2004] Peter Grunwald.  A tutorial introduction to the minimum description length principle.  _arXiv preprint arXiv:math/0406077_ , 2004.
  * Harchaoui and Lévy-Leduc [2010] Zaıd Harchaoui and Céline Lévy-Leduc.  Multiple change-point estimation with a total variation penalty.  _Journal of the American Statistical Association_ , 105:1480–1493, 2010.
  * Haynes et al. [2017a] Kaylea Haynes, Idris A Eckley, and Paul Fearnhead.  Computationally efficient changepoint detection for a range of penalties.  _Journal of Computational and Graphical Statistics_ , 26:134–143, 2017a.
  * Haynes et al. [2017b] Kaylea Haynes, Paul Fearnhead, and Idris A Eckley.  A computationally efficient nonparametric approach for changepoint detection.  _Statistics and Computing_ , 27:1293–1305, 2017b.
  * Heunis [2003] A. J. Heunis.  Strong invariance principle for singular diffusions.  _Stochastic Processes and their Applications_ , 104:57–80, 2003.
  * Horváth and Hušková [2012] L. Horváth and M. Hušková.  Change-point detection in panel data.  _Journal of Time Series Analysis_ , 33:631–648, 2012.
  * Horváth and Rice [2014] Lajos Horváth and Gregory Rice.  Extensions of some classical methods in change point analysis.  _TEST_ , 23:1–37, 2014.
  * Horváth and Steinebach [2000] Lajos Horváth and Josef Steinebach.  Testing for changes in the mean or variance of a stochastic process under weak invariance.  _Journal of Statistical Planning and Inference_ , 91:365–376, 2000.
  * Hušková [1990a] Marie Hušková.  Asymptotics for robust MOSUM.  _Commentationes Mathematicae Universitatis Carolinae_ , 31(2):345–356, 1990a.
  * Hušková [1990b] Marie Hušková.  Some asymptotic results for robust procedures for testing the constancy of regression models over time.  _Kybernetika_ , 26(5):392–403, 1990b.
  * Hušková [1996] Marie Hušková.  Tests and estimators for the change point problem based on M-statistics.  _Statistics & Risk Modeling_, 14:115–136, 1996.
  * Hušková [2004] Marie Hušková.  Permutation principle and bootstrap in change point analysis.  In L. Horváth and B. Szyszkowicz, editors, _Asymptotic Methods in Stochastics. Festschrift for Miklós Csörgö_ , volume 44, pages 273–292. American Mathematical Society, 2004.
  * Hušková [2013] Marie Hušková.  Robust change point analysis.  In _Robustness and Complex Data Structures_ , pages 171–190. Springer, 2013.
  * Hušková and Kirch [2008] Marie Hušková and Claudia Kirch.  Bootstrapping confidence intervals for the change-point of time series.  _Journal of Time Series Analysis_ , 29:947–972, 2008.
  * Hušková and Kirch [2010] Marie Hušková and Claudia Kirch.  A note on studentized confidence intervals for the change-point.  _Computational Statistics_ , 25:269–289, 2010.
  * Hušková and Marušiaková [2012] Marie Hušková and Miriam Marušiaková.  M-procedures for detection of changes for dependent observations.  _Communications in Statistics – Simulation and Computation_ , 41(7):1032–1050, 2012.
  * Hušková and Meintanis [2006a] Marie Hušková and Simos G Meintanis.  Change point analysis based on empirical characteristic functions.  _Metrika_ , 63:145–168, 2006a.
  * Hušková and Meintanis [2006b] Marie Hušková and Simos G Meintanis.  Change-point analysis based on empirical characteristic functions of ranks.  _Sequential Analysis_ , 25(4):421–436, 2006b.
  * Hušková and Picek [2002] Marie Hušková and Jan Picek.  M-tests for detection of structural changes in regression.  In _Statistical data analysis based on the L1-norm and related methods_ , pages 213–227. Springer, 2002.
  * Hušková and Slabỳ [2001] Marie Hušková and Aleš Slabỳ.  Permutation tests for multiple changes.  _Kybernetika_ , 37:605–622, 2001.
  * Hušková et al. [2007] Marie Hušková, Zuzana Prášková, and Josef Steinebach.  On the detection of changes in autoregressive time series I. Asymptotics.  _Journal of Statistical Planning and Inference_ , 137:1243–1259, 2007.
  * Hyun et al. [2021] Sangwon Hyun, Kevin Z Lin, Max G’Sell, and Ryan J Tibshirani.  Post-selection inference for changepoint detection algorithms with application to copy number variation data.  _Biometrics_ , 2021.
  * Jackson et al. [2005] Brad Jackson, Jeffrey D Scargle, David Barnes, Sundararajan Arabhi, Alina Alt, Peter Gioumousis, Elyus Gwin, Paungkaew Sangtrakulcharoen, Linda Tan, and Tun Tao Tsai.  An algorithm for optimal partitioning of data on an interval.  _IEEE Signal Processing Letters_ , 12:105–108, 2005.
  * Jandhyala et al. [2013] Venkata Jandhyala, Stergios Fotopoulos, Ian MacNeill, and Pengyu Liu.  Inference for single and multiple change-points in time series.  _Journal of Time Series Analysis_ , 34(4):423–446, 2013.
  * Jewell et al. [2019] Sean Jewell, Paul Fearnhead, and Daniela Witten.  Testing for a change in mean after changepoint detection.  _arXiv preprint arXiv:1910.04291_ , 2019.
  * Jirak [2015] Moritz Jirak.  Uniform change point tests in high dimension.  _The Annals of Statistics_ , 43:2451–2483, 2015.
  * Kaul et al. [2019] Abhishek Kaul, Venkata K Jandhyala, and Stergios B Fotopoulos.  Detection and estimation of parameters in high dimensional multiple change point regression models via $\ell_{1}/\ell_{0}$ regularization and discrete optimization.  _arXiv preprint arXiv:1906.04396_ , 2019.
  * Killick et al. [2012] Rebecca Killick, Paul Fearnhead, and Idris A Eckley.  Optimal detection of changepoints with a linear computational cost.  _Journal of the American Statistical Association_ , 107:1590–1598, 2012.
  * Killick et al. [2016] Rebecca Killick, Kaylea Haynes, and Idris A. Eckley.  _changepoint: An R package for changepoint analysis_ , 2016.  URL https://CRAN.R-project.org/package=changepoint.  R package version 2.2.2.
  * Kirch and Kamgaing [2014] Claudia Kirch and J Tadjuidje Kamgaing.  Detection of change points in discrete valued time series.  In Richard A. Davis, Scott H. Holan, Robert Lund, and Nalini Ravishanker, editors, _Handbook of Discrete Valued Time Series_. Chapman and Hall/CRC, New York, 2014.
  * Kirch and Kamgaing [2012] Claudia Kirch and Joseph Tadjuidje Kamgaing.  Testing for parameter stability in nonlinear autoregressive models.  _Journal of Time Series Analysis_ , 33:365–385, 2012.
  * Kirch and Klein [2021] Claudia Kirch and Philipp Klein.  Moving sum data segmentation for stochastics processes based on invariance.  _arXiv preprint arXiv:2101.04651_ , 2021.
  * Kirch and Reckrühm [2021] Claudia Kirch and Kerstin Reckrühm.  Data segmentation for time series based on a general moving sum approach.  In preparation, 2021.
  * Kirch et al. [2015] Claudia Kirch, Birte Muhsal, and Hernando Ombao.  Detection of changes in multivariate time series with application to EEG data.  _Journal of the American Statistical Association_ , 110:1197–1216, 2015.
  * Komlós et al. [1975] János Komlós, Péter Major, and Gábor Tusnády.  An approximation of partial sums of independent RV’s, and the sample DF. I.  _Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete_ , 32:111–131, 1975.
  * Komlós et al. [1976] János Komlós, Péter Major, and Gábor Tusnády.  An approximation of partial sums of independent RV’s, and the sample DF. II.  _Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete_ , 34:33–58, 1976.
  * Korostelev [1987] A. Korostelev.  On minimax estimation of a discontinuous signal.  _Theory of Probability and its Applications_ , 32:727–730, 1987.
  * Kovács et al. [2020] Solt Kovács, Housen Li, Peter Bühlmann, and Axel Munk.  Seeded binary segmentation: A general methodology for fast and optimal change point detection.  _arXiv preprint arXiv:2002.06633_ , 2020.
  * Kuelbs and Philipp [1980] James Kuelbs and Walter Philipp.  Almost sure invariance principles for partial sums of mixing $B$-valued random variables.  _The Annals of Probability_ , 8:1003–1036, 1980.
  * Kühn [2001] Christoph Kühn.  An estimator of the number of change points based on a weak invariance principle.  _Statistics & Probability Letters_, 51:189–196, 2001\.
  * Lavielle and Moulines [2000] Marc Lavielle and Eric Moulines.  Least-squares estimation of an unknown number of shifts in a time series.  _Journal of Time Series Analysis_ , 21:33–59, 2000.
  * Lebarbier [2005] Émilie Lebarbier.  Detecting multiple change-points in the mean of Gaussian process by model selection.  _Signal Processing_ , 85(4):717–736, 2005.
  * Lee [1995] Chung-Bow Lee.  Estimating the number of change points in a sequence of independent normal random variables.  _Statistics & Probability Letters_, 25:241–248, 1995\.
  * Leonardi and Bühlmann [2016] Florencia Leonardi and Peter Bühlmann.  Computationally efficient change point detection for high-dimensional regression.  _arXiv preprint arXiv:1601.03704_ , 2016.
  * Li and Sieling [2017] Housen Li and Hannes Sieling.  _FDRSeg: FDR-control in multiscale change-point segmentation_ , 2017.  URL https://CRAN.R-project.org/package=FDRSeg.  R package version 1.0-3.
  * Li et al. [2016] Housen Li, Axel Munk, and Hannes Sieling.  FDR-control in multiscale change-point segmentation.  _Electronic Journal of Statistics_ , 10:918–959, 2016.
  * Li et al. [2019] Housen Li, Qinghai Guo, and Axel Munk.  Multiscale change-point segmentation: Beyond step functions.  _Electronic Journal of Statistics_ , 13:3254–3296, 2019\.
  * Lin et al. [2017] Kevin Lin, James L Sharpnack, Alessandro Rinaldo, and Ryan J Tibshirani.  A sharp error analysis for the fused Lasso, with application to approximate changepoint screening.  In _Advances in Neural Information Processing Systems_ , pages 6884–6893, 2017.
  * Liu et al. [2021] Haoyang Liu, Chao Gao, and Richard J Samworth.  Minimax rates in sparse, high-dimensional change point detection.  _The Annals of Statistics_ , 49(2):1081–1112, 2021.
  * Liu and Chen [2020] Yi-Wei Liu and Hao Chen.  A fast and efficient change-point detection framework for modern data.  _arXiv preprint arXiv:2006.13450_ , 2020.
  * Lu et al. [2020] Zhiyuan Lu, Moulinath Banerjee, and George Michailidis.  Intelligent sampling for multiple change-points in exceedingly long time series with rate guarantees.  _arXiv preprint arXiv:1710.07420_ , 2020.
  * Maeng and Fryzlewicz [2019] Hyeyoung Maeng and Piotr Fryzlewicz.  Detecting linear trend changes and point anomalies in data sequences.  _arXiv preprint arXiv:1906.01939_ , 2019.
  * Maidstone et al. [2017] Robert Maidstone, Toby Hocking, Guillem Rigaill, and Paul Fearnhead.  On optimal multiple changepoint algorithms for large data.  _Statistics and Computing_ , 27:519–533, 2017.
  * Marušiaková [2009] Miriam Marušiaková.  _Tests for multiple changes in linear regression models_.  PhD thesis, Charles University in Prague, 2009.
  * Matteson and James [2014] David S. Matteson and Nicholas A. James.  A nonparametric approach for multiple change point analysis of multivariate data.  _Journal of the American Statistical Association_ , 109:334–345, 2014.
  * Meier et al. [2021a] Alexander Meier, Haeran Cho, and Claudia Kirch.  _mosum: Moving sum based procedures for changes in the mean_ , 2021a.  URL https://CRAN.R-project.org/package=mosum.  R package version 1.2.6.
  * Meier et al. [2021b] Alexander Meier, Claudia Kirch, and Haeran Cho.  mosum: A package for moving sums in change-point analysis.  _Journal of Statistical Software_ , 97(1):1–42, 2021b.
  * Messer et al. [2014] Michael Messer, Marietta Kirchner, Julia Schiemann, Jochen Roeper, Ralph Neininger, and Gaby Schneider.  A multiple filter test for the detection of rate changes in renewal processes with varying variance.  _The Annals of Applied Statistics_ , 8:2027–2067, 2014\.
  * Messer et al. [2018] Michael Messer, Stefan Albert, and Gaby Schneider.  The multiple filter test for change point detection in time series.  _Metrika_ , 81:589–607, 2018.
  * Mohr and Neumeyer [2020] Maria Mohr and Natalie Neumeyer.  Consistent nonparametric change point detection combining CUSUM and marked empirical processes.  _Electronic Journal of Statistics_ , 14:2238–2271, 2020\.
  * Ninomiya [2005] Yoshiyuki Ninomiya.  Information criterion for Gaussian change-point model.  _Statistics & Probability Letters_, 72:237–247, 2005\.
  * Niu and Zhang [2012] Yue S Niu and Heping Zhang.  The screening and ranking algorithm to detect DNA copy number variations.  _The Annals of Applied Statistics_ , 6:1306–1326, 2012\.
  * Olshen et al. [2004] Adam B Olshen, ES Venkatraman, Robert Lucito, and Michael Wigler.  Circular binary segmentation for the analysis of array-based DNA copy number data.  _Biostatistics_ , 5:557–572, 2004.
  * Orasch [2004] M Orasch.  Using U-statistcs based processes to detect multiple change-points.  In L. Horváth and B. Szyszkowicz, editors, _Asymptotic Methods in Stochastics. Festschrift for Miklós Csörgö_ , volume 44, pages 315–334. American Mathematical Society, 2004.
  * Padilla et al. [2019] Oscar Hernan Madrid Padilla, Yi Yu, Daren Wang, and Alessandro Rinaldo.  Optimal nonparametric change point detection and localization.  _arXiv preprint arXiv:1905.10019_ , 2019.
  * Page [1954] Ewan S Page.  Continuous inspection schemes.  _Biometrika_ , 41:100–115, 1954.
  * Pan and Chen [2006] Jianmin Pan and Jiahua Chen.  Application of modified information criterion to multiple change point problems.  _Journal of Multivariate Analysis_ , 97:2221–2241, 2006\.
  * Pein et al. [2017] Florian Pein, Hannes Sieling, and Axel Munk.  Heterogeneous change point inference.  _Journal of the Royal Statistical Society, Series B_ , 79:1207–1227, 2017.
  * Pein et al. [2019] Florian Pein, Thomas Hotz, Hannes Sieling, and Timo Aspelmeier.  _stepR: Multiscale change-point inference_ , 2019.  URL https://CRAN.R-project.org/package=stepR.  R package version 2.0-3.
  * Perron [2006] Pierre Perron.  Dealing with structural breaks.  _Palgrave Handbook of Econometrics_ , 1:278–352, 2006.
  * Prášková and Chochola [2014] Zuzana Prášková and Ondřej Chochola.  M-procedures for detection of a change under weak dependence.  _Journal of Statistical Planning and Inference_ , 149:60–76, 2014.
  * Preuss et al. [2015] Philip Preuss, Ruprecht Puchstein, and Holger Dette.  Detection of multiple structural breaks in multivariate time series.  _Journal of the American Statistical Association_ , 110:654–668, 2015.
  * Reckrühm [2019] Kerstin Reckrühm.  _Estimating multiple structural breaks in time series – a generalized MOSUM approach based on estimating functions_.  PhD thesis, Otto-von-Guericke University, Magdeburg, Germany, 2019.
  * Reeves et al. [2007] Jaxk Reeves, Jien Chen, Xiaolan L Wang, Robert Lund, and Qi Qi Lu.  A review and comparison of changepoint detection techniques for climate data.  _Journal of Applied Meteorology and Climatology_ , 46:900–915, 2007.
  * Rigaill [2015] Guillem Rigaill.  A pruned dynamic programming algorithm to recover the best segmentations with 1 to K_max change-points.  _Journal de la Société Frankcaise de Statistique_ , 156:180–205, 2015.
  * Rigaill and Hocking [2019] Guillem Rigaill and Toby Dylan Hocking.  _fpop: Segmentation using Optimal Partitioning and Function Pruning_ , 2019.  URL https://R-Forge.R-project.org/projects/opfp/.  R package version 2019.01.22/r56.
  * Rigaill et al. [2012] Guillem Rigaill, Émilie Lebarbier, and Stephane Robin.  Exact posterior distributions and model selection criteria for multiple change-point detection problems.  _Statistics and Computing_ , 22:917–929, 2012.
  * Rinaldo [2009] Alessandro Rinaldo.  Properties and refinements of the fused Lasso.  _The Annals of Statistics_ , 37:2922–2952, 2009.
  * Rissanen [1978] Jorma Rissanen.  Modeling by shortest data description.  _Automatica_ , 14:465–471, 1978.
  * Romano et al. [2021] Gaetano Romano, Guillem Rigaill, Vincent Runge, and Paul Fearnhead.  Detecting abrupt changes in the presence of local fluctuations and autocorrelated noise.  _Journal of the American Statistical Association (to appear)_ , 2021\.
  * Safikhani and Shojaie [2020] Abolfazl Safikhani and Ali Shojaie.  Joint structural break detection and parameter estimation in high-dimensional nonstationary VAR models.  _Journal of the American Statistical Association_ , pages 1–14, 2020\.
  * Schwarz [1978] Gideon Schwarz.  Estimating the dimension of a model.  _The Annals of Statistics_ , 6:461–464, 1978.
  * Scott and Knott [1974] Andrew Jhon Scott and M Knott.  A cluster analysis method for grouping means in the analysis of variance.  _Biometrics_ , 6:507–512, 1974.
  * Sharipov et al. [2016] Olimjon Sharipov, Johannes Tewes, and Martin Wendler.  Sequential block bootstrap in a Hilbert space with application to change point analysis.  _Canadian Journal of Statistics_ , 44:300–322, 2016.
  * Shin et al. [2020] Seung Jun Shin, Yichao Wu, and Ning Hao.  A backward procedure for change-point detection with applications to copy number variation detection.  _Canadian Journal of Statistics_ , 48:366–385, 2020.
  * Steinebach and Eastwood [1996] J. Steinebach and V. R. Eastwood.  Extreme value asymptotics for multivariate renewal processes.  _Journal of Multivariate Analysis_ , 56:284–302, 1996.
  * Steland [2020] Ansgar Steland.  Testing and estimating change-points in the covariance matrix of a high-dimensional time series.  _Journal of Multivariate Analysis_ , 177:104582, 2020.
  * Stoehr et al. [2021] Christina Stoehr, John AD Aston, and Claudia Kirch.  Detecting changes in the covariance structure of functional time series with application to fmri data.  _Econometrics and Statistics_ , 18:44–62, 2021.
  * Tartakovsky [2019] Alexander Tartakovsky.  _Sequential Change Detection and Hypothesis Testing: General Non-iid Stochastic Models and Asymptotically Optimal Rules_.  CRC Press, 2019.
  * Tartakovsky et al. [2014] Alexander Tartakovsky, Igor Nikiforov, and Michele Basseville.  _Sequential analysis: Hypothesis testing and changepoint detection_.  CRC Press, 2014.
  * Tecuapetla-Gómez and Munk [2017] Inder Tecuapetla-Gómez and Axel Munk.  Autocovariance estimation in regression with a discontinuous signal and m-dependent errors: A difference-based approach.  _Scandinavian Journal of Statistics_ , 44:346–368, 2017\.
  * Tibshirani et al. [2005] Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight.  Sparsity and smoothness via the fused Lasso.  _Journal of the Royal Statistical Society, Series B_ , 67:91–108, 2005.
  * Tibshirani [2014] Ryan J Tibshirani.  Adaptive piecewise polynomial estimation via trend filtering.  _The Annals of Statistics_ , 42:285–323, 2014.
  * Tickle et al. [2020] SO Tickle, IA Eckley, Paul Fearnhead, and Kaylea Haynes.  Parallelization of a common changepoint detection method.  _Journal of Computational and Graphical Statistics_ , 29:149–161, 2020.
  * Titsias et al. [2016] Michalis K Titsias, Christopher C Holmes, and Christopher Yau.  Statistical inference in hidden Markov models using k-segment constraints.  _Journal of the American Statistical Association_ , 111:200–215, 2016.
  * Truong et al. [2020] Charles Truong, Laurent Oudre, and Nicolas Vayatis.  Selective review of offline change point detection methods.  _Signal Processing_ , 167:107299, 2020.
  * Venkatraman [1992] E. S. Venkatraman.  _Consistency Results in Multiple Change-point Problems_.  PhD thesis, Stanford University, 1992.
  * Venkatraman and Olshen [2007] ES Venkatraman and Adam B Olshen.  A faster circular binary segmentation algorithm for the analysis of array CGH data.  _Bioinformatics_ , 23:657–663, 2007.
  * Vogel and Wendler [2017] Daniel Vogel and Martin Wendler.  Studentized U-quantile processes under dependence with applications to change-point analysis.  _Bernoulli_ , 23(4B):3114–3144, 2017.
  * Vostrikova [1981] L. J. Vostrikova.  Detecting ‘disorder’ in multidimensional random processes.  _Soviet Doklady Mathematics_ , 24:55–59, 1981.
  * Wang et al. [2019a] Daren Wang, Kevin Lin, and Rebecca Willett.  Statistically and computationally efficient change point localization in regression settings.  _arXiv preprint arXiv:1906.11364_ , 2019a.
  * Wang et al. [2019b] Daren Wang, Yi Yu, Alessandro Rinaldo, and Rebecca Willett.  Localizing changes in high-dimensional vector autoregressive processes.  _arXiv preprint arXiv:1909.06359_ , 2019b.
  * Wang et al. [2020] Daren Wang, Yi Yu, and Alessandro Rinaldo.  Univariate mean change point detection: Penalization, cusum and optimality.  _Electronic Journal of Statistics_ , 14:1917–1961, 2020\.
  * Wang et al. [2021] Daren Wang, Yi Yu, and Alessandro Rinaldo.  Optimal covariance change point localization in high dimension.  _Bernoulli_ , 27:554–575, 2021.
  * Wang et al. [2019c] Runmin Wang, Stanislav Volgushev, and Xiaofeng Shao.  Inference for change points in high dimensional data.  _arXiv preprint arXiv:1905.08446_ , 2019c.
  * Wang and Samworth [2018] Tengyao Wang and Richard J Samworth.  High dimensional change point estimation via sparse projection.  _Journal of the Royal Statistical Society, Series B_ , 80:57–83, 2018.
  * Yao [1984] Yi-Ching Yao.  Estimation of a noisy discrete-time step function: Bayes and empirical Bayes approaches.  _The Annals of Statistics_ , pages 1434–1447, 1984.
  * Yao [1988] Yi-Ching Yao.  Estimating the number of change-points via Schwarz’ criterion.  _Statistics & Probability Letters_, 6:181–189, 1988.
  * Yao [1990] Yi-Ching Yao.  On the asymptotic behavior of a class of nonparametric tests for a change-point problem.  _Statistics & Probability Letters_, 9:173–177, 1990.
  * Yao and Au [1989] Yi-Ching Yao and Siu-Tong Au.  Least-squares estimation of a step function.  _Sankhyā: The Indian Journal of Statistics, Series A_ , pages 370–381, 1989.
  * Yau and Zhao [2016] Chun Yip Yau and Zifeng Zhao.  Inference for multiple change points in time series via likelihood ratio scan statistics.  _Journal of the Royal Statistical Society, Series B_ , 78:895–916, 2016.
  * Zhang and Siegmund [2007] Nancy R Zhang and David O Siegmund.  A modified Bayes information criterion with applications to the analysis of comparative genomic hybridization data.  _Biometrics_ , 63:22–32, 2007.
  * Zhao et al. [2019] Zifeng Zhao, Li Chen, and Lizhen Lin.  Change-point detection in dynamic networks via graphon estimation.  _arXiv preprint arXiv:1908.01823_ , 2019.
  * Zou et al. [2014] Changliang Zou, Guosheng Yin, Long Feng, and Zhaojun Wang.  Nonparametric maximum likelihood approach to multiple change-point problems.  _The Annals of Statistics_ , 42:970–1002, 2014.