The EM Algorithm—an Old Folk-song Sung to a Fast New Tune

TLDR

The EM algorithm, introduced by Dempster, Laird, and Rubin, has become a cornerstone of statistical inference, and this paper reviews 20 years of work aimed at accelerating its convergence while preserving simplicity and stability. The authors seek to design fast EM implementations by introducing a working parameter, formulating a general alternating expectation–conditional maximization (AECM) algorithm, and exploring connections to the Gibbs sampler. They illustrate the AECM framework on multivariate t‑models and Poisson image‑reconstruction models, demonstrating how flexible data augmentation and model‑reduction schemes enable efficient computation. Empirical and theoretical results show that these strategies can dramatically reduce computational time with minimal extra effort, yielding algorithms that are simple, stable, and fast.

Abstract

Summary Celebrating the 20th anniversary of the presentation of the paper by Dempster, Laird and Rubin which popularized the EM algorithm, we investigate, after a brief historical account, strategies that aim to make the EM algorithm converge 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 for efficient data augmentation schemes and thus fast EM implementations. Second, summarizing various recent extensions of the EM algorithm, we formulate a general alternating expectation–conditional maximization algorithm AECM 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. 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.