Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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 \rightarrow \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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-cea.archives-ouvertes.fr/cea-01448112
Contributor : Emmanuelle de Laborderie <>
Submitted on : Friday, January 27, 2017 - 3:13:49 PM
Last modification on : Tuesday, September 22, 2020 - 3:49:52 AM
Long-term archiving on: : Saturday, April 29, 2017 - 3:53:59 AM

File

1610.02918v1.pdf
Files produced by the author(s)

Identifiers

Citation

Thibault Lesieur, Caterina de Bacco, Jess Banks, Florent Krzakala, Cris Moore, et al.. Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering. 2016. ⟨cea-01448112⟩

Share

Metrics

Record views

329

Files downloads

366