Engineering Enhancements for the EM Algorithm

Our initialization strategy gives $\vert\mathcal{U}\vert = \alpha \vert\mathcal{T}\vert$, where $\alpha$ is a free parameter and $0 < \alpha \le 1$. Too small an $\alpha$ reduces the ability of the nonparametric PDF to well approximate the uncorrupted-signal Markov PDF. Too large an $\alpha$ increases the number of parameters to be estimated--equal to $\vert\mathcal{U}\vert$--thereby increasing the chance of the EM algorithm getting stuck on local maxima. A large $\alpha$ also increases the space requirements of the algorithm: $O (\vert\mathcal{U}\vert \vert\mathcal{T}\vert)$. We have found that, in practice, the algorithm is not very sensitive to the specific choice of $\alpha$ and a choice of $\alpha = 0.33$ works well in practice.

To further reduce the computational and space requirements of the algorithm, we can replace the set $\mathcal{T}$ itself by a uniformly-distributed random sample of observations $\mathcal{T}^\dagger$, with $\vert\mathcal{T}^\dagger\vert = \beta \vert\mathcal{T}\vert, 0 < \beta \le 1$, and subsequently choose $U$ as a random sample from $\mathcal{T}^\dagger$, with $\vert\mathcal{U}\vert = \alpha \vert\mathcal{T}^\dagger\vert$. This makes the computational and space complexity of the EM algorithm both to be $O (\alpha \beta^2 \vert\mathcal{T}\vert^2)$. The results in this paper use $\alpha = 0.33$ and $\beta = 0.66$.