  We propose an algorithm to impute 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 predictions. At the core of our analysis is a representation result,
which states that for a large model class, the transformed time series matrix
is (approximately) low-rank. In effect, this generalizes the widely used
Singular Spectrum Analysis (SSA) in time series literature, and allows us to
establish a rigorous link between time series analysis and matrix estimation.
The key to establishing this link is constructing a Page matrix with
non-overlapping entries rather than a Hankel matrix as is commonly done in the
literature (e.g., SSA). This particular matrix structure allows us to provide
finite sample analysis for imputation and prediction, and prove the asymptotic
consistency of our method. Another salient feature of our algorithm is that it
is model agnostic with respect to both the underlying time dynamics and the
noise distribution in the observations. The noise agnostic property of our
approach allows us to recover the latent states when only given access to noisy
and partial observations a la a Hidden Markov Model; e.g., recovering the
time-varying parameter of a Poisson process without knowing that the underlying
process is Poisson. Furthermore, since our forecasting algorithm requires
regression with noisy features, our approach suggests a matrix estimation based
method - coupled with a novel, non-standard matrix estimation error metric - to
solve the error-in-variable regression problem, which could be of interest in
its own right. 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.
