  In this paper, we focus on learning a linear time-invariant (LTI) model with
low-dimensional latent variables but high-dimensional observations. We provide
an algorithm that recovers the high-dimensional features, i.e. column space of
the observer, embeds the data into low dimensions and learns the
low-dimensional model parameters. Our algorithm enjoys a sample complexity
guarantee of order $\tilde{\mathcal{O}}(n/\epsilon^2)$, where $n$ is the
observation dimension. We further establish a fundamental lower bound
indicating this complexity bound is optimal up to logarithmic factors and
dimension-independent constants. We show that this inevitable linear factor of
$n$ is due to the learning error of the observer's column space in the presence
of high-dimensional noises. Extending our results, we consider a meta-learning
problem inspired by various real-world applications, where the observer column
space can be collectively learned from datasets of multiple LTI systems. An
end-to-end algorithm is then proposed, facilitating learning LTI systems from a
meta-dataset which breaks the sample complexity lower bound in certain
scenarios.
