Skip to yearly menu bar Skip to main content


Poster

Adaptive Clustering through Semidefinite Programming

Martin Royer

Pacific Ballroom #211

Keywords: [ Clustering ] [ Convex Optimization ] [ Theory ]


Abstract:

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.

Live content is unavailable. Log in and register to view live content