[Ml-stat-talks] IDeAS Seminar today at 3:00 pm - 110 Fine Hall

Amit Singer amits at math.Princeton.EDU
Thu Sep 18 09:20:47 EDT 2014

DATE: Thursday Sept. 18 , 2014


PLACE: 110 Fine Hall 

TIME: 3:00 pm 

SPEAKER:Soledad Villar - University of Texas

TITLE: Integrality of clustering formulations


When dealing with combinatoric NP-hard problems one can either find an
efficient algorithm that works in every case but its solution is not optimal
(that is the philosophy behind approximation algorithms). Or efficiently
compute a probably optimal solution of the original problem under more
restrictive hypothesis (which is the spirit of compressed sensing recovery

In this talk we take the second approach applied to point cloud clustering
problems; showing recovery conditions of the integral solution through their
convex relaxations. We focus on two of the most common optimization problems
for unsupervised clustering: k-means and k-medians clustering. 

This talk is based on recent work with  P. Awasthi, A. S. Bandeira, M.
Charikar, R. Krishnaswamy and R. Ward. (http://arxiv.org/abs/1408.4045). 



Valerie Marino
Program Secretary
Program in Applied & Computational Mathematics
Tel: 609-258-3703
Fax: 609-258-1735
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/ml-stat-talks/attachments/20140918/024a735e/attachment.html>

More information about the Ml-stat-talks mailing list