`

Timezone: »

 
Poster
Adaptive Clustering through Semidefinite Programming
Martin Royer

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #211 #None

We analyze the clustering problem through a flexible probabilistic model that aims to identify an optimal partition on the sample X1,...,Xn. 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.

Author Information

Martin Royer (Université Paris-Saclay)