Asymptotic Convergence Rate of the EM Algorithm for Gaussian Mixtures
- 1 December 2000
- journal article
- Published by MIT Press in Neural Computation
- Vol. 12 (12) , 2881-2907
- https://doi.org/10.1162/089976600300014764
Abstract
It is well known that the convergence rate of the expectation-maximization (EM) algorithm can be faster than those of convention first-order iterative algorithms when the overlap in the given mixture is small. But this argument has not been mathematically proved yet. This article studies this problem asymptotically in the setting of gaussian mixtures under the theoretical framework of Xu and Jordan (1996). It has been proved that the asymptotic convergence rate of the EM algorithm for gaussian mixtures locally around the true solution Θ* is o(e0.5−ε(Θ*)), where ε > 0 is an arbitrarily small number, o(x) means that it is a higher-order infinitesimal as x → 0, and e(Θ*) is a measure of the average overlap of gaussians in the mixture. In other words, the large sample local convergence rate for the EM algorithm tends to be asymptotically superlinear when e(Θ*) tends to zero.Keywords
This publication has 12 references indexed in Scilit:
- Fast EM-type Implementations for Mixed Effects ModelsJournal of the Royal Statistical Society Series B: Statistical Methodology, 1998
- The EM Algorithm—an Old Folk-song Sung to a Fast New TuneJournal of the Royal Statistical Society Series B: Statistical Methodology, 1997
- Acceleration of the EM Algorithm by using Quasi-Newton MethodsJournal of the Royal Statistical Society Series B: Statistical Methodology, 1997
- Convergence results for the EM approach to mixtures of experts architecturesNeural Networks, 1995
- The ECME algorithm: A simple extension of EM and ECM with faster monotone convergenceBiometrika, 1994
- On the Rate of Convergence of the ECM AlgorithmThe Annals of Statistics, 1994
- Hierarchical Mixtures of Experts and the EM AlgorithmNeural Computation, 1994
- A tutorial on hidden Markov models and selected applications in speech recognitionProceedings of the IEEE, 1989
- Mixture Densities, Maximum Likelihood and the EM AlgorithmSIAM Review, 1984
- On the Convergence Properties of the EM AlgorithmThe Annals of Statistics, 1983