Time Series Analysis via Matrix Estimation

A. Agarwal, M. Amjad, D. Shah and D. Shen
We propose an algorithm to interpolate and forecast a time series by transforming the observed time series into a matrix, utilizing matrix estimation to recover missing values and de-noise observed entries, and performing linear regression to make pre- dictions. This algorithm is a consequence of a surprising and powerful link that we establish between (a single) time series data and matrix estimation. Subsequently, our algorithm is model agnostic with respect to the time dynamics and noise in the observations (similar to the recent matrix estimation literature). In particular, our method simultaneously provides meaningful imputation and prediction for a large class of models: finite sum of harmonics (which approximate stationary processes), non-stationary sublinear trends, Linear Time-Invariant (LTI) systems, and their additive mixtures. It is noteworthy that this simple linear forecaster coupled with matrix estimation comes with strong theoretical and experimental results. Due to the noise agnostic nature, our algorithm recovers the hidden state of sequential dynamics in settings where Expectation Maximization (EM) like approaches are often used, but have little or no theoretical guarantees. Through synthetic and real- world datasets, we demonstrate that our algorithm outperforms standard software packages (including R libraries) in the presence of missing data as well as high levels of noise. Moreover, when the packages – but not our algorithm – are given the underlying model, our algorithm still outperforms the standard packages.