Title: Exact clustering by semidefinite programming under the heterogeneous planted cluster model.

Abstract: Clustering, or the sorting of data into groups of similar items, is a fundamental task in machine learning and statistical analysis. Until recently, most computational methods for clustering relied on heuristics with no theoretical guarantee ensuring that clusters present in the data would be correctly identified. In this talk, I will present recent results partially addressing this issue. Specifically, I will discuss a new probabilistic model for clusterable data, called the heterogeneous planted cluster model, and establish conditions on the parameters in this model that ensure that the underlying clusters can be correctly identified using the solution of a particular semidefinite program. These results generalize earlier results guaranteeing perfect recovery under the stochastic block model. I will conclude with a discussion of first-order optimization methods for solving this semidefinite program and present empirical evidence of the efficacy of this approach.