Minimal Realization Problems for Hidden Markov Models
  Consider a stationary discrete random process with alphabet size d, which is
assumed to be the output process of an unknown stationary Hidden Markov Model
(HMM). Given the joint probabilities of finite length strings of the process,
we are interested in finding a finite state generative model to describe the
entire process. In particular, we focus on two classes of models: HMMs and
quasi-HMMs, which is a strictly larger class of models containing HMMs. In the
main theorem, we show that if the random process is generated by an HMM of
order less or equal than k, and whose transition and observation probability
matrix are in general position, namely almost everywhere on the parameter
space, both the minimal quasi-HMM realization and the minimal HMM realization
can be efficiently computed based on the joint probabilities of all the length
N strings, for N > 4 lceil log_d(k) rceil +1. In this paper, we also aim to
compare and connect the two lines of literature: realization theory of HMMs,
and the recent development in learning latent variable models with tensor
decomposition techniques.
