Reviews: Adaptive Clustering through Semidefinite Programming

The paper proposes a semidefinite relaxation for K-means clustering with isotropic and non-isotropic mixtures of sub-gaussian distributions in both high and low-dimensions. The paper has a good technical analysis of the methods proposed in it. There are some supporting empirical experiments too. However, one thing would have been useful to see was how computation time scales with both p and n. The empirical experiments considered n 30, which is pretty small for many application situations.