The world’s leading publication for data science, AI, and ML professionals.

Reduced-Rank Vector Autoregressive Model for High-Dimensional Time Series Forecasting

Introduction

Nowadays, with the remarkable development of data collection/availability techniques, we have more opportunities to approach many kinds of time series data in a lot of scientific and industrial fields. There are many types of time series data, including univariate time series, multivariate time series, and multidimensional time series. For multivariate time series, the data has more than one time-dependent variable, and each variable has dependencies on other variables. Therefore, vector autoregressive (VAR) model is a classical approach for multivariate time series analysis mainly due to its ability for identifying co-evolution patterns of the time-dependent variables.

However, there is a special case that if we have a large amount of variables (e.g., thousands or millions of variables) but only have a limited number of time steps, then the multivariate time series would be high-dimensional. For instance, Figure 1 shows an intuitive illustration of the VAR model for high-dimensional time series data. Here, the high-dimensional time series data are represented as "tall-skinny" matrices.

Figure 1. Illustration of the VAR model with high-dimensional multivariate time series {x1, x2, x3, x4}. The model is parameterized by the coefficient matrix A (i.e., a square matrix).
Figure 1. Illustration of the VAR model with high-dimensional multivariate time series {x1, x2, x3, x4}. The model is parameterized by the coefficient matrix A (i.e., a square matrix).

In this simple illustration, it is not difficult to see that there are many parameters in the coefficient matrix, exceeding the number of time series observations. In most cases, this VAR model is ill-posed because it would suffer from the over-parameterization issue. To address this issue in VAR, one important direction is developing the reduced-rank VAR model parameterized by matrix factorization.

In this blog post, we introduce a reduced-rank VAR model for multivariate time series analysis. The model is proposed by Velu, Reinsel, and Wichern in 1986 [1]. Before this art, Velu also discussed the estimation of certain reduced-rank autoregressive models in his unpublished PhD thesis at University of Wisconsin. Later in 1998, Velu and Reinsel published the book "Multivariate Reduced-Rank Regression: Theory and Applications" [2].

Although the reduced-rank VAR has a long history, the paper did not attract a lot of attention in the past few decades. As we have many kinds of high-dimensional time series data, many high-dimensional VAR models actually hold a similar idea as reduced-rank VAR.

This post is not limited to the content of the most previous reduced-rank VAR paper. We also provide a simple model description of the reduced-rank VAR model and give a toy example to illustrate its applications. In addition, we reproduce the model in Python, particularly with the Numpy package.

Model Description

Figure 1 shows the basic idea of VAR. Given a time series data X of size N-by-T where N is the number of variables and T is the number of time steps, then in any time step t, the first-order VAR, or VAR(1), takes the form of

where xt denotes the snapshot vector in time t and the size is N-by-1. A is the coefficient matrix, and it is of size N-by-N.

To address the over-parameterization issue in VAR, we can assume that the coefficient matrix A has a reduced rank, and define two matrices W (of size N-by-R) and V (of size R-by-N) such that

A=WV

where the coefficient matrix is reparameterized by a matrix factorization. In this case, it leads to a reduced-rank VAR model as shown in Figure 2. It is obvious that if we impose a suitable reduced rank R, parameters in the component matrices W and V would be less than the parameters in the coefficient matrix A. This in fact provides a technical path for addressing the over-parameterization issue of VAR in the high-dimensional time series data.

Figure 2. Illustration of the reduced-rank VAR model parameterized by the component matrices W and V. Here, W is a tall-skinny matrix, while V is a short-fat matrix.
Figure 2. Illustration of the reduced-rank VAR model parameterized by the component matrices W and V. Here, W is a tall-skinny matrix, while V is a short-fat matrix.

From a Machine Learning perspective, to estimate the parameters in the reduced-rank VAR model, we can formulate the autoregression errors as a L2-norm loss function:

For this optimization problem, we can obtain the closed-form solutions to W and V in the form of vector. However, the vector form is not the best choice for developing an algorithm. Here, we take into account a new optimization problem:

where we define

and the closed-form solutions to W and V are now given by

Algorithm

Since the closed-form solution to W involves V, and the closed-form solution to V involves W, we can use an Alternating Minimization scheme. For the least squares solutions, the algorithm is actually Alternating Least Squares (ALS). There are only three main steps of this iterative algorithm:

  • Initialize W and V with random values.
  • Iterative step 1: Update W by the least squares solution as mentioned above.
  • Iterative step 2: Update V by the least squares solution as mentioned above.

We can define a function for the reduced-rank VAR model in Python.

import numpy as np
def rrvar(data, R, pred_step, maxiter = 100):
    """Reduced-rank VAR algorithm."""

    N, T = data.shape
    X1 = data[:, : -1]
    X2 = data[:, 1 :]
    V = np.random.randn(R, N)
    for it in range(maxiter):
        W = X2 @ np.linalg.pinv(V @ X1)
        V = np.linalg.pinv(W) @ X2 @ np.linalg.pinv(X1)
    mat = np.append(data, np.zeros((N, pred_step)), axis = 1)
    for s in range(pred_step):
        mat[:, T + s] = W @ V @ mat[:, T + s - 1]
    return mat[:, - pred_step :]

This is a reduced-rank VAR algorithm where we have inputs like multivariate time series data and reduced rank.

Toy Example

We evaluate the algorithm by considering the following example:

The example data is of size 20-by-10, and this is a "tall-skinny" data. We will try to set the reduced rank as 2 and test the algorithm.

Write the code in Python:

X = np.zeros((20, 10))
for i in range(20):
    X[i, :] = np.arange(i + 1, i + 11)
pred_step = 2
R = 2
mat_hat = rrvar(X, R, pred_step)
print(mat_hat)

The results are:

[[11. 12.]
 [12. 13.]
 [13. 14.]
 [14. 15.]
 [15. 16.]
 [16. 17.]
 [17. 18.]
 [18. 19.]
 [19. 20.]
 [20. 21.]
 [21. 22.]
 [22. 23.]
 [23. 24.]
 [24. 25.]
 [25. 26.]
 [26. 27.]
 [27. 28.]
 [28. 29.]
 [29. 30.]
 [30. 31.]]

The results are completely same as the ground truth data.

Conclusion

Reduced-rank VAR is an important time series forecasting approach in the case of high-dimensional data. It have many advantages like compressing the coefficients and solving the over-parameterization issue in VAR. Despite the Matrix Factorization tool in the reduced-rank VAR, there are also some other tools like tensor factorization. Relying on this post, it is not hard to extend the reduced-rank VAR model with a higher order.

References

[1] Velu, R. P., Reinsel, G. C., & Wichern, D. W. (1986). Reduced rank models for multiple time series. Biometrika, 73(1), 105–118.

[2] Velu, R., & Reinsel, G. C. (1998). Multivariate reduced-rank regression: theory and applications. Springer Science & Business Media.

[3] Xinyu Chen (2021). Matrix Autoregressive Model for Multidimensional Time Series Forecasting. Medium. Website: https://towardsdatascience.com/matrix-autoregressive-model-for-multidimensional-time-series-forecasting-6a4d7dce5143


Related Articles