Accelerating the EM Algorithm Without Much Fuss: Squared Extrapolation Methods (SQUAREM)

• Activity Number: 70
• Type: Contributed
• Date/Time: Sunday, August 7, 2005 : 4:00 PM to 5:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Ravi Varadhan*+ and Christophe Roland
• Companies: Johns Hopkins University and Université des Sciences et Technologies de Lille
• Keywords: EM algorithm ; convergence acceleration ; extrapolation methods ; Picard iteration

Abstract

We present a new class of iterative schemes, squared extrapolation methods (SQUAREM), for accelerating the convergence of the EM algorithm by exploiting the connection between fixed-point iterations and extrapolation methods (Roland and Varadhan 2004, Varadhan and Roland 2004). SQUAREM schemes, such as the EM, are linearly convergent, but with a faster rate of convergence. They are particularly effective when the dominant eigenvalue of the Jacobian of the fixed-point mapping is close to unity, in which case the EM exhibits sublinear or logarithmic convergence. They can be incorporated easily into an existing EM algorithm because they require only the basic EM step for their implementation. They do not require auxiliary quantities, such as the complete data log likelihood and its gradient or hessian. Therefore, they are broadly applicable and attractive in problems with a large number of parameters (e.g., image reconstruction and haplotype frequency estimation) and in complex modeling problems where each EM step is computationally demanding (e.g., statistical inference with nonignorable missingness). We demonstrate through examples the effectiveness of the SQUAREM schemes.