Partial recovery bounds for clustering with the relaxed $K$means

  • 2018-07-19 17:33:30
  • Christophe Giraud, Nicolas Verzelen
  • 3

Abstract

We investigate the clustering performances of the relaxed $K$means in thesetting of sub-Gaussian Mixture Model (sGMM) and Stochastic Block Model (SBM).After identifying the appropriate signal-to-noise ratio (SNR), we prove thatthe misclassification error decay exponentially fast with respect to this SNR.These partial recovery bounds for the relaxed $K$means improve upon resultscurrently known in the sGMM setting. In the SBM setting, applying the relaxed$K$means SDP allows to handle general connection probabilities whereas otherSDPs investigated in the literature are restricted to the assortative case(where within group probabilities are larger than between group probabilities).Again, this partial recovery bound complements the state-of-the-art results.All together, these results put forward the versatility of the relaxed$K$means.

 

Quick Read (beta)

loading the full paper ...