MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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

share|cite|improve this answer

Your Answer


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.