Abstract

Recently, Awasthi et al. introduced an SDP relaxation of the kk-means problem in Rm\mathbb R^m. In this work, we consider a random model for the data points in which kk balls of unit radius are deterministically distributed throughout Rm\mathbb R^m, and then in each ball, nn points are drawn according to a common rotationally invariant probability distribution. For any fixed ball configuration and probability distribution, we prove that the SDP relaxation of the kk-means problem exactly recovers these planted clusters with probability 1−e−Ω(n)1-e^{-Ω(n)} provided the distance between any two of the ball centers is >2+ε>2+ε, where εε is an explicit function of the configuration of the ball centers, and can be arbitrarily small when mm is large.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.