Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Exact recovery of clusters via k-means SDP relaxation

Student-Run Applied & Math Seminar

Speaker: Yang Li, UC Davis Mathematics
Location: 2112 MSB
Start time: Wed, Nov 16 2016, 12:10PM

The classic Lloyd's algorithm solves the k-means problem efficiently but has no theoretical guarantee. However, by considering an SDP relaxation of the k-means problem, we can derive exact recovery under the random ball model, and the question becomes what is the necessary separation between these balls.

RSVP for Pizza