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   -

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

View abstract PDF