4
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .