The One-Step-Late PXEM Algorithm
Submitted to Statistics and Computing
Ruoxi Tang and David A. van Dyk
Department of Statistics, Harvard University, Cambridge, MA
02138, U.S.A.
The EM algorithm is a popular method for computing maximum likelihood
estimates or posterior modes in models that can be formulated in terms
of missing data or latent structure. Although easy implementation and
stable convergence add to the popularity of the algorithm, its
sometimes notoriously slow convergence can be a nuisance and in some
cases is severe enough to leave the algorithm untenable. In recent
years, however, various adaptations of the EM algorithm have
significantly improved its speed of convergence while maintaining its
stability and simplicity. One especially successful method for
maximum likelihood is known as the parameter expanded EM or PXEM
algorithm (Liu, Rubin, Wu, 1998). PXEM is based on the method of
working parameters (Meng, van Dyk, 1997), and has significantly
improved the rate of convergence of EM for a number of important
models. Unfortunately, PXEM does not generally have a closed form
M-step when computing posterior modes, even when the corresponding EM
algorithm is in closed form. In this paper we confront this problem
by adapting the one-step-late EM algorithm (Green, 1990) to PXEM to
establish a fast closed form algorithm that improves on the
one-step-late EM algorithm by insuring {\it monotone} convergence. We
illustrate these algorithms in a simple probit regression model and a
variety of dynamic linear models with multivariate time-invariant
system equations. We go into some detail in the case of dynamic linear
models, describing algorithms that can handle polynomial growth and
trends, seasonal components, seasonal factors, harmonic analysis, and
regression components. The various algorithms are used
in several examples showing computational savings of as much as
99.9%, with the biggest savings occurring when the EM algorithm is
the slowest to converge.
Return to David van Dyk's homepage.