A Caltech Library Service

A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians

Dasgupta, Sanjoy and Schulman, Leonard (2007) A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians. Journal of Machine Learning Research, 8 . pp. 203-226. ISSN 1533-7928.

See Usage Policy.


Use this Persistent URL to link to this item:


We show that, given data from a mixture of k well-separated spherical Gaussians in ℜd, a simple two-round variant of EM will, with high probability, learn the parameters of the Gaussians to near-optimal precision, if the dimension is high (d >> ln k). We relate this to previous theoretical and empirical work on the EM algorithm.

Item Type:Article
Additional Information:©2007 Sanjoy Dasgupta and Leonard Schulman. The first author [SD] is indebted to Daniel Hsu for suggesting many simplifications to the analysis, to the reviewers for significantly improving the presentation, and to the NSF for support under grant IIS-0347646.lman
Subject Keywords:expectation maximization, mixtures of Gaussians, clustering, unsupervised learning, probabilistic analysis
Record Number:CaltechAUTHORS:DASjmlr07
Persistent URL:
Alternative URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:8474
Deposited By: Archive Administrator
Deposited On:15 Aug 2007
Last Modified:02 Oct 2019 23:51

Repository Staff Only: item control page