The Reducibility of Reachable Space for Structured Hidden Markov Models

The order of a hidden Markov model (HMM) is an index of the complexity and is closely related to the reachable subspace in the state of the model. When the reachable subspace is not the whole space, there exists a reduced-order quasi hidden Markov model (quasi-HMM), which may not satisfy the nonnegative constraints, equivalent to the original HMM. Such an HMM will be called reachable-space reducible. In this paper, we explore a necessary and sufficient condition for the reachable-space reducible HMM. The condition indicates that if the transition matrix and the observation matrix jointly have a certain structured non-zero pattern, then the HMM is reachable-space reducible. We show that the connection graph of the HMM characterizes the condition. Subsequently, we prove that the HMM satisfying this particular structure always has a reduced-order HMM realization satisfying the nonnegative constraints. Some examples are given to demonstrate our results.