Lumpable hidden Markov models - Model reduction and reduced complexity filtering

This paper is concerned with filtering of hidden Markov processes (HMPs) wh ich possess (or approximately possess) the property of lumpability. This pr operty is a generalization of the property of lumpability of a Markov chain which has been previously addressed by others. In essence, the property of lumpability means that there is a partition of the (atomic) states of the Markov chain into aggregated sets which act in a similar manner as far as t he state dynamics and observation statistics are concerned. We prove necess ary and sufficient conditions on the HMP for exact lumpability to hold. For a particular class of hidden Markov models (HMMs), namely finite output al phabet models, conditions for lumpability of all HMPs representable by a sp ecified HMM are given. The corresponding optimal filter algorithms for the aggregated states are then derived. The paper also describes an approach to efficient suboptimal filtering for HMPs which are approximately lumpable. By this we mean that the HMM generat ing the process may be approximated by a lumpable HMM. This approach involv es directly finding a lumped HMM which approximates the original HMM well, in a matrix norm sense. An alternative approach for model reduction based o n approximating a given HMM;I by an exactly lumpable HMM is also derived. T his method is based on the alternating convex projections algorithm. Some s imulation examples are presented which illustrate the performance of the su boptimal filtering algorithms.