Name
Title | ||
|---|---|---|
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 → ∞ and α = m/n stays finite. Using exact but non-rigorous methods from statistical physics, we determine the critical value of α 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√α, there is a gap between the threshold for information-theoretically optimal performance and the threshold at which known algorithms succeed. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1109/ALLERTON.2016.7852287 | 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton) |
Keywords | DocType | Volume |
phase transitions,optimal algorithms,high-dimensional Gaussian mixture clustering,nonrigorous method,statistical physics,cluster distance,information theory,Bayes-optimal estimation algorithm,information-theoretically optimal performance,data science | Conference | abs/1610.02918 |
ISSN | ISBN | Citations |
2474-0195 | 978-1-5090-4551-8 | 2 |
PageRank | References | Authors |
0.37 | 10 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thibault Lesieur | 1 | 42 | 2.63 |
| Caterina De Bacco | 2 | 19 | 2.37 |
| Jess Banks | 3 | 2 | 0.37 |
| Florent Krzakala | 4 | 977 | 67.30 |
| Cristopher Moore | 5 | 1765 | 160.55 |
| Lenka Zdeborová | 6 | 1190 | 78.62 |