02 MSSA

MSSA. Background.

Construction of Trajectory Matrix

The first step in the MSSA is the same as for the SSA. One starts with the construction of the trajectory matrix. Although the construction procedure is quite similar, one should be aware of the size of the trajectory matrix. Let $s$ denote the number of the given time series, $N$ the length of each of $s$ time series, $L$ - window size and $2 \leq L \leq N/2$ and $L \in N$, $K=N-L+1$ The trajectory matrix for the MSSA results in a $L \times Ks$ matrix $X$. We simply stack the trajectory matrices $X^i$ for each of $s$ time series. The columns of the trajectory matrix $X^i$ for $i$-th time series comprise lagged versions of $i$ time series just like in SSA.

The $X^i$ matrices can stacked in a vertical or horizontal direction, however due to performance reasons for SVD, horizontal direction is often preferred.

Thus, each matrix $X^i$ for $i=0,1,2,...,s$ can be represented as follows:

$$X^i = \begin{bmatrix} f^i_0 & f^i_1 &f^i_2 & f^i_3 &\dots & f^i_{N-L}\\\\ f^i_1 & f^i_2 &f^i_3 & f^i_4 &\dots & f^i_{N-L+1}\\\\ f^i_2 & f^i_3 &f^i_4 & f^i_5 &\dots & f^i_{N-L+2}\\\\ \vdots & \vdots &\vdots & \vdots &\vdots & \vdots\\\\ f^i_{L-1}& f_{L} &f^i_{L+1} & f^i_{L+2} &\dots & f^i_{N-1} \end{bmatrix}$$

It is clear that the elements of the anti-diagonals are equal. This a Hankel matrix.

Finally, we obtain the resulting trajectory matrix $X$ as

$$X = \begin{bmatrix} X^0 & X^1 & X^2 & ... & X^s \end{bmatrix}$$

Decomposition of the Trajectory Matrix X

The second step is to decompose $X$. There exist several options, we focus on the SVD decomposition and the Eigendecomposition.

1. SVD Decomposition

This option is used primarly when the time series is not too long, because SVD is computationally intensive algorithm. It becomes critical especially for the MSSA, where the trajectory matrix becomes extremly high-dimensional, because of stacking of trajectory matrices for each time series. The formula for SVD is defined as follows:

$$X=U \Sigma V^T$$

where:

• $U$ is an $L \times L$ unitary matrix containing the orthonormal set of left singular vectors of $X$ as columns
• $\Sigma$ is an $L \times K$ rectangular diagonal matrix containing singular values of $X$ in the descending order
• $V^T$ is a $Ks \times Ks$ unitary matrix containing the orthonormal set of right singular vectors of $X$ as columns.

The SVD of the trajectory matrix can be also formulated as follows:

$$X = \sum^{d-1}_{i=0}\sigma_iU_iV_i^T = \sum^{d-1}_{i=0}{X_i}$$

where:

• ${\sigma_i,U_i,V_i}$ it the $i^{th}$ eigentriple of the SVD

• $\sigma_i$ is the $i^{th}$ singular value, is a scaling factor that determines the relative importance of the eigentriple

• $U_i$ is a vector representing the $i^{th}$ column of $U$, which spans the column space of $X$

• $V^j_i$ is a vector representing the $i^{th}$ column of $V$, which spans the row space of $X$. There are $Ks$ such vectors for MSSA. Every set of consequtive $K$ vectors $V^j_i$ corresponds to the time series $j$, where $j = 0,..s$

• $d$, such that $d \leq L$, is a rank of the trajectory matrix $X$. It can be regarded as the instrinsic dimensionality of the time series' trajectory space

• $X_i=\sigma_iU_iV_i^T$ is the $i^{th}$ elementary matrix

Note, that the difference arises in the dimensionality of the elementary matrices. While for the SSA we obtain an elementary matrix $X_i$ of the size $L \times K$, for the MSSA we get an elementary matrix $X_i$ of the size $L \times Ks $!

2. Randomized SVD

   This techinque is used for the approximation of the classic SVD and primarly used for SSA with large $N$ and in the case of MSSA where $X$ is high-dimensional because of stacking of trajectory matrices of each considered time series. The main purpose of this technique is to reduce the dimensionality of $U$ and $V$.

Eigentriple Grouping and Elementary Matrix Separation

On this step we perform an eigentriple grouping to decompose time series into several components. We make use of one or several techniques listed below:

1. Visual Inspection of Elementary Matrices for Patterns

   Matrices without patterns are referred as the trend component, while seasonal and noise components are associated with repeating patterns. The most frequent alterations of the pattern are indicators of the noise component.Note, that in the MSSA case it might be quite inconvenient due to the dimensionality of elementary matrices.

2. Eigenvalue Contribution and Shape of Eigenvectors $U$

   This combines considering the shape of eigenvectors $U$ and relative contribution of eigenvalues. The most important $\sigma_i$-s are associated with the ternd component. The related eignevectors demonstrate absence of periodicity and clear trend, while seasonal and noice components have a great deal lesser contribution and periodicity.

3. Weighted Correlation between Components

   This approach is frequently used for the automatic eigentriple grouping. It is obviuous, that the most correlated components $X_i$ have more in common than decorrelated or negatively correlated ones.

Time Series Reconstruction

Forecasting