Electronic Journal of Statistics
Vol. 0 (0000)
ISSN: 1935-7524
DOI: 10.1214/154957804100000000

arXiv:1610.03783v4 [] 3 May 2017

Change-point detection in
high-dimensional covariance structure
Valeriy Avanesov, Nazar Buzun
WIAS
Mohrenstr. 39
10117 Berlin
Germany
e-mail: avanesov@wias-berlin.de; buzun@wias-berlin.de
Abstract: In this paper we introduce a novel approach for an important
problem of break detection. Specifically, we are interested in detection of
an abrupt change in the covariance structure of a high-dimensional random
process – a problem, which has applications in many areas e.g., neuroimaging and finance. The developed approach is essentially a testing procedure
involving a choice of a critical level. To that end a non-standard bootstrap
scheme is proposed and theoretically justified under mild assumptions. Theoretical study features a result providing guaranties for break detection. All
the theoretical results are established in a high-dimensional setting (dimensionality p  n). Multiscale nature of the approach allows for a trade-off
between sensitivity of break detection and localization. The approach can
be naturally employed in an on-line setting. Simulation study demonstrates
that the approach matches the nominal level of false alarm probability and
exhibits high power, outperforming a recent approach.
MSC 2010 subject classifications: Primary 62M10, 62H15; secondary
91B84, 62P10.
Keywords and phrases: multiscale, bootstrap, structural change, critical
value, precision matrix.

1. Introduction
The analysis of high dimensional time series is crucial for many fields including neuroimaging and financial engineering. There, one often has to deal with
processes involving abrupt structural changes which necessitate a corresponding
adaptation of a model and/or a strategy. Structural break analysis comprises
determining if an abrupt change is present in the given sample and if so, estimating the change-point, namely the moment in time when it takes place. In
literature both problems may be referred to as change-point or break detection.
In this study we will be using terms break detection and change-point localization
respectively in order to distinguish between them. The majority of approaches
to the problem consider only a univariate process [13] [1]. However, in recent
years the interest for multi-dimensional approaches has increased. Most of them
cover the case of fixed dimensionality [27] [25] [2] [35] [36]. Some approaches
[10, 24, 11] feature high-dimensional theoretical guaranties but only the case
of dimensionality polynomially growing in sample size is covered. The case of
exponential growth has not been considered so far.
0

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure 1

In order to detect a break, a test statistic is usually computed for each point
t (e.g. [27]). The break is detected if the maximum of these values exceeds a
certain threshold. A proper choice of the latter may be a tricky issue. Consider
a pair of plots (Figure 1) of the statistic A(t) defined in Section 2. It is rather
difficult to see how many breaks are there, if any. The classic approach to the
problem is based on the asymptotic behaviour of the statistic [13] [1] [2] [24] [6]
[36]. As an alternative, permutation [24] [27] or parametric bootstrap may be
used [24]. Clearly, it seems attractive to choose the threshold in a solely datadriven way as it is suggested in the recent paper [10], but a careful bootstrap
validation is still an open question.
In the current study we are interested in a particular kind of a break – an
abrupt transformation in the covariance matrix – which is motivated by applications to neuroimaging. The covariance structure of data in functional Magnetic
Resonance Imaging has recently drawn a lot of interest, as it encodes so-called
functional connectivity networks [34] which refer to the explicit influence among
neural systems [18]. A rather popular approach to inferencing these networks is
based on estimating inverse covariance or precision matrices [? ]. The technique
generally makes use of the observation that functional connectivity networks are
of small-world type [34], which makes sparsity assumptions feasible. Analysing
the dynamics of these networks is particularly important for the research on
neural diseases and also in the context of brain development with emphasis on
characterizing the re-configuration of the brain during learning [4].
A similar problem is found in finance: the dynamics of the covariance structure of a high-dimensional process modelling exchange rates and market indexes
is crucial for a proper asset allocation in a portfolio [12, 5, 14, 29].
One approach to the change-point localization is developed in [25], the corresponding significance testing problem is considered in [2]. However, neither of
these papers address the high-dimensional case.
A widely used break detection approach (named CUSUM) [11, 2, 24] suggests
to compute a statistic at a point t as a distance of estimators of some parameter
of the underlying distributions obtained using all the data before and after that
point. This technique requires the whole sample to be known in advance, which
prevents it from being used in online setting. In order to overcome this drawback we propose the following augmentation: choose a window size n ∈ N and
compute parameter estimators using only n points before and n points after
the central point t (see Section 2 for formal definition). Window size n is an
important parameter and its choice is case-specific (see Section 4 for theoretical
treatment of this issue). Using a small window results in high variability and
low sensitivity, while a large window implies higher uncertainty in change-point
localization yielding the issue of a proper choice of window size. The multiscale
nature of the proposed method enables us to incorporate the advantages of narrower and wider windows by considering multiple window sizes at once in order
for wider windows to provide higher sensitivity while narrower ones improve
change-point localization.
The contribution of our study is the development of a novel break detection
approach which is

A(t)

A(t)

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure 2

50

100

150

200

250

50

100

t

150

200

250

t

Figure 1: Plots of test statstics A(t) computed on synthetically generated data
without (left) and with a single change-point at t = 150 (right). Clearly, the
choice of a threshold is not obvious.

• high-dimensional, allowing for up to exponential growth of the dimensionality with the window size
• suitable for on-line setting
• multiscale, attaining trade-off between break detection sensitivity and
change-point localization accuracy
• using a fully data-driven threshold selection algorithm rigorously justified
under mild assumptions
• featuring formal sensitivity guaranties in high-dimensional setting
We consider the following setup. Let X1 , ... XN ∈ Rp denote an independent
sample of zero-mean vectors (the on-line setting is discussed in Section 3) and
we want to test a hypothesis

H0 := {∀i : Var [Xi ] = Var [Xi+1 ]}
versus an alternative suggesting the existence of a break:
H1 := {∃τ : Var [X1 ] = Var [X2 ] = ... = Var [Xτ ] 6= Var [Xτ +1 ] = ... = Var [XN ]}
and localize the change-point τ as precisely as possible or (in online setting) to
detect a break as soon as possible.
The approach proposed in the paper focuses on applications in neuroimagin
In the current study it is also assumed that some subset of indices Is ⊆ 1..N
of size s (possibly, s = N ) is chosen. The threshold is chosen relying on the

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure 3

sub-sample {Xi }i∈Is while the test-statistic is computed based on the whole
sample.
To this end we define a family of test statistics in Section 2.1 which is followed by Section 2.2 describing a data-driven (bootstrap) calibration scheme
and Section 2.3 describing change-point localization procedure. The theoretical
part of the paper justifies the proposed procedure in a high-dimensional setting.
The result justifying the validity of the proposed calibration scheme is stated
in Section 3. Section 4 is devoted to the sensitivity result yielding a bound for
the window size n necessary to reliably detect a break of a given extent and
hence bounding the uncertainty of the change-point localization (or the delay
of detection in online setting). The theoretical study is supported by a comparative simulation study (described in Section 5) demonstrating conservativeness
of the proposed test and higher sensitivity compared to the other algorithms.
Appendix A contains a finite-sample version of sensitivity result along with the
proofs. Appendix B provides a a finite-sample version of bootstrap sensitivity
result which is followed by the proofs. Finally, Appendix H lists results which
were essential for our theoretical study.
2. Proposed approach
This section describes the proposed approach along with a data-driven calibration scheme. Informally the proposed statistic can be described as follows.
Provided that the break may happen only at moment t, one could estimate
some parameter of the distribution using n data-points to the left of t, estimate
it again using n data-points to the right and use the norm of their difference
as a test-statistic An (t). Yet, in practice one does not usually possess such
knowledge, therefore we propose to maximize these statistics over all possible
locations t yielding An . Finally, in order to attain a trade-off between break detection sensitivity and change-point localization accuracy we build a multiscale
approach: consider a family of test statistics {An }n∈N for multiple window sizes
n ∈ N ⊂ N at once.
2.1. Definition of the test statistic
Now we present a formal definition of the test statistic. In order to detect a
break we consider a set of window sizes N ⊂ N. Denote the size of the widest
window as n+ and of the narrowest as n− . Given a sample of length N , for each
window size n ∈ N define a set of central points Tn := {n + 1, ..., N − n + 1}.
Next, for all n ∈ N define a set of indices which belong to the window on the left
side of the central point t ∈ Tn as Inl (t) := {t − n, ..., t − 1} and correspondingly
for the window on the right side define Inr (t) := {t, ..., t + n − 1}. Denote the
sum of numbers of central points for all window sizes n ∈ N as
X
T :=
|Tn | .
n∈N

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure 4

For each window size n ∈ N, each central point t ∈ Tn and each side S ∈ {l, r}
we define a de-sparsified estimator of precision matrix [23] [22] as
S
T
S
T S
S
T̂nS (t) := Θ̂S
n (t) + Θ̂n (t) − Θ̂n (t) Σ̂n (t)Θ̂n (t)

where
Σ̂S
n (t) =

1
n

X

Xi XiT

S (t)
i∈In

and Θ̂S
n (t) is a consistent estimator of precision matrix which can be obtained by
graphical lasso [31] or node-wise procedure [22] (see Definition 3.1 and Appendix
H.5 for details).
Now define a matrix of size p × p with elements
Zi,uv := Θ∗u Xi Θ∗v Xi − Θ∗uv

(2.1)


−1
where Θ∗ := E Xi XiT
for i ≤ τ , Θ∗u stands for the u-th row of Θ∗ . Denote
2 :=
Var [Z1,uv ] and introduce the diagonal matrix S =
their variances as σuv
diag(σ1,1 , σ1,2 ...σp,p−1 σp,p ). Denote a consistent estimator (see Definition 3.1 for
details) of the precision matrix Θ∗ obtained based on the sub-sample {Xi }i∈Is as
2
Θ̂ . In practice, the variances σuv
are unknown, but under normality assumption
2 :=
Θ̂uu Θ̂vv + Θ̂2uv which have been proven to be consistent
one can plug in σ̂uv
2
[23] [3]. If the node-wise procedure
(uniformly for all u and v) estimators of σuv
2
has been
is employed, the uniform consistency of an empirical estimate of σuv
shown under some mild assumptions (not including normality) [22].
For each window size n ∈ N and a central point t ∈ Tn we define a statistic
r
An (t) :=

n −1 l
S (T̂n (t) − T̂nr (t))
2

(2.2)
∞

where we write M for a vector composed of stacked columns of matrix M .
Finally we define our family of test statistics for all n ∈ N as
An = max An (t).
t∈Tn

Our approach heavily relies on the following expansion under H0
√

1
n(T̂nS (t) − Θ∗ ) = √
n

X

√
Zi + rnS (t) n,

S (t)
i∈In

where the residual term


 
∗
rnS (t) := T̂nS (t) − Θ∗ − Θ∗ Σ̂S
(t)
−
Σ
Θ∗
n
can be controlled under mild assumptions [23] [22] [3].

(2.3)

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure 5

This expansion might have been used in order to investigate the asymptotic
properties of An and obtain the threshold, however we propose a data-driven
scheme.
Remark 2.1. A different test statistic An (t) can be defined as the maximum distance between elements of empirical covariance matrices Σ̂(t)ln and Σ̂(t)rn . However, application to neuroimaging motivates the search for a structural change
in a functional connectivity network which is encoded by the structure of the
corresponding precision matrix. Clearly, a change in the precision matrix also
means a change in the covariance matrix, though we believe that the definition
(2.1) increases the sensitivity to this kind of alternative.
2.2. Bootstrap calibration
Our approach rejects H0 in favor of H1 if at least one of statistics An exceeds
the corresponding threshold x[n (α) or formally if ∃n ∈ N : An > x[n (α).
In order to properly choose the thresholds, we define bootstrap statistics
A[n in the following non-standard way. Note, that we cannot use an ordinary
scheme with replacement or weighted bootstrap since in a high-dimensional
case (|Is | ≤ p) the covariance matrix of bootstrap distribution would be singular
which would made inverse covariance matrix estimation procedures meaningless.
First, draw with replacement a sequence {κi }N
i=1 of indices from Is and denote
Xi[ = Xκi − EIs [Xj ]
where EIs [·] stands
for averaging over values of index belonging to Is e.g.,
P
EIs [Xj ] = |I1s | j∈Is Xj . Denote the measure Xi[ are distributed with respect
to as P[ . In accordance with (2.1) define
[
Zi,uv
:= Θ̂u Xi[ Θ̂v Xi[ − Θ̂uv

and for technical purposes define
Ẑi,uv := Θ̂u Xi Θ̂v Xi − Θ̂uv .
Now for all central point t define a bootstrap counterpart of An (t)

A[n (t) :=



1
√ S −1 
Zi[ −
Zi[ 
2n
r
l
i∈I (t)
i∈I (t)
X

X

n

n

(2.4)
∞

which is intuitively reasonable due to expansion (2.1). And finally we define the
bootstrap counterpart of An as
A[n = max A[n (t).
t∈Tn

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure 6

Now for each given x ∈ [0, 1] we can define quantile functions zn[ (x) such that
n
n
o
o
zn[ (x) := inf z : P[ A[n > z ≤ x .
Next for a given significance level α we apply multiplicity correction choosing
α∗ as
n
n
o
o
α∗ := sup x : P[ ∃n ∈ N : A[n > zn[ (x) ≤ α
and finally choose thresholds as x[n (α) := zn[ (α∗ ).
Remark 2.2. One can choose Is = 1, 2, ..., N and use the whole given sample
for calibration as well as for detection. In fact, it would improve the bounds in
Theorem 3.1 and Theorem 4.1, since it effectively means s = N . However, in
practise such a decision might lead to reduction of sensitivity due to overestimation of the thresholds.
2.3. Change-point localization
In order to localize a change-point we have to assume that Is ⊆ 1..τ . Consider
the narrowest window detecting a change-point as n̂:
n
o
n̂ := min n ∈ N : An > x[n (α)
(2.5)
and the central point where this window detects a break for the first time as
n
o
τ̂ := min t ∈ Tn̂ : An̂ (t) > x[n̂ (α) .
By construction of the family of test statistics we conclude (up to the confidence
level α) that the change-point τ is localized in the interval
[τ̂ − n̂; τ̂ + n̂ − 1] .
Clearly, if a non-multiscale version of the approach is employed, i.e. |N| = {n},
n = n̂ and the precision of localization (delay of the detection in online setting)
equals n.
3. Bootstrap validity
This section states and discusses the theoretical result demonstrating the validity of the proposed bootstrap scheme i.e.
n
o
P ∀n ∈ N : An ≤ x[n (α) ≈ 1 − α.
Our theoretical results require the tails of the underlying distributions to be
light. Specifically, we impose Sub-Gaussianity vector condition.

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure 7

Assumption 3.1 (Sub-Gaussianity vector condition).
"
 T 2 !#
a Xi
∃L : ∀i ∈ 1..N sup E exp
≤ 2.
L
a∈Rp
||a||2 ≤1

Naturally, in order to establish a theoretical result we have to assume that
a method featuring theoretical guaranties was used for estimating the precision
matrices. Such methods include graphical lasso [31], adaptive graphical lasso
[37] and thresholded de-sparsified estimator based on node-wise procedure [22].
These approaches overcome the high dimensionality of the problem by imposing
a sparsity assumption, specifically bounding the maximum number of non-zero
elements in a row: d := maxi {j|Θ∗ij 6= 0} . These approaches are guaranteed to
yield a root-n consistent estimate revealing the sparsity pattern of the precision
matrix [31, 3, 22] or formally
Definition 3.1. Consider an i.i.d. sample x1 , x2 , ...xn ∈ Rp . Denote their pre−1
cision matrix as Θ∗ = E [X1 ] . Let p and d grow with n. A positive-definite
matrix Θ̂n is a consistent estimator of the high-dimensional precision matrix if
!
r
log p
∗
n
Θ − Θ̂
= Op
n
∞
and
∀i, j ∈ 1..p and Θ∗ij = 0 ⇒ Θ̂nij = 0.
Graphical lasso and its adaptive versions impose an assumption, common for
`1 -penalized approaches.
Assumption 3.2 (Irrepresentability condition). Denote an active set

S := (i, j) ∈ 1..p × 1..p : Θ∗ij 6= 0
and define a p2 × p2 matrix Γ∗ := Θ∗ ⊗ Θ∗ where ⊗ denotes Kronecker product.
Irrepresentability condition holds if there exists ψ ∈ (0, 1] such that
max Γ∗eS (Γ∗SS )−1
e∈S
/

1

≤ 1 − ψ.

The interpretation of irrepresentability condition under normality assumption is given in [23] [31]. Particularly, Assumption 3.2 requires low correlation
between the elements of empirical covariance matrix from the active set S and
from its complement. The higher the constant ψ is, the stricter upper bound is
assumed.
These observations give rise to the two following assumptions.
Assumption 3.3.A. Suppose, either graphical
lasso or its adaptive version was
p
used with regularization parameter λn  log p/n and also impose Assumption
3.2.

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure 8

Assumption 3.3.B. Suppose, thresholded de-sparsified estimator
p based on nodewise procedure was used with regularization parameter λn  log p/n.
Now we are ready to establish a result which guarantees that the suggested
bootstrap procedure yields proper thresholds.
Theorem 3.1. Assume H0 holds and furthermore, let X1 , X2 , ...XN ∈ Rp be
i.i.d. Let Assumption 3.1 and either Assumption 3.3.A or Assumption 3.3.B
hold. Also assume, the spectrum of Θ∗ is bounded. Allow the parameters d, s, p, |N| , n− , n+
grow with N . Further let N > 2n+ , n+ ≥ n− and also impose the sparsity assumption

q

4
min s, n2−
.
d = o
3
|N| log10 (pN )
Then
n
o
P ∀n ∈ N : An ≤ x[n (α) − (1 − α) = oP (1).
The finite-sample version of this result, namely, Theorem B.1, is given in
Appendix B along with the proofs.
Bootstrap validity result discussion Theorem 3.1 guarantees under mild
assumptions (Assumption 3.2 seems to be the most restrictive one, yet it may
be dropped if the node-wise procedure is employed) that the first-type error
rate meets the nominal level α if the narrowest window size n− and the set Is
are large enough. Clearly, the dependence on dimensionality p is logarithmic
which establishes applicability of the approach in a high-dimensional setting.
It is worth noticing that, unusually, the sparsity bound gets stricter with N
but the dependence is only logarithmic. Indeed, we gain nothing from longer
samples, since we use only 2n data points each time.
On-line setting As one can easily see, the theoretical result is stated in offline setting, when the whole sample of size N is acquired in advance. In on-line
setting we suggest to control the probability α to raise a false alarm for at
least one central point t among N data points (which differs from the classical
techniques controlling the mean distance between false alarms [32]). Having α
and N chosen one should acquire s data-points (the set Is ), use the proposed
bootstrap scheme with bootstrap samples of length N in order to obtain the
thresholds. Next the approach can be naturally applied in on-line setting and
Theorem 3.1 guarantees the capability of the proposed bootstrap scheme to
control the aforementioned probability to raise a false alarm.
Proofs The proof of the bootstrap validity result, presented in Appendix B,
mostly relies on the high-dimensional central limit theorems obtained in [9], [8].
These papers also present bootstrap justification results, yet do not include a

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure 9

comprehensive bootstrap validity result. The theoretical treatment is complicated by the randomness of x[n (α). We overcome it by applying the so-called
“sandwiching” proof technique (see Lemma C.1), initially used in [33].
4. Sensitivity result
Consider the following setting. Let there be index τ , such that {Xi }i≤τ arei.i.d.
T
and {Xi }i>τ are i.i.d. as well. Denote precision matrices Θ−1
1 := E X1 X1 and


−1
T
Θ2 := E Xτ +1 Xτ +1 . Define the break extent ∆ as
∆ := ||Θ1 − Θ2 ||∞ .
The question is, how large the window size n should be in order to reliably reject
H0 and how firmly can we localize the change-point.
Theorem 4.1. Let Assumption 3.1 and either Assumption 3.3.A or Assumption
3.3.B hold. Also assume, the spectrums of Θ1 and Θ2 are bounded. Allow the
parameters d, s, p, |N| , n− , n+ grow with N and let ∆ decay with N . Further let
N > 2n+ , n+ ≥ n− ,
!
p
max{s, n− }
(4.1)
d=o
d log7 (pN )
and

log2 (pN )
= o(1).
n+ ∆

(4.2)

Then H0 will be rejected with probability approaching 1.
This result is a direct corollary of the finite-sample sensitivity result established and discussed in Appendix A.
The assumption Is ⊆ 1..τ is only technical. The result may be proven without
relying on it by methodologically the same argument.
Sensitivity result discussion Assumptions (Theorem 4.1) and (Theorem 4.1)
are essentially a sparsity bound and a bound for the largest window size n+ .
Clearly, they do not yield a particular value n+ necessary to detect a break, since
it depends on the underlying distributions, however, the result includes dimensionality p only under the sign of logarithm, which guarantees high sensitivity
of the test in high-dimensional setting.
Online setting Theorem 4.1 is established in offline setting as well. In online
setting it guarantees that the proposed approach can reliably detect a break of
an extent not less than ∆ with a delay at most n+ bounded by (Theorem 4.1).
Change-point localization guaranties Theorem 4.1 implies by construction of statistic An that the change-point can be localized with precision up to
n+ . Hence condition (Theorem 4.1) provides the bound for change-point localization accuracy.

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure10

5. Simulation study
5.1. Design
In our simulation we test

H0 = {Xi }N
i=1 ∼ N (0, I)
versus an alternative

H1 = ∃τ : {Xi }τi=1 ∼ N (0, I) and {Xi }N
i=τ +1 ∼ N (0, Σ1 )
The alternative covariance matrix Σ1 was generated in the following way. First
we draw k ∼ P oiss(3). The matrix Σ1 is composed as a block-diagonal matrix
of k matrices of size 2 × 2 with ones on their diagonals and their off-diagonal
element drawn uniformly from [−0.6; −0.3] ∪ [0.3; 0.6] and an identity matrix of
size (p − 2k) × (p − 2k). The dimensionality of the problem is chosen as p = 50,
the length of the sample N = 1000 and we choose the set Is = [1, 2, ..100], e.g.
τ > 100. The absence of positive effect of large sample size N is discussed in
Sections 3 and 4. Moreover, in all the simulations under alternative the sample
was generated with the change point in the middle: τ = N/2 but the algorithm
was oblivious about this as well as about either of the covariance matrices. The
significance level α = 0.05 was chosen.
In all the experiments graphical lasso
q
with penalization parameter λn = logn p was used in order to obtain Θ̂S
n (t). In
the same way, graphical lasso with penalization parameter λs was used in order
to obtain Θ̂.
We have also come up with an approach to the same problem not involving bootstrap. The paper [26] defines a high-dimensional two-sample test for
equality of matrices. Moreover, the authors prove asymptotic normality of their
statistic which makes computing p-value possible. We suggest to run this test
for every t ∈ Tn and every n ∈ N, adjust the obtained p-values using Holm
method [19] and eventually compare them against α.
The paper [27] suggests an approach based on comparing characteristic functions of random variables. The critical values were chosen with permutation
test as proposed by the authors. In our experiments the method was allowed to
consider all the sample at once. The R-package ecp [21] was used.
The first type error rate and power for our approach are reported in Table 1.
As one can see, our approach allows to properly control first type error rate. As
expected, its power is higher for larger windows and it is decreased by adding
narrower windows into consideration which is the price to be paid for better
localization of a change point.
In our study the approach proposed in [27] and the one based on the two
sample test [26] turned out to be conservative, but neither of them exhibited
power above 0.1.
Also, in order to justify application of multiscale approach (i. e. |N| > 1) for
the sake of better change-point localization we report the distribution of the

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure11
Table 1
First type error rate, power and precision of change-point localization of the proposed
approach for various sets of window sizes N
N
{70}
{100}
{140}
{70, 140}
{100, 140}
{70, 100, 140}

I type error rate
0.02
0.00
0.01
0.01
0.01
0.01

Power
0.09
0.37
0.81
0.76
0.75
0.74

Localization precision
70
100
140
135
124
123

Figure 2: Pie charts representing distribution of narrowest detecting window n̂
and the precision of localization in cases of |N| = {70, 140}, |N| = {100, 140}
and |N| = {70, 100, 140} respectively
100

100
70

70

140
140

140

narrowest detecting window n̂ (defined by (2.3)) over N in Figure 2. The Table
1 represents average precision of change-point localization for various choices
of set of window sizes N. One can see, that multiscale approach significantly
improves the precision of localization.
Appendix A: Proof of sensitivity result
Proof of Theorem 4.1. Proof consists in applying of the finite-sample Theorem
A.1. Its applicability is guaranteed by the consistency results given in papers
[31, 3, 22] and by the results from [23, 22, 3] bounding the term RT̂ . High
probability of set T↔ is ensured by Lemma G.1.
Theorem A.1. Let Is ⊆ 1..τ . Let Θ̂ denote a symmetric estimator of Θ1 s.t.
for some r ∈ R it holds that
Θ1 − Θ̂

∞

<r

and (Θ1 )ij = 0 ⇒ Θ̂ij = 0. Suppose Assumption 3.1 holds and there exists RT̂
such that

rnS+ (t)

∞

≤ RT̂ for all S ∈ {l, r} and t ∈ Tn+ on some set

n
∗
T↔ := ∀t ≤ τ − n+ : Σ̂S
n (t) − Σ1
n
\
∗
∀t ≥ τ + n+ : Σ̂S
n (t) − Σ2

∞
∞

≤ δ n+

o

o
≤ δ n+ .

Moreover, let the residual RAb defined in Lemma F.2 be bounded:

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure12

RAb ≤
Also let

r

where

α
.
6 |N|


n+
||S||∞ ∆ − 2RT̂ ≥ q,
2

s
q :=


2 (1 + ∆Y (r)) log

2N |N| p2
α − 3 |N| RAb

(A.1)


(A.2)

and ∆Y is defined in Lemma G.2. Then on set T↔ with probability at least
Y
1 − pΣ
s (x, q),
Y
where pΣ
s (x, q) is defined in Lemma G.2, H0 will be rejected.

Discussion of finite-sample sensitivity result The assumption (Theorem A.1)
is rather complicated. Here we note that if either graphical lasso [31], adaptive
graphical lasso [37] or thresholded de-sparsified estimator basedpon node-wise
procedure [22] with penalization parameter chosen as λs  o( log p/n) was
√
used, given d, s, p, N, n− , n+ → ∞, N > 2n+ , n+ ≥ n− , s ≥ n− and d = o( n+ )
it boils down to
2
1
n+ ≥ D 6
S −1 ∞ log(N |N| p2 )
∆
for some positive constant D6 independent of N, N, p, d, S while the parameters
q, γ and x may be chosen as in (B), (B), (B) (high probability of T↔ is ensured
by Lemma G.1). At the same time the remainder RAb can be bounded by (B).
As expected, the bound for sufficient window size decreases with growth of
the break extent ∆ and the size of the set Is , but increases with dimensionality
p. It is worth noticing, that the latter dependence is only logarithmic. And again,
in the same way as with Theorem 3.1, the bound increases with the sample size
N (only logarithmically) since we use only 2n data points.
Proof of Theorem A.1. Consider a pair of centered normal vectors
η :=

η1

η2

...

η |N|



∼ N (0, Σ∗Y ),

ζ :=

ζ1

ζ2

...

ζ |N|



∼ N (0, Σ̂Y ),

Σ∗Y :=

Σ̂Y :=

2n+
 
1 X
Var Y·jn ,
2n+ j=1
2n+
h
i
1 X
Var Y·jn[ ,
2n+ j=1

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure13

where vectors Y·jn and Y·jn[ are defined in proofs of Lemma E.2 and Lemma F.1
respectively. Lemma A.2 applies here and yields for all positive q


2
q
,
P {||ζ n+ ||∞ ≥ q} ≤ 2 Tn+ p2 exp −
2 Σ̂Y
∞

where Σ̂Y = Var [ζ] and Tn+ is the number of central points for window of
Y
size n+ . Applying Lemma G.2 on a set of probability at least 1 − pΣ
s (x, q)
yields Σ∗Y − Σ̂Y
construction,

∞

≤ ∆Y , and hence, due to the fact that ||Σ∗Y ||∞ = 1 by


P {||ζ n+ ||∞ ≥ q} ≤ 2 Tn+ p2 exp −

q2
2 (1 + ∆Y )


.

Due to Lemma F.2 and continuity of Gaussian c.d.f.
n
o
P[ A[n+ ≥ x[n+ (α) ≥ α/ |N| − 2RAb
and due to Lemma F.2 along with the fact that Tn+ < N , choosing q as
proposed by equation (Theorem A.1) we ensure that x[n+ (α) ≤ q.
Now by assumption of the theorem and by construction of the test statistics
An
r

n+
||S||∞ ∆ − 2RT̂ .
An + ≥
2
Finally, we notice that due to assumption (Theorem A.1) An+ > q and therefore,
H0 will be rejected.
Lemma A.1. Consider a centered random Gaussian vector ξ ∈ Rp with arbitrary covariance matrix Σ. For any positive q it holds that


n
o
q2
P max ξi ≥ q ≤ p exp −
.
i
2 ||Σ||∞
Proof. By convexity we obtain the following chain of inequalities for any t
h P i


2
etE[t maxi ξi ] ≤ E et maxi ξi ≤ E et i ξi ≤ pet ||Σ||∞ /2 .
Chernoff bound yields for any t
n
o pet2 ||Σ||∞ /2
P max ξi ≥ q ≤
.
i
etq
Finally, optimization over t yields the claim.
As a trivial corollary, one obtains
Lemma A.2. Consider a centered random Gaussian vector ξ ∈ Rp with arbitrary covariance matrix Σ. For any positive q it holds that


q2
P {||ξ||∞ ≥ q} ≤ 2p exp −
.
2 ||Σ||∞

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure14

Appendix B: Proof of bootstrap validity result
Proof of Theorem 3.1. Proof consists in applying of the finite-sample Theorem
B.1. Its applicability is guaranteed by the consistency results given in papers
[31, 3, 22] and by the results from [23, 22, 3] bounding the term RT̂ . High
probability of set TT is ensured by Lemma G.1.
Theorem B.1. Assume H0 holds and furthermore, let X1 , X2 , ...XN be i.i.d.
Let Θ̂ denote a symmetric estimator of Θ∗ s.t. for some positive r
Θ∗ − Θ̂

∞

<r

and Θ∗ij = 0 ⇒ Θ̂ij = 0. Suppose Assumption 3.1 holds and there exists RT̂
√
such that n rnS (t) ∞ ≤ RT̂ for all S ∈ {l, r}, n ∈ N and t ∈ Tn on set
n


T
TT := ∀S ∈ {l, r}, n ∈ N, t ∈ Tn : Σ̂S
n (t) − E X1 X1

∞

o
≤ δn .

Moreover, let
 α
±
(r) ≤ ,
R := (3 + 2 |N|) 2RA (RT̂ ) + 2RAb + RΣ
2
±
where the remainders RA , RAb , RΣ
are defined in Lemma E.1, Lemma F.2 and
±
Lemma C.1 respectively and the mis-tie ∆Y involved in the definition of RΣ
comes from Lemma G.2. Then on set TT it holds that
n
o
P ∀n ∈ N : An ≤ x[n (α) − (1 − α) ≤ R + 2(1 − q).

where
Σ
M
Y
q = 1 − pΣ
s (x, q) − p (γ) − ps (x)

(B.1)

Σ
M
Y
and the terms pΣ
s (x, q), p (γ) and ps (x) are defined in Lemma G.2, Lemma
G.1 and Lemma F.2 respectively.

Discussion of finite-sample bootstrap validity result The terms ∆Y ,
±
RA , RAb and RΣ
involved in the statement of Theorem B.1 are rather complicated. The exact expressions for them are provided by Lemma G.2, Lemma
E.1, Lemma F.2 and Lemma C.1 respectively, 3rd and 4th moments M33 and
M44 involved therein are bounded by Lemma E.4 and Lemma G.3 while asymptotic bounds for RT̂ are provided in [22] (for node-wise procedure) and [23] (for
graphical lasso). For the case of graphical lasso an explicit form of RT̂ is given
in [3].
Here we just note that if Θ̂ is a root-n consistent estimator, recovering sparsity pattern (graphical lasso [31], adaptive graphical lasso [37] or thresholded desparsified estimator based on node-wise procedure [22]), then for d, s, p, N, n− , n+ →
2
∞, N > 2n+ , n+ ≥ n− , s ≥ n− and nd− = o(1) given the spectrum of Θ∗ is
bounded

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure15


RAb ≤ D1

L4 d log7 (2p2 T n+ )
n−

1/6

log2 (ps).

(B.2)

If either graphical
q lasso, adaptive graphical lasso or node-wise procedure [28] is
used with λn  logn p in order to obtain Θ̂S
n (t), then on set TT it holds that
s
1/6
 4
log 2p2 T
L d log7 (2p2 T n+ )
+ D3
d log p.
RA ≤ D2
n−
n−
The high probability of TT may be ensured by means of Lemma G.1 e.g., choosing γ = log(500T ) for P {TT } ≥ 0.99. Further
L4 d2
∆Y ≤ D4 √ ,
s
±
RΣ


≤ D5

L4 d2
√
s

1/3

log2/3 (2p2 T ).

Here D1 , ..., D5 are positive constants independent of N , N, d, p and s. We also
note that the proper choice of x, γ and q in (Theorem B.1) is
x = 6,

(B.3)

γ = log(500T ),

(B.4)

q = 7 + 4 log(p)

(B.5)

which ensures the probability defined by (Theorem B.1) to be above 0.99. For
Σ
M
Y
exact expression of pΣ
s (x, q), p (γ) and ps (x) see Lemma G.2, Lemma G.1
and Lemma F.2.
Proof of Theorem B.1. The proof consists in application of Lemma F.1, Lemma
E.2 and Lemma D.1 justifying applicability of Lemma C.1.
Appendix C: Sandwiching lemma
Lemma C.1. Consider a normal multivariate vector η with a deterministic
covariance matrix and a normal multivariate vector ζ with a possibly random
covariance matrix such that
sup
{xn }n∈N ⊂R

|P {∀n ∈ N : An ≤ xn } − P {∀n ∈ N : ||ηn ||∞ ≤ xn }| ≤ RA , (C.1)

sup
{xn }n∈N ⊂R

n
o
P[ ∀n ∈ N : A[n ≤ xn − P[ {∀n ∈ N : ||ζn ||∞ ≤ xn } ≤ RAb ,
(C.2)

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure16

sup
{xn }n∈N ⊂R

n
o
P {∀n ∈ N : An ≤ xn } − P[ ∀n ∈ N : A[n ≤ xn ≤ R.

(C.3)

where ηn and ζn are sub-vectors of η and ζ respectively. Then
n
o
P ∀n ∈ N : An ≤ x[n (α) − (1 − α) ≤ (3 + 2 |N|) (R + RA + RAb ) .
Proof. Let us introduce some notation. Denote multivariate cumulative distribution function of An , A[n , ||ηn ||∞ , ||ζn ||∞ as P, P [ , N , N [ : R|N| → [0, 1] respectively. Define the following sets for all δ ∈ [0, α]
Z+ (δ) := {z : N (z) ≥ 1 − α − δ} ,

Z− (δ) := {z : N (z) ≤ 1 − α + δ}
and their boundaries
∂Z+ (δ) := {z : N (z) = 1 − α − δ} ,

(C.4)

∂Z− (δ) := {z : N (z) = 1 − α + δ} .
Consider δ = R + RA + RAb and denote sets Z+ = Z+ (δ), Z− = Z− (δ), ∂Z− =
∂Z− (δ), ∂Z+ = ∂Z+ (δ) Define a set of thresholds satisfying the confidence level
n
o
Z [ := z : P [ (z) ≥ 1 − α & ∀z1 < z : P [ (z1 ) < 1 − α
here and below comparison of vectors should be understood element-wise. Notice that due to continuity of multivariate normal distribution and assumption
(Lemma C.1) ∀z [ ∈ Z [
P [ (z [ ) − (1 − α) ≤ RAb .

(C.5)

Now for all z− ∈ ∂Z− and for all z [ ∈ Z [ it holds that
P [ (z− ) ≤ P (z− ) + R
≤ N (z− ) + R + RA
≤ 1 − α − RAb
≤ P [ (z [ )
where we have consequently used (Lemma C.1), (Lemma C.1), (C) and (C). In
the same way one obtains for all z+ ∈ ∂Z+ and for all z [ ∈ Z [
P [ (z+ ) ≥ P [ (z [ )

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure17

which implies that Z [ ⊂ Z− ∩ Z+ .
Now denote quantile functions of ||ηn ||∞ as z N : [0, 1] → R|N| :

∀n ∈ N : P ||ηn ||∞ ≥ znN (x) = x.
[

In exactly the same way define quantile functions z N : [0, 1] → R|N| of ||ζn ||∞ .
Clearly for all x ∈ [0, 1],
z N (x + δ) ≤ z [ (x) ≤ z N (x − δ)
and hence
z [ (α∗ ) ≤ z N (α∗ − δ) ≤ z [ (α∗ − 2δ),
1 − α ≤ P [ (z N (α∗ − δ)) ≤ P [ (z [ (α∗ − 2δ)).
Using Taylor expansion with Lagrange remainder term we obtain for some 0 ≤
κ ≤ 2δ


 [

N [ z [ (α∗ − 2δ) ≤ N [ z N (α∗ − 2δ) + δ
 [
 X
[
[
= N [ z N (α∗ ) +
∂zn[ N [ (z N (α∗ ))∂α znN (α∗ )κ + δ
n∈N

≤1−α+

X

[

[

∂zn[ N [ (z N (α∗ ))∂α znN (α∗ )κ + 3δ.

n∈N

Next successively using Lemma C.2 and the fact that the quantile function is
an inverse function of c.d.f. we obtain


N [ z [ (α∗ − 2δ) ≤ 1 − α + 3δ + 2δ |N|
and therefore


1 − α ≤ P [ z [ (α∗ − 2δ) ≤ 1 − α + δ (3 + 2 |N|) ,

1 − α ≤ P [ z N (α∗ − δ) ≤ 1 − α + δ (3 + 2 |N|) .
In the same way one obtains

1 − α − δ (3 + 2 |N|) ≤ P [ z N (α∗ + δ) ≤ 1 − α.
Next, by the argument used in the beginning of the proof we obtain
z N (α∗ + δ), z N (α∗ − δ) ∈ Z− (δ (3 + 2 |N|)) ∩ Z+ (δ (3 + 2 |N|)) .
As the final ingredient, we need to choose deterministic α+ and α− such that
N (z N (α− + δ)) = 1 − α − δ (3 + 2 |N|) ,
N (z N (α+ − δ)) = 1 − α + δ (3 + 2 |N|)

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure18

(which is possible due to continuity), so α− ≤ α∗ ≤ α+ and hence by monotonicity
z N (α− + δ) ≤ z N (α∗ + δ) ≤ z [ (α∗ ) ≤ z N (α∗ − δ) ≤ z N (α+ − δ)
and finally
1 − α − δ (3 + 2 |N|) ≤ P (z N (α− + δ))
≤ P (z [ (α∗ ))
≤ P (z N (α+ − δ))
≤ 1 − α + δ (3 + 2 |N|) .

Lemma C.2. Consider a random variable ξ and an event A defined on the
same probability space. Let c.d.f. P {ξ ≤ x} and P {ξ ≤ x&A} be differentiable.
Then
∂x P {ξ ≤ x&A}
≤1
∂x P {ξ ≤ x}
Proof. Indeed, denoting the complement of set A as A we obtain,
∂x P {ξ ≤ x&A}
∂x P {ξ ≤ x&A}


=
∂x P {ξ ≤ x}
∂x P {ξ ≤ x&A} + P ξ ≤ x&A
∂x P {ξ ≤ x&A}

∂x P {ξ ≤ x&A} + ∂x P ξ ≤ x&A
1
=
∂x P{ξ≤x&A}
1 + ∂x P{ξ≤x&A}

=

Using the fact that derivative of c.d.f. is non-negative we finalize the proof.
Appendix D: Similarity of joint distributions of {An }n∈N and
{A[n }n∈N
Lemma D.1. Under assumptions of Theorem 3.1 it holds that on set T with
probability at least
Σ
M
Y
1 − pΣ
s (x, q) − p (γ) − ps (x)
that
sup
{xn }n∈N ⊂R

n
o
±
P {∀n ∈ N : An ≤ xn } − P[ ∀n ∈ N : A[n ≤ xn ≤ RA +RAb +RΣ
.

Proof. The proof consists in applying Lemma F.1, Lemma E.2, Lemma G.2 and
Lemma H.3.

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure19

Appendix E: Gaussian approximation result for An
√
Lemma E.1. Suppose there exists RT̂ such that n rS (t)
and t on some set T . Then on set T it holds that

∞

≤ RT̂ for all S

sup |P {∀n ∈ N : An ≤ xn } − P {∀n ∈ N : ||η n ||∞ ≤ xn }| ≤ RA
x


p
1/6
:= CA F log7 (p2 T n+ )
+ 4RT̂ log(2p2 T ) .
where F is defined by (Lemma E.2) and η n by (Lemma E.2).
Proof. Substituting (2.1) to (2.1) yields


An (t) =



1
1
√ S −1 
Zi −
Z i  + √ (rnl − rnr )
2n
2
r (t)
l (t)
i∈In
i∈In
|
{z
}
X

X

n (t)
SZ

.

∞

Now denote stacked SZn (t) for all n ∈ N and as SZn and for all n as SZ . Lemma
E.2 bounds the c.d.f. of ||SZ ||∞ as
sup |P {∀n ∈ N : ||SZn ||∞ ≤ xn } − P {∀n ∈ N : ||η n ||∞ ≤ xn }| ≤ CA F log7 (p2 T n+ )

1/6

.

x

But clearly on set T
|An − ||SZn ||∞ | ≤

√

2RT̂

And hence for all {xn }n∈N ⊂ R
1/6
|P {∀n ∈ N : An < xn |T } − P {∀n ∈ N : ||η n ||∞ ≤ xn }| ≤ CA F log7 (p2 T n+ )
o
n
√
+ P ∀n ∈ N : ||η n ||∞ ≤ xn + 2RT̂
n
o
√
− P ∀n ∈ N : ||η n ||∞ ≤ xn − 2RT̂ .
Now notice that ∀i : (Σ∗Y )ii = 1 and bound the latter two terms by means of
Lemma H.2:
sup
{xn }n∈N

⊂R|N|

1/6
|P {∀n ∈ N : An < xn |T } − P {∀n ∈ N : ||η n ||∞ ≤ xn }| ≤ CA F log7 (p2 T n+ )
p
+ 4RT̂ ( log(2p2 T ))

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure20

Lemma E.2. Let Assumption 3.1 hold. Then
1/6
sup |P {∀n ∈ N : ||SZn ||∞ ≤ xn } − P {∀n ∈ N : ||η n ||∞ ≤ xn }| ≤ CA F log7 (2p2 T n+ )
x

Where
η1

η2

...

Σ∗Y =

1
F =
2n−

√

2
γ
β log 2 ∨ √
2−1

!2

η |N|



∼ N (0, Σ∗Y ),

(E.1)

N
1 X
Var [Y·i ] ,
N i=1

1
∨
2n+



n+
n−

1/3

s
M32

∨

1
M2
2n+ n− 4

(E.2)

with γ defined by (E), β by (E) and Y by (E) and an independent constant CA
.
Proof. Consider a matrix Yn with 2n+ columns
YnT

r

:=





















n+
×
n
Z1S
O
Z2S
Z2S
...
Z3S
S
...
Zn
S
S
−Zn+1
Zn+1
S
S
−Zn+2 −Zn+2
S
...
−Zn+3
S
−Z2n
...
S
O
−Z2n+1
O
O
...
...
O
O

...
O
...
...
...
...
...
...
...
...
...
...
...
O
S
... Z2n
+ −2n+1
S
... Z2n
+ −2n+2
...
...
S
... −Z2n
+ −1
S
...
−Z2n
+

S
−Z2n
+ +1
...
...
...
...
...
...
O
S
Z2n
+ −2n+2
...
S
−Z2n
+ −1
S
−Z2n
+

...
...
...
...
...
...
...
...
...
...
...
...






















where ZiS := (S −1 Z i )T . Clearly, columns of the matrix are independent and
SZn = √

2n+
1 X
(Yn )·l
2n+
l=0

Next define a block matrix composed of Yn matrices:


Y1
 Y2 

Y := 
 ... 
Y|N|

(E.3)

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure21

Clearly vectors Y·l are independent and
SZ = √

2n+
1 X
Y·l
2n+
l=0

In order to complete the proof we make use of Lemma H.1. Denote
r
Bn+ =

n+
n−

√

2
γ
β log 2 ∨ √
2−1

!


∨

n+
n−

1/6


M3 ∨

n+
n−

1/4
M4

(E.4)

By means of Lemma G.3 one shows that the assumptions of Lemma E.3 hold
for components of ZiS with
√
γ := 12L2 dΛ (Θ∗ ) ||Θ∗ ||∞ S −1 ∞
(E.5)

β :=


9 2√
L dΛ (Θ∗ ) + 1 ||Θ∗ ||∞ S −1
2

(E.6)

∞

where Λ (Θ∗ ) denotes the maximal eigen value of Θ∗ . Therefore condition (Assumption H.2)
holds with Bn defined by equation (E).
N
 S
1 X  n 2
E (Yij ) ≥ min Var Z1j
=1
j
N i=1

Hence, Assumption H.1 is fulfilled with b = 1. Next notice that for some k-th
component of ZiS and central point t (both defined by j):
2n+
1 X h n 3i
1
E Yij
=
2n+ i=1
2n+

=

1
2n+

X

"r
E

l (t)∪I r (t)
i∈In
n

X
l (t)∪I r (t)
i∈In
n

n+ S
Zik
n

 n 3/2
+

n

2n  n+ 3/2 h S 3 i
E Zik
2n+ n
r
n+ h S 3 i
=
E Zik
n
r
n+ 3
≤
M
n− 3
=

and in the same way:
N
1 X h n 4 i n+ 4
E Yij
M
≤
2n+ i=1
n− 4

3 #

h
i
S 3
E Zik

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure22

Therefore Assumption H.2 holds with Bn+ so Lemma H.1 applies here and
provides us with the claimed bound. Moreover, CA depends only on b which
equals one which implies that the constant CA depends on nothing.
Lemma E.3. Consider a random variable ξ. Suppose the following bound holds
∀x ≥ 0:
P {|ξ| ≥ γx + β} ≤ e−x
Then

 
|ξ|
E exp
≤2
B
for
√

B = β log 2 ∨ √

2
γ
2−1

Proof. Integration by parts yields

 
 


Z
|ξ|
β
γ +∞
γx + β
E exp
≤ exp
+
e−x dx
exp
B
B
B 0
B


 
Z +∞
γx + β
B
β
−x
exp
e dx =
exp
B
B
−
γ
B
0

 
 
|ξ|
B
β
E exp
≤
exp
B
B−γ
B
≤2

By the same technique the following lemma can be proven
Lemma E.4. Under assumptions of Lemma E.3
h i
3
E |ξ| ≤ β 3 + 3γβ 2 + 6βγ 2 + 2γ 3 ,
 
E ξ 4 ≤ β 4 + 4γβ 3 + 12β 2 γ 2 6βγ 3 + 24γ 4 .

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure23

Appendix F: Gaussian approximation result for A[n
Lemma F.1.
sup
{xn }n∈N ⊂R


1/6
n
o
.
P[ ∀n ∈ N : A[ ≤ xn − P[ {∀n ∈ N : ||ζ n ||∞ ≤ xn } ≤ ĈA[ F [ log7 (2p2 T n+ )

Where
ζ1

ζ2

Σ̂Y =

[

F =

1
1
∨
2n− log2 2 2n+

ζ |N|

...





∼ N (0, Σ̂Y ),

N
h i
1 X
Var Y·i[ ,
N i=1

n+
n−

s

1/3
∨

M [ = max Ẑi
i∈Is

1
2n+ n−

!
S −1

2
∞

(M [ )2

∞

Yn[ are defined by (F), and ĈA[ depends only on min1≤k≤p (Σ̂Y )kk
Proof. Denote the term under the sign of ||·||∞ in (2.2) as SZn[
SZn[


T
X
1  X
:= √
ZiS[ −
ZiS[ 
2n i∈I l (t)
r
i∈I (t)
n

n

where ZiS[ := (S −1 Zi[ )T and let SZ[ be a vector composed of stacked vectors SZn[
for all n ∈ N.
Consider a matrix

(Yn[ )T

r

:=






















n+
×
n
Z1S[
O
S[
Z2
Z2S[
...
Z3S[
S[
...
Zn
S[
S[
−Zn+1
Zn+1
S[
S[
−Zn+2 −Zn+2
S[
...
−Zn+3
S[
−Z2n
...
S[
O
−Z2n+1
O
O
...
...
O
O

...
O
...
...
...
...
...
...
...
...
...
...
...
O
S[
... Z2n
+ −2n+1
S[
... Z2n
+ −2n+2
...
...
S[
... −Z2n
+ −1
S[
...
−Z2n
+

S[
−Z2n
+ +1
...
...
...
...
...
...
O
S[
Z2n+ −2n+2
...
S[
−Z2n
+ −1
S[
−Z2n
+

...
...
...
...
...
...
...
...
...
...
...
...























(F.1)

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure24

which is a bootstrap counterpart of Yn from the proof of Lemma E.2 and construct a block matrix Y [ :

Y1[
 Y2[ 

Y[ =
 ... 
[
Y|N|


Clearly vectors Y·l[ are independent and
SZ[ = √

N
1 X [
Y·l
2n+
l=0

Now notice
N
i rn
1 X h
+
3
E |Yij | ≤
max Ẑi
2n+ i=1
n− i∈Is
N
i n
1 X h
+
4
E |Yij | ≤
max Ẑi
2n+ i=1
n− i∈Is

3

S −1

∞
4
∞

S −1

3
∞

4
∞

And finally apply Lemma H.1.
Lemma F.2. Let Θ̂ denote an estimator of Θ∗ s.t. for some positive r
Θ∗ − Θ̂

∞

<r

and Θ∗ij = 0 ⇒ Θ̂ij = 0, furthermore, let ∆Y (r) < 1/2, also suppose Assumption
ΣY
3.1 holds. Then at least with probability 1 − pM
s (x) − ps (x, q)
sup
{xn }n∈N ⊂R

n
1/6
o

P[ ∀n ∈ N : A[ ≤ xn − P[ {∀n ∈ N : ||ζ n ||∞ ≤ xn } ≤ RAb := CA[ F̂ log7 (2p2 T n+ )

where
F̂ =

1
1
∨
2
2n− log 2 2n+



n+
n−

s

1/3
∨

1
2n+ n−

!
S −1

2
∞

(C [ )2

C [ := Zs (x) + (3(dx)2 + 1)r
and constant CA[ depends only on ∆Y .
Proof. The proof consists in subsequently applying Lemma F.1 and Lemma F.3
ensuring C [ ≥ M [ = maxi∈Is Ẑi
with probability at least 1−pM
s (x) and ap∞

plying Lemma G.2 providing that Σ∗Y − Σ̂Y

∞

≤ ∆Y ≤ 1 = min1≤k≤p (Σ∗Y )kk

Y
with probability at least 1 − pΣ
s (x, q) which implies the existence of a deterministic constant CA[ > ĈA[ .

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure25

Lemma F.3. Let Θ̂ denote an estimator of Θ∗ s.t. for some positive r
Θ∗ − Θ̂

∞

<r

and Θ∗ij = 0 ⇒ Θ̂ij = 0. Also let Assumption 3.1 hold. Then with probability at
least 1 − pM
s (x)
M [ ≤ Zs (x) + ∆Z (x)
where

pM
s (x)

:= pZs (x) +

(F.2)

pX
s (x).

Proof. Direct application of Lemma G.4 yields
P {∀i ∈ Is : ||Zi ||∞ ≤ Zs (x)} ≥ 1 − pZs (x)
which in combination with the fact (provided by Lemma G.6) that Ẑi − Zi

∞

≤

∆Z (x) implies (Lemma F.3).

Appendix G: Σ̂Y ≈ Σ∗Y
h i
 
First of all, if Σ∗Z := Var Zi ≈ Var[ Zi[ , then Σ∗Y ≈ Σ̂Y as well (Lemma G.2).
The idea is to notice that

h i
h i 
h iT 
Cov Zi[ = Σ̂Ẑ := EIs Ẑi − EIs Ẑi
Ẑi − EIs Ẑi
due hto the choice of the bootstrap scheme.
Next we show that Σ∗Z ≈ Σ̂Z :=
 
 T i
Zi − EIs Zi
(Lemma G.5) and finalize the proof by
EIs Zi − EIs Zi
proving that Σ̂Z ≈ Σ̂Ẑ (Lemma G.7).
The results of this section rely on a lemma which is a trivial corollary of
Lemma 6 by [23] providing the concentration result for the empirical covariance
matrix
Lemma G.1. Let Assumption 3.1 hold for some L > 0. Then for any positive
γ
!
r
2 log p + χ
4 log p + 2χ
2
δn (χ) := 2L
+
n
n
n
o
≥ δn (γ) ≤ pΣ (γ) := 2e−χ .
P Σ̂ − Σ∗
∞

Lemma G.2. Assume, Assumption 3.1 holds. Moreover, let


EIs Xi XiT − Σ∗

∞

≤ δs

and let Θ̂ denote a symmetric estimator of Θ∗ s.t.

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure26

Θ∗ − Θ̂

∞

<r

and Θ∗ij = 0 ⇒ Θ̂ij = 0. Then for positive x and q
o
n
Y
≥ ∆Y ≤ p Σ
P Σ̂Y − Σ∗Y
s (x, q)
∞

where
ΣZ1
Z2
Y
(x, q) + pΣ
(x)
pΣ
s (x, q) := ps
s

∆Y := S −1
(1)

2
∞



(1)
(2)
∆ΣZ + ∆ΣZ

(2)

Z1
Z2
and ∆ΣZ and ∆ΣZ along with the probabilities pΣ
(x, q) and pΣ
(x) are defined
s
s
in Lemma G.5 and Lemma G.7 respectively.

Proof. Notice that
Σ̂Y − Σ∗Y

∞

= S −1 Σ̂Ẑ S −1 − S −1 Σ∗Z S −1

∞

≤ S −1

2
∞

Σ̂Ẑ − Σ∗Z

∞

because the matrices Σ̂Y and Σ∗Y are composed of blocks S −1 Σ̂Z S −1 and S −1 Σ∗Z S −1
respectively, each block multiplied by some positive value not greater than 1
(which can be verified by simple algebra).
By Lemma G.7 and Lemma G.5
Σ̂Ẑ − Σ∗Z

(1)

∞

(2)

≤ ∆ΣZ + ∆ΣZ

and hence
Σ̂Y − Σ∗Y

∞

≤ S −1

2
∞

(1)

(2)

(∆ΣZ + ∆ΣZ )

with probability at least
Z1
Z2
1 − pΣ
(x, q) − pΣ
(x)
s
s

Lemma G.3. Under Assumption 3.1 it holds for arbitrary 1 ≤ u, v ≤ p and
positive x that






√
3
2
∗
∗
+ 4x + 1 ||Θ ||∞ ≥ 1 − e−x
P |Z1,uv | ≤ 3L dΛ (Θ )
2
Proof. Re-write the definition (2.1) of an element Zi,uv for arbitrary 1 ≤ u, v ≤ p
Zi,uv = Θ∗u Xi Θ∗v Xi − Θ∗uv


= XiT Θ∗u (Θ∗v )T Xi − Θ∗uv .

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure27

The first term is clearly a value of a quadratic form defined by the matrix
B = Θ∗u (Θ∗v )T . Note that rankB = 1 which implies that it is either positive
semi-definite or negative semi-definite. Next we apply Lemma H.4 and obtain
for all positive x
n
P

o

p
≤ e−x .
XiT BXi ≥ 3L2 |trB| + 2 tr(B 2 )x + 2 |Λ (B)| x

Again, due to the fact that B is a rank-1 matrix
√
trB = Λ (B) = trB 2

(G.1)

(G.2)

and by construction of matrix B
|trB| = Θ∗u (Θ∗v )T
≤ ||Θ∗u ||1 ||Θ∗ ||∞
√
≤ d||Θ∗u ||2 ||Θ∗ ||∞
√
≤ dΛ (Θ∗ ) ||Θ∗ ||∞ .

(G.3)

Substitution of (G) and (G) to (G) yields
n
√
o
√
P XiT BXi ≥ 3L2 dΛ (Θ∗ ) ||Θ∗ ||∞ 1 + 2 x + 2x ≤ e−x .
√
And since x ≤ x + 14



√
3
T
2
∗
∗
P Xi BXi ≥ 3L dΛ (Θ ) ||Θ ||∞
+ 4x
≤ e−x .
2
Finally, we obtain a bound for Zi,uv as






√
3
+ 4x + 1 ||Θ∗ ||∞ ≤ e−x .
P |Zi,uv | ≥ 3L2 dΛ (Θ∗ )
2

Correction for all i, u and v establishes the following result
Lemma G.4. Consider an i.i.d. sample Xi of length n. Under Assumption 3.1
for positive x it holds that
P {∀i ∈ {1..n} : ||Zi ||∞ ≤ Zn (x)} ≥ 1 − pZn (x)
where

Zn (x) :=

2

3L

√

∗

dΛ (Θ )





3
2
+ 4 log p n + 4x + 1 ||Θ∗ ||∞ ,
2

pZn (x) := e−x .

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure28

Lemma G.5. Under Assumption 3.1 for positive x and q
o
n
(1)
Z1
≥ ∆ΣZ ≤ pΣ
(x, q)
P Σ̂Z − Σ∗Z
s
∞

where

(1)
∆ΣZ


∗
4Zs2 (x) + s−1
s
s ||ΣZ ||∞ q
:=
s−1
3s

s
1+

1+

!

2
9sσW

q 4Zs2 (x) +

s−1
s

||Σ∗Z ||∞

2

Z1
pΣ
(x, q) := p4 e−q + pZs (x)
s

Proof. Denote
 
 
s−1 ∗
ΣZ
W (i) := (Z i − EIs Zi )(Z i − EIs Zi )T −
s
and note that
 1X
s−1
W (i) .
Σ̂Z − Σ∗Z =
s
s
i∈Is

By Lemma G.4 we have ||Zi ||∞ ≤ Zs (x) with probability at least 1 − pZs (x)
(i)
∗
which implies W (i) ∞ ≤ 4Zs2 (x) + s−1
s ||ΣZ ||∞ . Since Wkl are i.i.d., bounded
and centered, Bernstein inequality applies here:
(

i
h
4Zs2 (x) +
(i)
P EIs Wkl ≥
where
(
P

2
σW

s−1
s


||Σ∗Z ||∞ q

3s

s
1+

1+
q

is the smallest variance of components of W

h
i
EIs W (i)

∞

≥

4Zs2 (x) +

s−1
s


||Σ∗Z ||∞ q

3s

(i)

4Zs2 (x)

+

s−1
s

2
||Σ∗Z ||∞

1+

!)

2
9sσW

q 4Zs2 (x) +

s−1
s

||Σ∗Z ||∞

The following lemma bounds the mis-tie between Zi and Ẑi .
Lemma G.6. Let Assumption 3.1 holds and let Θ̂ be a symmetric estimator of
Θ∗ s.t.
Θ∗ − Θ̂

∞

<r

and Θ∗ij = 0 ⇒ Θ̂ij = 0. Then for positive x
n
o
P ∀i ∈ Is : Zi − Ẑi
≤ ∆Z (x) ≥ 1 − pX
s (x)
∞

where

≤ e−q

. Therefore

s
1+

!)

2
9sσW

2

≤ p4 e−q .

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure29

∆Z (x) := 2rd3/2 x2 ||Θ∗ ||∞ + (rdx)2
−x
pX
s (x) := se

2

/L2

Proof. Due to sub-Gaussianity,
∀α ∈ Rp : P



αT Xi ≤ x ≥ 1 − se−x

2

/L2

(G.4)

Now consider the mis-tie of arbitrary elements Zi,uv and Ẑi,uv :
Zi,uv − Ẑi,uv = Θ∗u Xi Θ∗v Xi + Θ∗uv − Θ̂u Xi Θ̂v Xi − Θ̂uv
≤ (Θ∗u − Θ̂u )Xi Θ∗v Xi + (Θ∗u − Θ̂u )Xi Θ̂v Xi + r
Now note that due to (G) and assumptions imposed on Θ∗
√
|Θ∗v Xi | ≤ d ||Θ∗ ||∞ x
(Θ∗v − Θ̂v )Xi ≤ rdx
Θ̂v Xi ≤ |Θ∗v Xi | + (Θ∗v − Θ̂v )Xi ≤

√

d ||Θ∗ ||∞ x + rdx

And hence
Zi,uv − Ẑi,uv ≤ 2rd3/2 x2 ||Θ∗ ||∞ + (rdx)2

Lemma G.7. Assume Assumption 3.1 holds. Let Θ̂ be a symmetric estimator
of Θ∗ s.t.
Θ∗ − Θ̂

∞

<r

and Θ∗ij = 0 ⇒ Θ̂ij = 0. Then for positive x
n
o
(2)
Z2
P
Σ̂Z − Σ̂Ẑ
≥ ∆ΣZ ≤ pΣ
(x)
s
∞

where
psΣZ2 (x) := pX
s (x) + pZs (x)
(2)

∆ΣZ = ∆Z (x)(2Zs (x) + ∆Z (x))

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure30

Proof. By Lemma G.4 with probability at least 1 − pZs (x) we have ||Zi ||∞ ≤
Zs (x) and in combination with Lemma G.6 we obtain Ẑi
with probability at least 1 − pZs (x) −

pX
s (x).

∞

≤ Zs (x) + ∆Z (x)

Now denote
h i
 
ξi := Zi − EIs Zi and ξˆi := Ẑi − EIs Ẑi

And deliver the bound
Σ̂Z − Σ̂Ẑ

∞

h
i
≤ EIs ξi (ξi − ξˆi )T + (ξi − ξˆi )ξˆiT


+ ||ξi ||∞ ξi − ξˆi
ξˆi
≤
∞

∞

≤ ∆Z (x)(2Zs (x) + ∆Z (x))

Appendix H: Known results
H.1. Gaussian approximation result
In this section we briefly describe the result obtained in [9].
Throughout this section consider an independent sample x1 , ..., xn ∈ Rp of
centered random variables. Define their Gaussian counterparts yi ∼ N (0, Var [xi ])
and denote their scaled sums as
n

1 X
xi
SnX := √
n i=1
n

1 X
yi
SnY := √
n i=1
Definition H.1. We call a set A of the form A = {w ∈ Rp : ai ≤ wi ≤ bi ∀i ∈
{1..p}} a hyperrectangle. The family of all hyperrectangles is denoted as Are .
Assumption H.1. ∃b > 0 such that
n

1X  2
E xij ≥ b for all j ∈ 1..p
n i=1
Assumption H.2. ∃Gn ≥ 1 such that
n

i
1X h
2+k
≤ G2+k
for all j ∈ 1..p and k ∈ {1, 2}
E |xij |
n
n i=1



|xij |
E exp
≤ 2 for all j ∈ 1..p and i ∈ 1..n
Gn

(H.1)

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure31

Lemma H.1 (Proposition 2.1 by [9]). Let Assumption H.1 hold for some b and
Assumption H.2 hold for some Gn . Then


sup P SnX ∈ A − P SnY ∈ A


≤C

A∈Are

G2n log7 (pn)
n

1/6

and the constant C depends only on b.
H.2. Anti-concentration result
Lemma H.2 (Nazarov’s inequality [30]). Consider a normal p-dimensional
vector X ∼ N (0, Σ) and let ∀i : Σii = 1. Then for any y ∈ Rp and any positive
a
p
P {X ≤ y + a} − P {X ≤ y} ≤ Ca log p,
where C is an independent constant.
H.3. Gaussian comparison result
By the technique given in the proof of Theorem 4.1 by [9] one obtains the
following generalization of the result given in [7]
Lemma H.3. Consider a pair of covariance matrices Σ1 and Σ2 of size p × p
such that
||Σ1 − Σ2 ||∞ ≤ ∆
and ∀k : C1 ≥ Σ1,kk ≥ c1 > 0. Then for random vectors η ∼ N (0, Σ1 ) and
ζ ∼ N (0, Σ2 ) it holds that
sup |P {η ∈ A} − P {ζ ∈ A}| ≤ C∆1/3 log2/3 p,

A∈Are

where C is a positive constant which depends only on C1 and c1 .
H.4. Tail inequality for quadratic forms
The following result is a direct corollary of Theorem 1 in [20]
Lemma H.4. Consider a positive semi-definite or negative semi-definite matrix
B and suppose Assumption 3.1 holds. Then for all t > 0
n

o
p
P X1T BX1 ≥ 3L2 |trB| + 2 tr(B 2 )t + 2 |Λ (B)| t
≤ e−t
H.5. High-dimensional precision matrix estimation
In order to address the problem of high-dimensional precision matrix estimation
one has to assume its sparsity. Below we describe two approaches exploiting this
assumption. In both of them we assume that an i.i.d. sample X1 , ...Xn ∈ Rp is
supplied.

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure32

H.5.1. Graphical lasso
In [17] the graphical lasso approach was suggested. An estimate may be obtained
as the solution of the following optimization problem over a positive-definite
p
cone S++
of p × p dimensional matrices.
h
i
Θ̂GL := arg min
tr(ΘΣ̂) − log detΘ + λ ||Θ||1
(H.2)
p
Θ∈S++

where Σ̂ stands for the empirical covariance matrix
n

Σ̂ =

1X
Xi XiT .
n i=1

The theoretical treatment of the approach keeps track on the following Schatten norms: κΣ∗ = |||Σ∗ |||∞ and κΓ∗ =
(Γ∗SS )−1 ∞ . The following result
establishes consistency of the estimator in the sense of Definition 3.1.
Lemma H.5 (Theorem 1, [31]). Consider a distribution satisfying Assumption
3.2 with some φ ∈ (0, 1], let Θ̂ be a solution of the optimization problem (H.5.1)
with tuning parameter λn = ψ8 δn . Furthermore, impose the following sparsity
assumption:
1
d≤
.
6(δn + λn ) max{κΓ∗ κΣ∗ , κ2Γ∗ κ3Σ∗ }
n
o
Σ̂ − Σ∗
< δn the following holds:
Then on the set T =
∞

Θ̂GL − Θ∗

∞

≤ rλ := 2κΓ∗ (δn + λn )

and
Θ∗ij = 0 ⇒ Θ̂ij = 0.
A rather similar result is provided in paper [3] for adaptive versions of graphical lasso suggested and studied in [38] [15] [16] [37] .
H.5.2. Node-wise lasso
This section describes the node-wise lasso approach which was suggested in [28].
For each 1 ≤ j ≤ n define a vector
Γ̂j := (γ̂j 1 , ..., γ̂j j−1 , 1, γ̂j j+1 , ..., γ̂j p )
where γ̂j is defined as a solution of the following lasso regression:
γ̂j := arg max
p−1
γ∈R

1 X
n

1≤i≤n

T
Xij − Xi,−j
γ

2

+ 2λ ||γ||1

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure33

and
τ̂j2 :=

1 X
n

T
Xij − Xi,−j
γ̂j

2

+ λ ||γ||1 .

1≤i≤n

Finally the j-th column of the estimator is defined as
B
:= Γ̂j /τ̂j2 .
Θ̂M
j

Note, that this estimator might not be symmetric, so one cannot use it as
an estimator Θ̂ based on the sub-sample {Xi }i∈Is . The paper [22] suggests to
construct a de-sparsified estimator T̂ (Θ̂M B ) where
T̂ (Θ̂) := Θ̂ + Θ̂T − Θ̂T Σ̂Θ̂
and threshold elements of T̂ obtaining a positive-definite estimate.
p
= o(1) and the asUnder Assumption 3.1, the sparsity assumption d log
n
sumption of the bounded spectrum (Assumption H.3) the paper [22] establishes
the root-n consistency of such an estimator (see Definition 3.1).
Assumption H.3.
∃E :

1
≤ λ (Θ∗ ) ≤ Λ (Θ∗ ) ≤ E.
E

H.5.3. Bounds for r
While graphical lasso and node-wise estimate are point estimates, de-sparsified
estimators have been suggested in order to obtain confidence intervals [23] [22].
The analysis of these estimators relies on the bounds for the residual term r:


r := T̂ − Θ∗ − Θ∗ (Σ∗ − Σ̂)Θ∗
The next two lemmas bound the remainder r for the case of graphical lasso
and node-wise estimator.
Lemma H.6 (by [23]). Impose Assumption 3.1, Assumption 3.2 and Assumption H.3. Then under the sparsity assumption
d log p
√
= o(1)
n

(H.3)

it holds that

||r||∞ = Op

d log p
n


.

A finite sample-size bound for r along with its adaptations for the case of
adaptive graphical lasso may be found in [3]

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure34

Lemma
H.7 (by [22]). Let Θ̂ be yielded by the node-wise procedure with λn 
q
log p
n . Then under Assumption 3.1, Assumption H.3 and sparsity assumption
(Lemma H.6)


d log p
||r||∞ = Op
.
n
Acknowledgements
We thank Vladimir Spokoiny and Karsten Tabelow for comments and discussions that greatly improved the manuscript.
References
[1] Alexander Aue and Lajos Horvath. Structural breaks in time series. Journal
of Time Series Analysis, 34(1):1–16, 2013.
[2] Alexander Aue, Siegfried Hörmann, Lajos Horváth, and Matthew
Reimherr. Break detection in the covariance structure of multivariate time
series models. Ann. Statist., 37(6B):4046–4087, 12 2009.
[3] Valeriy Avanesov, Jörg Polzehl, and Karsten Tabelow. Consistency results
and confidence intervals for adaptive l1-penalized estimators of the highdimensional sparse precision matrix. Technical Report 2229, WIAS, 2016.
[4] Danielle S. Bassett, Nicholas F. Wymbs, Mason a. Porter, Peter J. Mucha,
Jean M. Carlson, and Scott T. Grafton. Dynamic reconfiguration of human
brain networks during learning. Proceedings of the National Academy of
Sciences, 108(18):7641, 2010.
[5] Luc Bauwens, Sébastien Laurent, and Jeroen V K Rombouts. Multivariate
GARCH models: a survey. Journal of Applied Econometrics, 21(1):79–109,
jan 2006.
[6] Gérard Biau, Kevin Bleakley, and David M. Mason. Long signal changepoint detection. Electron. J. Statist., 10(2):2097–2123, 2016.
[7] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Comparison
and anti-concentration bounds for maxima of gaussian random vectors.
Dec 2013.
[8] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Gaussian
approximations and multiplier bootstrap for maxima of sums of highdimensional random vectors. Ann. Statist., 41(6):2786–2819, 12 2013.
[9] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Central limit
theorems and bootstrap in high dimensions. Dec 2014.
[10] Haeran Cho. Change-point detection in panel data via double cusum statistic. Electron. J. Statist., 10(2):2000–2038, 2016.
[11] 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(2):475–507, 2015.

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure35

[12] Mihaela Şerban, Anthony Brockwell, John Lehoczky, and Sanjay Srivastava. Modelling the dynamic dependence structure in multivariate financial
time series. Journal of Time Series Analysis, 28(5):763–782, 2007.
[13] Miklós Csörgő and Lajos Horváth. Limit theorems in change-point analysis.
Wiley series in probability and statistics. J. Wiley & Sons, Chichester, New
York, 1997.
[14] Robert F. Engle, Victor K. Ng, and Michael Rothschild. Asset pricing with
a factor-arch covariance structure. Empirical estimates for treasury bills.
Journal of Econometrics, 45(1-2):213–237, 1990.
[15] Jianqing Fan, Yang Feng, and Yichao Wu. Network exploration via the
adaptive lasso and scad penalties. Ann. Appl. Stat., 3(2):521–541, 06 2009.
[16] Jianqing Fan and Li R. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American Statistical Association, 96:1348–1360, 2001.
[17] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Sparse inverse
covariance estimation with the graphical lasso. Biostatistics, 9(3):432–441,
July 2008.
[18] Karl J. Friston. Functional and effective connectivity: A review. Brain
Connectivity, 1(1):13–36, 2011.
[19] S. Holm. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6:65–70, 1979.
[20] Daniel Hsu, Sham M. Kakade, and Tong Zhang. A tail inequality for
quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17(0), January 2012.
[21] Nicholas A. James and David S. Matteson. ecp: An R package for nonparametric multiple change point analysis of multivariate data. Journal of
Statistical Software, 62(7):1–25, 2014.
[22] Jana Janková and Sara van de Geer. Honest confidence regions and optimality in high-dimensional precision matrix estimation. TEST, 26(1):143–162,
2017.
[23] Jana Janková and Sara van de Geer. Confidence intervals for highdimensional inverse covariance estimation. Electron. J. Statist., 9(1):1205–
1229, 2015.
[24] Moritz Jirak. Uniform change point tests in high dimension. Ann. Statist.,
43(6):2451–2483, 12 2015.
[25] M. Lavielle and G. Teyssière. Detection of multiple change-points in multivariate time series. Lithuanian Mathematical Journal, 46(3):287–306, 2006.
[26] Jun Li and Song Xi Chen. Two sample tests for high-dimensional covariance
matrices. Ann. Statist., 40(2):908–940, 04 2012.
[27] 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(505):334–345, 2014.
[28] Nicolai Meinshausen and Peter Bühlmann. High-dimensional graphs and
variable selection with the lasso. Ann. Statist., 34(3):1436–1462, 06 2006.
[29] Thomas Mikosch, Søren Johansen, and Eric Zivot. Handbook of Financial
Time Series. Time, 468(1996):671–693, 2009.

V. Avanesov, N. Buzun/Change-point detection in high-dimensional covariance structure36

[30] Fedor Nazarov. On the maximal perimeter of a convex set in Rn with
respect to a Gaussian measure, pages 169–187. Springer Berlin Heidelberg,
Berlin, Heidelberg, 2003.
[31] Pradeep Ravikumar, Martin J. Wainwright, Garvesh Raskutti, and Bin
Yu. High-dimensional covariance estimation by minimizing l1-penalized
log-determinant divergence. Electron. J. Statist., 5:935–980, 2011.
[32] A.N. Shiryaev. Optimal Stopping Rules. Stochastic Modelling and Applied
Probability. Springer Berlin Heidelberg, 2007.
[33] V. Spokoiny and N. Willrich. Bootstrap tuning in ordered model selection.
ArXiv e-prints, July 2015.
[34] O. Sporns. Networks of the brain. The MIT Press, 2011.
[35] Yao Xie and David Siegmund. Sequential multi-sensor change-point detection. Ann. Statist., 41(2):670–692, 04 2013.
[36] Changliang Zou, Guosheng Yin, Long Feng, and Zhaojun Wang. Nonparametric maximum likelihood approach to multiple change-point problems.
Ann. Statist., 42(3):970–1002, 06 2014.
[37] H. Zou. The adaptive lasso and its oracle properties. Journal of the American Statistical Association, 101(476):1418–1429, 2006.
[38] Hui Zou and Runze Li. One-step sparse estimates in nonconcave penalized
likelihood models. Ann. Statist., 36(4):1509–1533, 08 2008.

