Simple and Globally Convergent Methods for Accelerating the Convergence of Any EM Algorithm

Abstract

Abstract. The expectation‐maximization (EM) algorithm is a popular approach for obtaining maximum likelihood estimates in incomplete data problems because of its simplicity and stability (e.g. monotonic increase of likelihood). However, in many applications the stability of EM is attained at the expense of slow, linear convergence. We have developed a new class of iterative schemes, called squared iterative methods (SQUAREM), to accelerate EM, without compromising on simplicity and stability. SQUAREM generally achieves superlinear convergence in problems with a large fraction of missing information. Globally convergent schemes are easily obtained by viewing SQUAREM as a continuation of EM. SQUAREM is especially attractive in high‐dimensional problems, and in problems where model‐specific analytic insights are not available. SQUAREM can be readily implemented as an ‘off‐the‐shelf’ accelerator of any EM‐type algorithm, as it only requires the EM parameter updating. We present four examples to demonstrate the effectiveness of SQUAREM. A general‐purpose implementation (written in R) is available.

Keywords

Affiliated Institutions

• Johns Hopkins University US
• Laboratoire Paul Painlevé FR

Related Publications