Conjugate Gradient Acceleration of the EM Algorithm

Abstract

The EM algorithm is a very popular and widely applicable algorithm for the computation of maximum likelihood estimates. Although its implementation is generally simple, the EM algorithm often exhibits slow convergence and is costly in some areas of application. Past attempts to accelerate the EM algorithm have most commonly been based on some form of Aitken acceleration. Here we propose an alternative method based on conjugate gradients. The key, as we show, is that the EM step can be viewed (approximately at least) as a generalized gradient, making it natural to apply generalized conjugate gradient methods in an attempt to accelerate the EM algorithm. The proposed method is relatively simple to implement and can handle Problems with a large number of parameters, an important feature of most EM algorithms. To demonstrate the effectiveness of the proposed acceleration method, we consider its application to several Problems in each of the following areas: estimation of a covariance matrix from incomplete multivariate normal data, confirmatory factor analysis, and repeated measures analysis. The examples in these areas demonstrate promise for the new acceleration method. In terms of Operation counts, for all of the examples considered the accelerated EM algorithm increases the speed of the EM algorithm, in some cases by a factor of 10 or more. In the context of repeated measures analysis, we give a new EM algorithm that, compared to earlier algorithms, can have a considerably smaller cost per iteration. We have not, however, attempted to evaluate the performance of this latter algorithm here.

KEY WORDS:

• Factor analysis
• Incomplete data
• Repeated measures