Premium
Adaptive estimation of hidden nearly completely decomposable Markov chains with applications in blind equalization
Author(s) -
Krishnamurthy Vikram
Publication year - 1994
Publication title -
international journal of adaptive control and signal processing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.73
H-Index - 66
eISSN - 1099-1115
pISSN - 0890-6327
DOI - 10.1002/acs.4480080303
Subject(s) - hidden markov model , markov chain , computational complexity theory , algorithm , markov model , computer science , expectation–maximization algorithm , variable order markov model , markov process , mathematics , estimation theory , mathematical optimization , artificial intelligence , statistics , maximum likelihood
This paper proposes maximum likelihood (ML) estimation schemes for nearly completely decomposable Markov chains (NCDMCs) in white Gaussian Noise. Aggregation techniques based on stochastic complementation are applied to significantly reduce the dimension of the resulting hidden Markov model (HMM) and hence substantially reduce the computational requirements of the estimation algorithms. Stochastic complementation results in exact aggregation in that no approximations are involved in the steady state probability distribution of the Markov chain. We then present an off‐line estimation algorithm for the parameters and states of the HMM based on the estimation of the aggregated HMM. This off‐line algorithm is an ML estimation scheme and is based on the expectation maximization (EM) algorithm. It has a significantly reduced computational complexity compared with the standard (full‐order) EM‐based HMM estimation scheme. Finally we present an application of our techniques. We show that hidden NCDMCs can be used to formulate the blind equalization problem for noisy FIR channels with Markov inputs, e.g. phase‐shiftkeyed (PSK) signals. We then propose recursive EM and gradient estimation techniques for the aggregated HMM resulting in on‐line estimates of the channel coefficients and signal estimate. For an N a ‐state Markov chain our aggregate‐based estimation scheme has a computational complexity O ( N −2 a ), whereas standard algorithms have a complexity O ( N a − L + 1 ) at each time instant, where L is the length of the FIR channel.