Lumpable hidden Markov models-model reduction and reduced complexity filtering

This paper is concerned with filtering of hidden Markov processes (HMP) which possess (or approximately possess) the property of lumpability. This property is a generalization of the property of lumpability of a Markov chain which has been previously addressed by others. In essence, the property of...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on automatic control 2000-12, Vol.45 (12), p.2297-2306
Main Authors: White, L.B., Mahony, R., Brushe, G.D.
Format: Article
Language:English
Subjects:
Algorithms
Alphabets
Approximation
Brushes
Filtering
Filtering algorithms
Filters
Filtration
Frequency estimation
Hidden Markov models
Markov analysis
Markov chains
Markov processes
Mathematical models
Modeling
Performance analysis
Reduced order systems
Statistics
Studies
Sufficient conditions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper is concerned with filtering of hidden Markov processes (HMP) which possess (or approximately possess) the property of lumpability. This property 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 the state dynamics and observation statistics are concerned. We prove necessary and sufficient conditions on the HMP for exact lumpability to hold. For a particular class of hidden Markov models (HMM), namely finite output alphabet models, conditions for lumpability of all HMP representable by a specified 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 HMP which are approximately lumpable. By this we mean that the HMM generating the process may be approximated by a lumpable HMM. This approach involves directly finding a lumped HMM which approximates the original HMM well, in a matrix norm sense. An alternative approach for model reduction based on approximating a given HMM by an exactly lumpable HMM is also derived. This method is based on the alternating convex projections algorithm. Some simulation examples are presented which illustrate the performance of the suboptimal filtering algorithms.
ISSN:0018-9286
1558-2523
DOI:10.1109/9.895565