Performance analysis of Hidden Markov Model based tracking algorithms

© 1997 Dr. Moses Sanjeev ArulampalamThis thesis investigates the performance of Hidden Markov Model (HMM) based tracking algorithms. The algorithms considered have applications in frequency line tracking and target position tracking. The performance of these algorithms are investigated by a combination of theoretical and simulation based approaches. The theoretical based approach focuses on deriving upper bounds on probabilities of error paths in the output of the tracker. Upper bounds on specific error paths, conditioned on typical true paths are derived for a HMM based frequency line tracker that uses continuous valued observation vectors. These bounds are derived by enumerating possible estimated state sequences, and using necessary conditions on the Viterbi scores of these sequences. The derived upper bounds are found to compare well with simulation results. Next, upper bounds on average error event probabilities (averaged over all possible true paths) are derived for the same HMM based frequency tracker. Here, 'error event' refers to a brief divergence of the estimated track from the true path. Numerical computation of the derived upper bounds are shown to compare well with simulation results. Using these bounds a theorem is established which states that optimum tracking, corresponding to minimum error probability, is achieved when model transition probabilities are matched to 'true' transition probabilities of the underlying signal. Other interesting features of this algorithm are analysed, including robustness of the algorithm to variations in model transition probabilities, and characterisation of the benefits of using HMM based tracking as opposed to a simple approach based on isolated Maximum Liklihood estimators. The theoretical analysis is extended to two other HMM based frequency line trackers that use discrete valued observation vectors. A comparative study of the three HMM based frequency line trackers is carried out to arrive at conditions for the superiority of one algorithm over another. The simulation based approach to analysing performance consists of a combination of Monte-Carlo (MC) and Importance Sampling (IS) simulations. MC simulations are carried out at moderate SNR where required computation time for estimating performance measures is feasible. At high SNR, the error probabilities are small and the required computation time becomes infeasible. To overcome this, importance sampling schemes are designed which reduce the computation time by orders of magnitude. Importance sampling is a modified Monte-Carlo method which is useful in the simulation of rare probabilities. The basic principle is to use a different simulation density to increase the relative frequency of "important" events and then weight the observed data in order to obtain an unbiased estimate of the parameter of interest. In this thesis, a systematic procedure based on minimizing an upper bound to the IS estimator variance is used in the simulation density design. High efficiency gains, of order 1013 are demonstrated with the proposed scheme