This paper proposes a new structural change point detection method for time series using our new matrix decomposition method. We propose YMN decomposition which decomposes one time-series data matrix into a large random matrix and a sparse matrix. YMN decomposition can obtain the information about the latent structure from the sparse matrix. Thus our structural change point detection method using YMN decomposition can detect the change in higher-order moments of a mixing matrix as well as typical structural changes such as the change in mean, variance, and autocorrelation of time series. We also partly theorize our methods using existing theories of random matrix and statistics. Our experiment using artificial data demonstrates the efectiveness of our change point detection techniques and our experiment using real data demonstrates that our methods can detect structural changes in economics and finance.
Unveiling the model of time-series data is necessary to explain
the causal relationships and to forecast the future. In economic
and financial modeling, the models of time-series data are not
apparent in many cases; moreover, their models are time varying
[
Structural change point detection is dificult because we do
not know the structure of the time-series before/after the change
point, and how the change occurs. However, factor modeling is
typically used to unveil the partial structures in economics [
yt = Azt . ∗This work was performed when the author was an intern at Preferred Networks, Inc.
science yt (observed)
zt (latent) Motion of parts Waves from parts
Structure of data
Structure
Economic
Structure
Structure
of Market
zt is a low-dimensional time-variant vector of factors, while A is
a time-invariant coeficient matrix. A is called “factor loadings”
in the context of econometrics and “mixing matrix” in the context
of computer science. A implies the latent “structure” behind the
observed data. However, the structure may be changed abruptly
in reality because of major economic or political events such
as Brexit or the Global Financial Crisis. Most of the work
performed by economists and quantitative financial analysts, such
as the prediction and explanation of time-series, strongly rely on
their models [
The change exhibits several patterns. The simplest one is the
change in the mean and variance of A’s entities; it can be detected
by merely calculating the mean and variance of y. The change
in the numbers of factors and the change in the autocorrelation
of y are also the essential but straightforward ones [
Many previous studies showed the efectiveness of linear
models in detecting the structural changes of high-dimensional
data. Well-known methods such as principal component analysis
(PCA), non-negative matrix factorization (NMF), and
independent component analysis (ICA) can be interpreted as methods to
1This interpretation of the central limit theorem is often used in ICA literature
[
We herein propose a new non-parametric change point
detection method of the structures of multidimensional time series.
Our method decomposes the observed data matrix into a large
random matrix and a sparse coeficient matrix. First, we use
randomly generated large matrices as latent time series. However,
when a large random time series row vectors is generated, most
of its row vectors are not related to the latent time series, and
some are close to the latent time series. Therefore, we select good
row vectors by applying a sparse matrix to this. Finally, we can
detect the structural changes by calculating the diference of the
sparse matrix. Some previous works reported similar frameworks
such as latent feature Lasso [
Moreover, we defined a new 2 type of change point, i.e., “the third or fourth moment of factor loading changes”. Our experiment showed that our method can detect these change points. Our framework does not exert power in other tasks such as prediction and factor analysis. Meanwhile, in the context of non-parametric change point detection, it has a high expressive power.
The main contributions of this paper are as follows. • We propose YMN decomposition, which decompose one time-series data matrix into a product of a random matrix and a sparse matrix. • We propose a structural change point detection method using YMN decomposition. • We demonstrate the efectiveness of our structural change point detection techniques using experimental data and real data.
The remainder of the paper is organized as follows. In the next section, we present the related work. In Section 3, we clearly define the problems to solve. In Section 4, we propose the method. The method is evaluated in Section 5. We discuss the experimental results, issues, and future work in Section 6. Finally, we conclude the paper in Section 7. 2
This paper proposes a new structural change point detection
method using nonparametric matrix decomposition. In this
section, we review the previous research that is related to ours in
terms of (1) method and (2) purpose. We do not review the works
that are not directly related to ours. Therefore, we refer to the
survey by Truong et al. [
As mentioned in the introduction, change point detection can be divided into two types: (1) parametric and (2) nonparametric change point detection.
Because parametric change point detection places strong assumptions on the distribution of time series, it exhibits strong capability within the assumption of the model users, but any unexpected change point cannot be detected. Meanwhile, nonparametric change point detection methods place only a few assumptions on the time-series distribution of data. Therefore, 2This concept is not new. However, no research in econometrics has defined this type of change yet. the model is free and can present a robust result; however, their results often cannot be interpreted, and they can be less accurate than parametric methods in some situations, e.g., the observed time-series data completely follows one stochastic model.
Nonparametric change point detection methods are
primarily divided into two types. One type uses matrix decomposition
and the other uses kernel methods. The kernel methods [
Next, we will explain the structural change point detection
methods. In the parametric method, it is possible to assume a graph
structure or a time-series structure such as auto-regressive (AR)
and moving average [
Finally, we clarify our position. First, our method is an online change point detection method using nonparametric matrix decomposition. Our method can be considered a matrix decomposition method; meanwhile, it is close to the kernel method in that it assumes that the latent time-series follows some model. However, in the context of online change point detection, time-series are generated within a small window width; therefore, the randomly generated time-series variation is large, and our method can be considered as model-free. Meanwhile, our purpose is to detect the change point of the structure, and can be applied to all the structural changes defined above. It is also applicable to new types of changes such as changes in higher moments of the mixing matrix. Under such circumstances, our method can be regarded as a new nonparametric method to detect structural changes. 3
In this section, we mathematically and clearly explain the models that we will investigate, define the structural change that we want to detect and explain the change according to the real-world applications.Table 2 summarizes the notations used herein.
We begin from the generative model. We observe a vector yt ∈ RD at every time t . We assume that the vector yt is generated as a mixture of latent time series
yt = At zt , where At ∈ RD×K is a mixing matrix and zt ∈ RK is a latent time series. We can observe only yt and that both At and zt are latent.
As is often the case in an econometric setting zt is assumed to follow one stable deterministic or stochastic model. At is assumed to be piece-wise constant with respect to time and shows the structure behind data. Therefore, At may change abruptly because major events occurred and the relation between the latent and the observed changed. In this study, we denote t ∗ as the time of a structural change point if the following holds:
At = ( A(1) A(2) where A(1), A(2) ∈ RD×K are constants and A(1) , A(2). Meanwhile, latent random signal zt is assumed to follow a Gaussian distribution at any time, and it is independent and identically distributed (i.i.d.) with respect to time:
zt ∼ N (0, I K ). where I K is an identity matrix in RK ×K . Finally, the problem is to obtain the time of the structural change point t ∗, and the estimation of At is of no interest.
As for the type of changes that we will detect, we will follow
the literature of econometric and finance [
Change (1) is the simplest change. For example, the 1st-order moment change in the At means the abrupt increase and decrease of the values. The 2nd-order moment change in the At means some of the latent factors are increasingly or decreasingly correlated to the observed data. The 4th-order moment change in the At means the increase or decrease in the number of non-zero entries of At .
Change (2) is also under intense investigation in econometrics because a new connection between the latent and observed timeseries are recognized and the explanation capability of the old model decreased if the number of factors increased. Although this is contrary to the setting, “The dimension of latent data K is a constant,” we will address this type of change point similarly.
Change (3) appears not related to our models, but by substituting ⟨zt , yt −1, yt −2, · · · ⟩ for zt , we can also address the time-series models. This change is also important in many literature because the time-series becomes less predictable from the observed timeseries if the autocorrelation of the y decreased and vice versa. 4
In this section, we propose our structural change point
detection method. Our goal is to detect the change in the matrix At .
Although both coeficients At and factors zt are latent, the
theory of random matrix and statistics [
In this section, we describe the methodology and the theory of our method. First, we will explain the problem, and how and why that problem can be solved.
As described in the previous section, our goal is to detect the change in At . Most of the existing methods such as PCA, NMF, and ICA solve this problem by estimating the At and subsequently detect the change in the estimated At . However, we will directly calculate the change d(At , At −1) for an ideal distance of matrix d, and we are not interested in estimating At .
To calculate the change in structure d(At , At −1), our method decomposes the observed data yt into a sparse matrix Mt and a large random matrix Nt , and subsequently calculates the change in Mt . How our method operates can be explained by the following three basic ideas.
(1) If we generate many random vectors {Nt(i)}iQ=1, the linear
combination of {N t(i)}iQ=1 may be similar to the true latent
variables zt .
(2) If we perform a Lasso regression analysis, setting Nt
(random vectors) as explanatory variables and yt (observed
time-series) as explained variables, then random vectors
in Nt that are similar to zt may be automatically chosen
and used to explain yt .
(3) If we perform such a Lasso regression analysis and
obtain Mt as a sparse coeficient matrix (i.e., yt = Mt Nt ),
the change in Mt may be related with the change in At
(structural change = true coeficient matrix’s change).
We explain our basic ideas briefly but they are mathematically
formulated and confirmed by the existing random matrix theory
and statistical theory in this section. For idea (1), we can use
the random matrix theory. Suppose we generated K -dimensional
random vectors denoted by {Nt(i)}iQ=1 for Q times. As above, we
are considering the case where Q is much larger than K . For
example, in our experiments, we consider the case with Q =
100 max{D, K }. If the matrix ⟨Nt(1), · · · Nt(Q )⟩ is full rank (i.e.,
rank = K ), some of the {Nt(i)}iQ=1 are linearly independent and
we can obtain any vector in RK (including Zt ) by the linear
combination of {Nt(i)}iQ=1 . The situation where the matrix is full
rank can be interpreted in that any singular value of the matrix
is non-zero. Many studies regarding the singular value of the
random matrix have been conducted [
Proposition 4.1 (Theorem 1.3 [
Suppose that E[ξ ] = 0, E[ξ 2] = 1 and E[ξ C0 ] < ∞ for some suficiently large absolute constant C0. Subsequently, for all t > 0, we have
p(nσn (Mn (ξ ))2 ≤ t ) = 1 − e−t /2−√t + O(n−c ) where c > 0 is an absolute constant and implied constants in the O(.) The notation depends on E[ξ C0 ] but are uniform on t
This proposition can be used in any normalized square,
random matrix (i.e., each entry are i.i.d. random variables whose
mean and variance are 0 and 1, respectively). The stronger result
is obtained in the Gaussian case (Theorem 1.1 in [
Idea (2) is mathematically formulated as follows.
Proposition 4.2 (mathematical formulation of idea (2)). Let • zt 1, · · · , zt n ∈ R be i.i.d random variables. • a1, · · · an ∈ R be constants. • yt := a1zt 1 + · · · + anzt n for all t = 0, 1, · · · , T − 1 • wt 1, · · · , wtm ∈ R be i.i.d random variables • where each pairs zt i , wt j are independent. and we estimate the coeficients by Lasso, such that
yt = b1zt 1 + · · · + bnzt n + bn+1wt 1 + · · · + bn+mwtm holds. Then, as T → ∞.
• bi → ai for i = 1, · · · , n • bi → 0 for i = n + 1, · · · n + m
To prove this proposition, we use a seminal work by
Candes and Tao [
Definition 4.3 (Definition 1.1 [
(1 − δS )∥c ∥2 ≤ ∥FT c ∥2 ≤ (1 + δS )∥c ∥2 for all subset T ⊂ J of cardinality |T | ≤ S, and all real coeficients (cj )j ∈T . Similarly, we define the S, S ′-restricted orthogonality constants θS,S′ for S + S ′ ≤ | J | to be the smallest quantity such that
|⟨FT c, FT c ′⟩| ≤ θS,S′ · ∥c ∥ ∥c ′∥ holds for all disjoint sets T , T ′ ⊂ J of cardinality |T | ≤ S and |T ′| ≤ S ′.
The numbers δS and θS,S′ measure how close the vectors are to behaving as an orthonormal system. Subsequently, Proposition 4.2 can be proven as follows.
Proposition 4.4 (Theorem 1.1 [
β ′ = argminβ˜ ∈Rp ∥β˜∥L1 subject to ∥X ∗(y − X β˜)∥L∞ ≤ λp σ Then β ′ obeys
∥β ′ − β ∥L22 ≤ C12 · (2 log p) · S · σ 2 where C1 = 4/(1 − δS − θS,2S ) with large probability. 3
Idea (1) can be interpreted as, "we can generate the true latent time series zt ;" idea (2) can be interpreted as "we can obtain the true latent time series zt ". Therefore, by combining ideas (1) and (2), we will obtain idea (3), "we can generate and obtain the true latent time-series and the true latent mixing matrix."
Conjecture 4.5 (mathematical formulation of idea (3)). Let • yt = At zt • yt ∈ RD×T be an observed matrix, • zt ∈ RK ×T be a latent matrix, • At ∈ RD×K be a mixing matrix, • Nt ∈ RQ ×T be a large random matrix. • Mt ∈ RD×Q be the sparsest matrix such that ∥yt − Mt Nt ∥ ≤ (1 − θ )∥yt ∥ holds for a given hyperparameter θ .
Then, distances d1 and d2 exist in RD×K and RD×Q such that d1(At1 , At2 ) ≃ d2(Mt1 , Mt2 ) holds for all 0 < t1 < t2 < T
This conjecture suggests that we can approximate the change of mixing matrix d1(At1 , At2 ) by the change of the sparse matrix d2(Mt1 , Mt2 ) and that we don’t have to directly identify A in change point detection problems. In the remainder of this section, we show the matrix decomposition algorithm and the change point detection algorithm based on this conjecture. We do not know the properties of the distances d1andd2. However, we used the function d2(Mt1 , Mt2 ) := ∥Mt1 ∥L2 /∥Mt2 ∥L2 , which is not a distance but is robust under the permutations of the row vectors of M .
Algorithm 14 shows how our matrix decomposition using a
large random matrix is conducted. Our ultimate goal is to
decompose the observed data yt into a random matrix Nt and
sparse matrix Mt such that the change in the Mt is related to
the change in At . To obtain a sparse matrix Mt , we first
generate a large random matrix Nt ; subsequently, our method
minimizes the sparseness of the coeficient matrix within a constraint
∥Y −Mt Nt ∥ ≤ (1 −θ )∥Y ∥ where Y is the D ×T matrix whose row
vectors are yt . Algorithm 2 shows our change point detection
3 The term "with large probability" is used in the original paper [
Algorithm 1 Matrix decomposition using a large random matrix (YMN)
Y : D × T matrix that we want to decompose M: D × K sparse matrix N : K × T large random matrix Ni : 1 × T i-th row vector of N E[x ], V [x ]: the mean and variance of vector x ’s entities θ : threshold value of Lasso fitting score α : hyperparameter of Lasso, i.e., the coeficient of the L1 term δ : step value of α , used during hyperparameter optimization Lasso(X , T ; α ): matrix W that minimizes ||T − W X ||2 +α ||W ||1
N = ⟨N0, · · · , NK −1⟩ ∼ N (0, I ) for i = 0, · · · , K − 1 do
Ni ⇐ (Ni − E[Ni ])/pV [Ni ] end for M ⇐ Lasso(Y , N ; α ) while ∥Y − M N ∥ ≤ (1 − θ )∥Y ∥ do α ⇐ α + δ
M ⇐ Lasso(Y , N ; α ) end while algorithm. First, we use the series of window frames Yt for each time and perform the matrix decomposition of Yt . At this time, we have a series of matrix Mt . We calculate the change point score using the distance between Mt and Mt +1.
Algorithm 2 Change point detection algorithm using YMN decomposition
w: window size, t : current time yt : series vector, st : change point score ⟨, ⟩: concatenation of vectors into a matrix.
MatrixDecomp(Y ): Decompose Y into two matrices by YMN decomposition.
for t = 0, · · · , T − w − 1 do Yt ⇐ ⟨yt , yt +1, . . . , yt +w −1⟩ Nt Mt ⇐ MatrixDecomp(Yt ) st ⇐ d2(Mt , Mt +1) end for 5
To demonstrate that our methods can detect structural change points, we conducted two experiments. First, we conducted experiments in artificial settings where their structures and changes are clear. We demonstrate which type of structural change points can be detected and how these changes are detected clearly by these experiments.
Subsequently, we conducted experiments in real-world
settings where the structures and changes in structures are not clear.
We used economics [
In this experiment, we detected the following types of changes. (1) Mean of Factor Loadings’ Change
( A (t < t ∗), At =
A + W
yt +1 = αt yt + βt 1 + γt ϵt
To verify that our method can be used in the real world, we
conducted experiments with two famous datasets in economics [
5.2.1 US macroeconomic dataset. We analyzed the US representative macroeconomic dataset of 101 time series, collected monthly between 1959 and 2006 (T = 576), for the change points.
We listed 10 remarkable changes resulting from the
aforementioned of-line listing method with P = 30, Q = 10 in Figure 5.2.
Our change point detection methods clearly show the following
major change points in the US economy.
• the Great Moderation period that started in 1983
• major economic recession in early 1970s
• major economic recession in early 1980s
• Internet Bubble between 1999 and 2001
• the oil crisis at 1973
These change points are consistent with the existing research
on business cycles [
5.2.2 US 48 Industry Portfolios. We analyzed the US 48
industry portfolio collected daily between 1926 and 2018 (T = 24350)
for the change points [
We demonstrated that our method can detect all three types of structural changes defined in Section 3. This is because Conjecture 4.5 is true to some degree. That is, by Proposition 4.1, we can generate the same latent time-series by combining the random time-series; further, by Proposition 4.2, we can detect true latent time series by Lasso. Table 4 shows that this method is much more accurate than the existing matrix decomposition methods. This is because our method was initially created to detect the structural changes that we defined, but the existing methods cannot detect these changes.
Figure 5.1 shows the L2 norm of the Mt and we can see that the change of the original mixing matrix At and the change of the sparse matrix Mt are highly correlated. Hence this figure supports our Conjecture 4.5.
However, we could not detect the change (6). This is because the distance we used does not consider the permutation of the row. In other words, we consider only ∥Mt ∥L2 at each time t . Therefore, we cannot detect changes in swaps of elements of At . We expect that our methods can detect these changes by choosing some of the row vectors and by performing our decomposition repeatedly. From the facts above, it is clear that our method can be applied to the detection of structural changes in economics and ifnance. As mentioned in the Introduction, econometrics is an advanced research field in handling the change points; therefore, we think that this method can be applied to the detection of structural changes in many fields. For example, neuroscience and network analysis have similar objectives to ours because they cannot detect the exact model of the time-series, and structural changes are important to them. 4.0 Mt fo3.0 m r o n 2L2.0
We herein proposed a new nonparametric change point detection method of the structures of multidimensional time series. We 0 20 40 60 80
time (a) Experiment (1) Mean of At ’s Change 0 20 40 60 80
time (b) Experiment (2) Variance of At ’s Change 0 20 40 60 80
time (c) Experiment (3) Skew and Kurtosis of At ’s Change used a large random matrix to generate the latent time series, and Lasso to obtain good row vectors and to select the related row vectors. We also demonstrated that our method could detect not only typical structural changes used in econometrics and ifnance but also new types of structural changes such as the changes in the higher moment of the mixing matrix. With the random matrix theory and statistical theory of Lasso, we partly unveiled the mechanism and theory of our methods. However, a conjecture that fully supports our methods remains unproven. We demonstrated the efectiveness of our change point detection techniques by artificial data and real-world data in economics and ifnance. Similar structural changes may occur in many fields, but we have allocated comparison with the state-of-the-art methods and specialization in other fields as future work.
We would like to thank Tomoki Komatsu, Takeru Miyato, Tomohiro Hayase, Kosuke Nakago, and Hirono Okamoto for insightful comments and discussion.