Analysis and Operator Theory Seminar - Dustin Mixon

September 9, 2017
Tuesday, September 19, 2017 - 11:30am to 12:25pm
Cockins Hall 240
photo of Dustin Mixon

Title: A semidefinite relaxation of k-means clustering

Speaker: Dustin Mixon (Ohio State University)

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).

S M T W T F S
 
 
 
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
9
 
10
 
11
 
12
 
13
 
14
 
15
 
16
 
17
 
18
 
19
 
20
 
21
 
22
 
23
 
24
 
25
 
26
 
27
 
28