# Semidefinite programming on population clustering: a global analysis

arXiv: https://arxiv.org/abs/2301.00344 · HTML: https://mlsanity.com/paper/2301.00344/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 45 references that are in the map.
- First posted on arXiv 1 Jan 2023.

## Builds on (most cited first, 11 of 11)

- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [Community detection in sparse networks via Grothendieck's inequality](https://mlsanity.com/paper/1411.4686/) (2014)
- [Clustering subgaussian mixtures by semidefinite programming](https://mlsanity.com/paper/1602.06612/) (2016)
- [Relax, no need to round: integrality of clustering formulations](https://mlsanity.com/paper/1408.4045/) (2014)
- [A Two-round Variant of EM for Gaussian Mixtures](https://mlsanity.com/paper/1301.3850/) (2013)
- [Probably certifiably correct k-means clustering](https://mlsanity.com/paper/1509.07983/) (2015)
- [When Do Birds of a Feather Flock Together? k-Means, Proximity, and Conic Programming](https://mlsanity.com/paper/1710.06008/) (2017)
- [Hidden Integrality and Semi-random Robustness of SDP Relaxation for Sub-Gaussian Mixture Model](https://mlsanity.com/paper/1803.06510/) (2018)
- [Joint mean and covariance estimation with unreplicated matrix-variate data](https://mlsanity.com/paper/1611.04208/) (2016)

## Abstract (arXiv)

In this paper, we consider the problem of partitioning a small data sample of size n drawn from a mixture of 2 sub-gaussian distributions. Our work is motivated by the application of clustering individuals according to their population of origin using markers, when the divergence between the two populations is small. We are interested in the case that individual features are of low average quality γ, and we want to use as few of them as possible to correctly partition the sample. We consider semidefinite relaxation of an integer quadratic program which is formulated essentially as finding the maximum cut on a graph where edge weights in the cut represent dissimilarity scores between two nodes based on their features. A small simulation result in Blum, Coja-Oghlan, Frieze and Zhou (2007, 2009) shows that even when the sample size n is small, by increasing p so that np= Omega(1/γ2), one can classify a mixture of two product populations using the spectral method therein with success rate reaching an ``oracle'' curve. There the ``oracle'' was computed assuming that distributions were known, where success rate means the ratio between correctly classified individuals and the sample size n. In this work, we show the theoretical underpinning of this observed concentration of measure phenomenon in high dimensions, simultaneously for the semidefinite optimization goal and the spectral method, where the input is based on the gram matrix computed from centered data. We allow a full range of tradeoffs between the sample size and the number of features such that the product of these two is lower bounded by 1/γ2 so long as the number of features p is lower bounded by 1/γ.