A Caltech Library Service

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

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

PDF - Published Version
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
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2007 Sanjoy Dasgupta and Leonard Schulman. The first author 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.
Funding AgencyGrant Number
Subject Keywords:expectation maximization, mixtures of Gaussians, clustering, unsupervised learning, probabilistic analysis
Record Number:CaltechAUTHORS:DASjmlr07
Persistent 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:24 Feb 2020 17:06

Repository Staff Only: item control page