Time Series Analysis via Matrix Estimation

We consider the task of interpolating and forecasting a time series in the presence of noise and missing data. As the main contribution of this work, we introduce an algorithm that transforms the observed time series into a matrix, utilizes singular value thresholding to simultaneously recover missing values and de-noise observed entries, and performs linear regression to make predictions. We argue that this method provides meaningful imputation and forecasting 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. In general, our algorithm recovers the hidden state of dynamics based on its noisy observations, like that of a Hidden Markov Model (HMM), provided the dynamics obey the above stated models. We demonstrate on synthetic and real-world datasets that our algorithm outperforms standard software packages not only in the presence of significantly missing data with high levels of noise, but also when the packages are given the underlying model while our algorithm remains oblivious. This is in line with the finite sample analysis for these model classes.

Joint work with Muhammad Jehangir, Devavrat Shah, Dennis Shen