Adaptive estimation of hidden nearly completely decomposable Markov chains with applications in blind equalization
Vikram Krishnamurthy · International Journal of Adaptive Control and Signal Processing · 1994
Abstract 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.