Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I once may have heard (but I may misremember or misunderstand), that the problem of deciding how many local maxima a mixture of Gaussians has is NP-hard.

Is this true, or is the hardness of this problem is an open problem? Can anyone give a reference, if it is a well-known result?

share|improve this question

1 Answer 1

This year's FOCS paper seems relevant.

"Settling the Polynomial Learnability of Mixtures of Gaussians"

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We give an algorithm for this problem that has a running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy, with provably minimal assumptions on the Gaussians.

Edit 10/25: Suresh has a nice summary of the two papers that appeared on this problem here http://geomblog.blogspot.com/2010/10/focs-day-1-clustering.html

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.