Adaptive Clustering through Semidefinite Programming
We analyze the clustering problem through a flexible probabilistic model that aims to identify an optimal partition on the sample X 1 , ..., X n . We perform exact clustering with high probability using a convex semidefinite estimator that interprets as a corrected, relaxed version of K-means. The estimator is analyzed through a non-asymptotic framework and showed to be optimal or near-optimal in recovering the partition. Furthermore, its performances are shown to be adaptive to the problem's effective dimension, as well as to K the unknown number of groups in this partition. We illustrate the method's performances in comparison to other classical clustering algorithms with numerical experiments on simulated high-dimensional data.
In this work, we build upon the work and context of [6], and transpose and adapt their ideas for point clustering: we introduce a semidefinite estimator for point clustering inspired by the findings of [17] with a correction component originally presented in [6]. We show that it produces a very strong contender for clustering recovery in terms of speed, adaptivity and robustness to model perturbations. In order to do so we produce a flexible probabilistic model inducing an optimal partition of the data that we aim to recover. Using the same structure of proof in a different context, we establish elements of stochastic control (see for instance Lemma A.1 on the concentration of random subgaussian Gram matrices in the supplementary material) to derive conditions of exact clustering recovery with high probability and show optimal performances -including in high dimensions, improving on [16], as well as adaptivity to the effective dimension of the problem. We also show that our results continue to hold without knowledge of the number of structures given one single positive tuning parameter. Lastly we provide evidence of our method's efficiency and further insight from simulated data.
Notation. Throughout this work we use the convention 0/0 := 0 and [n] = {1, ..., n}. We take a n b n to mean that a n is smaller than b n up to an absolute constant factor. Let S d−1 denote the unit sphere in R d . For q ∈ N * ∪ {+∞}, ν ∈ R d , |ν| q is the l q -norm and for M ∈ R d×d , |M | q , |M | F and |M | op are respectively the entry-wise l q -norm, the Frobenius norm associated with scalar product ., . and the operator norm. |D| V is the variation semi-norm for a diagonal matrix D, the difference between its maximum and minimum element. Let A B mean that A − B is symmetric, positive semidefinite.
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. So, for a better picture, it would have been good to see some results on computation times.
The paper is nicely written and the flow of arguments in the paper is relatively clear. There are some minor typos like in line 111 in definition of b2, the subscript should be b in [n]\{a, b1}.
The paper extends an approach of semidefinite relaxation for K-means clustering to account for non-isotropic behavior of mixture components. The method proposed can work for high-dimensional data too. The method will be quite useful but possibly computationally heavy too. So, an idea about the computational resources necessary to implement this method would have been useful.