Time: Monday, May 01, 2017, 1:00pm @ MTH3206

Speaker: Dustin Mixon (Air Force)

Title: A semidefinite relaxation of k-means clustering

Abstract: Recently, Awasthi et al proved that a semidefinite relaxation of the k-means clustering problem is tight under a particular data model called the stochastic ball model. This result exhibits two shortcomings: (1) naive solvers of the semidefinite program are computationally slow, and (2) the stochastic ball model prevents outliers that occur, for example, in the Gaussian mixture model. This talk will cover recent work that tackles each of these shortcomings. First, I will discuss a new type of algorithm (introduced by Bandeira) that combines fast non-convex solvers with the optimality certificates provided by convex relaxations. Second, I will discuss how to analyze the semidefinite relaxation under the Gaussian mixture model. In this case, outliers in the data obstruct tightness in the relaxation, and so fundamentally different techniques are required. Several open problems will be posed throughout. This is joint work with Takayuki Iguchi and Jesse Peterson (AFIT), as well as Soledad Villar and Rachel Ward (UT Austin).