Abstract
Recently, Awasthi et al. introduced an SDP relaxation of the -means problem in . In this work, we consider a random model for the data points in which balls of unit radius are deterministically distributed throughout , and then in each ball, 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 -means problem exactly recovers these planted clusters with probability provided the distance between any two of the ball centers is , where is an explicit function of the configuration of the ball centers, and can be arbitrarily small when is large.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.