FoCM 2014 conference
Workshop A2 - Computational Harmonic Analysis, Image and Signal Processing
No date set
Relax, no need to round: Integrality of clustering formulations
Soledad Villar
University of Texas at Austin, United States - mvillar@math.utexas.edu
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 (this 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 guarantees).
In this work we take the second approach applied to point cloud clustering problems; showing recovery conditions of an 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.
Joint work with P. Awasthi (Princeton University), A. S. Bandeira (Princeton University), M. Charikar (Princeton University), R. Krishnaswamy (Princeton University) and R. Ward (University of Texas at Austin).