Partial recovery bounds for clustering with the relaxed \(K\)-means (Q2319817)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partial recovery bounds for clustering with the relaxed \(K\)-means |
scientific article |
Statements
Partial recovery bounds for clustering with the relaxed \(K\)-means (English)
0 references
20 August 2019
0 references
Summary: We investigate the clustering performances of the relaxed \(K\)-means in the setting of sub-Gaussian Mixture Model (sGMM) and Stochastic Block Model (SBM). After identifying the appropriate signal-to-noise ratio (SNR), we prove that the misclassification error decays exponentially fast with respect to this SNR. These partial recovery bounds for the relaxed \(K\)-means improve upon results currently known in the sGMM setting. In the SBM setting, applying the relaxed \(K\)-means SDP allows us to handle general connection probabilities whereas other SDPs investigated in the literature are restricted to the (dis-)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.
0 references
relaxed \(K\)-means
0 references
clustering
0 references
partial recovery bound
0 references
mixture of sub-Gaussian
0 references
stochastic block model
0 references
0 references
0 references
0 references