Minimal realization problem for Hidden Markov Models

In this paper, we study the problem of finding a minimal order (quasi-) Hidden Markov Model for a random process, which is the output process of an unknown stationary HMM of finite order. In the main theorem, we show that excluding a measure zero set in the parameter space of transition and observation probability matrices, both the minimal quasi-HMM realization and the minimal HMM realization can be efficiently constructed based on the joint probabilities of length N output strings, for N > max(4 log_d(k) + 1,3), where d is the size of the output alphabet size, and k is the minimal order of the realization. We also aim to connect the two lines of literature: realization theory of HMMs/automatas, and the recent development in learning latent variable models with tensor techniques.