The EM Algorithm - An Old Folk Song Sung To A Fast New Tune
Xiao-Li Meng
Department of Statistics, The University of Chicago,
Chicago, IL 60637, U.S.A.
David A. van Dyk
Department of Statistics, Harvard University, Cambridge, MA
02138, U.S.A.
Celebrating the 20th anniversary of the publication of Dempster,
Laird, and Rubin (1977) which popularized the EM
algorithm, we investigate, after a brief historical
account, strategies that aim to make EM converge much faster
while maintaining its simplicity and stability (e.g.,
automatic monotone convergence in likelihood).
First, we introduce the idea of a ``working parameter"
to facilitate the search of efficient data-augmentation
schemes and thus, fast EM implementations. Second, summarizing various recent
extensions of EM, we formulate a general Alternating
Expectation/Conditional Maximization (AECM)
algorithm that couples flexible data-augmentation schemes with
model-reduction schemes to achieve efficient computations.
We illustrate these methods using
multivariate t-models with known or unknown degrees of freedom and
Poisson models for image reconstruction; a third application involving
random-effects models is presented in an accompanying paper.
We show, through both empirical and theoretical evidence, the potential
for a dramatic reduction in computational time with little increase in
human effort.
We also discuss the intrinsic connection between EM-type algorithms and
the Gibbs sampler, and the possibility of using the techniques presented
here to speed up the latter. The main conclusion of the paper is that, with
the help of statistical considerations, it is
possible to construct algorithms that are simple, stable, and
fast.
Keywords: DATA AUGMENTATION; ECM ALGORITHM; ECME
ALGORITHM; GIBBS SAMPLER; INCOMPLETE DATA; MARKOV-CHAIN MONTE CARLO;
MISSING DATA; MODEL REDUCTION; MULTIVARIATE t-DISTRIBUTIONS;
POISSON MODEL; POSITRON EMISSION TOMOGRAPHY;\break RATE OF CONVERGENCE; SAGE
ALGORITHM.
Return to David van Dyk's homepage.