On Multivariate Singular Spectrum Analysis: Tensor and Matrix Variants

We introduce and analyze two extensions of Singular Spectrum Analysis (SSA) to the multivariate setting: a new variant of the well-known matrix-based method (mSSA), and a novel tensor-based approach (tSSA). For mSSA, under a spatio-temporal factor model with N time series and T observations per series, we establish that prediction mean-squared-error for both imputation and out-of-sample forecasting effectively scales as 1 / \sqrt{\min(N, T )T}. This improves over: (i) 1 /\sqrt{T} error scaling of SSA, the univariate restriction of mSSA; (ii) 1/\min(N, T) error scaling for matrix estimation methods that ignore temporal structure. The out-of-sample forecasting result of mSSA could be of independent interest for online learning under a spatio-temporal factor model. For tSSA, we characterize its imputation mean-squared-error and showcase its better sample complexity, compared to mSSA, for certain regimes of N and T. We establish that our spatio-temporal model admits a broad range of time series dynamics including harmonics, polynomials, differentiable periodic functions, and Holder continuous functions. This is further illustrated via the {\em Hankel Calculus}, which establishes that the set of time series the model represents is closed under component-wise addition and multiplication. Empirically, on benchmark datasets, mSSA performs competitively with state-of-the-art neural-network time series methods (e.g. DeepAR, LSTM) and significantly outperforms classical methods such as vector autoregression (VAR). Consistent with our theory, tSSA achieves improved imputation performance over mSSA in certain regimes of N and T. Finally, we introduce and analyze an additional variant of SSA to estimate the time-varying variance of a time series. To our knowledge, this is the first result providing provable finite-sample performance guarantees for this task.