On the Orderings and Groupings of Conditional Maximizations
Within ECM-Type Algorithms
David A. van Dyk
Department of Statistics, Harvard University, Cambridge, MA
02138, U.S.A.
Xiao-Li Meng
Department of Statistics, The University of Chicago,
Chicago, IL 60637, U.S.A.
The ECM (Meng and Rubin, 1993) and ECME (Liu and Rubin, 1994) algorithms
are generalizations of the EM
algorithm in which the maximization (M) step is replaced by
several conditional
maximization (CM) steps. The order that the CM-steps are performed
is trivial to change and generally affects how fast the algorithm
converges.
Moreover, the same order of CM-steps need not be used at each
iteration and in some applications it is feasible to group two or
more CM-steps into one larger CM-step. These issues also arise
when implementing the Gibbs sampler and in
this paper we study them
in the context of fitting log-linear and random-effects models with
ECM-type algorithms.
We find that some standard theoretical measures of the
rate of convergence can be of little use
in comparing the computational time required, and that common
strategies such as using a random ordering
may not provide the desired effects.
We also develop two new algorithms for fitting random-effects models to
illustrate that with careful selection of CM-steps ECM-type
algorithms can be substantially faster than the standard EM algorithm.
Key Words: Contingency Table,
Convergence Rate; Data Augmentation;
Gibbs Sampler; EM Algorithm; Incomplete Data;
IPF; Missing Data; Model Reduction; Random-Effects Models
Return to David van Dyk's homepage.