Title: Recent progress on sum-of-norms clustering

Stephen Vavasis

Abstract: Clustering is perhaps the most classical and still central
problem of unsupervised machine learning.  Sum-of-norms clustering is a
formulation of the clustering problem as convex optimization.  Recently,
we showed using duality that sum-of-norms clustering is guaranteed to
recover data generated from a Gaussian mixture using a dual
characterization of the solution.  Duality also establishes an early
stopping test for the underlying optimization solver that guarantees the
correct clustering has been found.  Finally, we use ideas from the
theory of Euclidean distance matrices to strengthen the recovery
guarantees of the method.  

Joint work with Tao Jiang (Cornell), Samuel Tan (Cornell), and Sabrina Zhai (MIT).