Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering

Abstract

We consider the problem of Gaussian mixture clustering in the high-dimensional limit where the data consists of $m$ points in $n$ dimensions, $n,m\to \infty$ and $\alpha =m/n$ stays finite. Using exact but non-rigorous methods from statistical physics, we determine the critical value of $\alpha$ and the distance between the clusters at which it becomes information-theoretically possible to reconstruct the membership into clusters better than chance. We also determine the accuracy achievable by the Bayes-optimal estimation algorithm. In particular, we find that when the number of clusters is sufficiently large, $r>4+2\sqrt{\alpha }$, there is a gap between the threshold for information-theoretically optimal performance and the threshold at which known algorithms succeed.

8 pages, 3 figures, conference

References in corpus (7)

• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Statistical physics of inference: Thresholds and algorithms
• Universality in polytope phase transitions and message passing algorithms
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Mutual Information in Rank-One Matrix Estimation
• A note on classical ground state energies
• Phase transitions in optimal unsupervised learning

Cited by in corpus (3)

• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Streaming Bayesian inference: theoretical limits and mini-batch approximate message-passing
• Low-rank Matrix Estimation with Inhomogeneous Noise