EM and ML Sequence Estimation

To minimize BER, we must find $\bf A$ to maximize $f({\bf A}\vert{\bf r})$. Using Bayes rule:

$$% latex2html id marker 1180 f({\bf A}\vert{\bf r}) = \frac {f... ...{\bf A})f({\bf A }) \doteq f({\bf r}\vert{\bf A})f({\bf A }) ,$$ (3)

where $K_{\ref{eq:f(A\vert r)}}$ is a constant which takes into account the effect of $f({\bf r})$ for normalizing the distribution.²

MAP estimators minimize BER by maximizing $f({\bf r}\vert{\bf A})f({\bf A })$. If $f({\bf A })$ is unknown or assumed to be uniform, then the ML estimator which maximizes the likelihood function $f({\bf r}\vert{\bf A})$ can be used instead. The EM algorithm derived in the next section produces an iterative solution to the ML problem of maximizing $f({\bf r}\vert{\bf A})$. But if $f({\bf A })$ is known and not uniform, then it could be incorporated into the EM algorithm as an additive term in the cost function, thus producing a MAP estimator.

The dependence of $f({\bf r}\vert{\bf A})$ on the random channel coefficients is:

$$f({\bf r}\vert{\bf A}) = E[f({\bf r}\vert{\bf H},{\bf A})] = ... ...\bf H}} f({\bf r}\vert{\bf H},{\bf A}) f({\bf H }) d{\bf H } ,$$ (4)

where $f({\bf r}\vert{\bf H},{\bf A})$ is given by (2). Evaluating this multidimensional integral and then maximizing the result with respect to $\bf A$ seems to be an intractable problem in general. Yet this is exactly the problem which EM algorithms can solve iteratively.

To maximize (4) using EM, define the auxiliary function [5]:

 

$$Q({\bf A}\vert{\bf B}) E [ \log (f({\bf r},{\bf H}\vert{\bf A})) \ \vert {\bf r},{\bf B} ]$$ =

$$\int_{\bf H} \log ( f({\bf r},{\bf H}\vert{\bf A}) ) f({\bf H }\vert{\bf r},{\bf B}) d {\bf H} ,$$ = (5)

where we desire the ML estimate of $\bf A$, and ${\bf B}$ represents the current estimate of $\bf A$. In the terminology of EM, ${\bf r}$ is the observed data, $\bf H$ is the hidden data, and $({\bf r},{\bf H})$ is the complete data.

The general EM algorithm for this problem is:

1.

Initialize ${\bf B}$ to an estimate of $\bf A$.

2.

E-step (Expectation): construct $Q({\bf A}\vert{\bf B})$

3.

M-step (Maximization): find $\bf A$ to maximize $Q({\bf A}\vert{\bf B})$

4.

Set ${\bf B}={\bf A}$ and repeat steps 2 and 3 until converged.

It can be shown [14,15] that $Q({\bf A}\vert{\bf B})$ from (5) may be written as:

$$Q({\bf A}\vert{\bf B}) \doteq \int_{\bf H} \log ( f({\bf r}\v... ...bf A}) ) f({\bf r}\vert{\bf H},{\bf B}) f({\bf H}) d {\bf H} .$$ (6)

In the specific case of the Gauss-Markov channel distribution, we will show that the E-step reduces to computing sufficient statistics of $Q({\bf A}\vert{\bf B})$, which are the mean and covariance of $\bf H$conditioned on ${\bf r}$ and ${\bf B}$. This enables the Viterbi algorithm [16] to be used for the M-step.