Optimization Online


Recovery of a mixture of Gaussians by sum-of-norms clustering

Tao Jiang(tao.jiang***at***uwaterloo.ca)
Stephen Vavasis(vavasis***at***uwaterloo.ca)
Chen Wen Zhai(sabrina.zhai***at***edu.uwaterloo.ca)

Abstract: Sum-of-norms clustering is a method for assigning $n$ points in $\R^d$ to $K$ clusters, $1\le K\le n$, using convex optimization. Recently, Panahi et al.\ proved that sum-of-norms clustering is guaranteed to recover a mixture of Gaussians under the restriction that the number of samples is not too large. The purpose of this note is to lift this restriction, i.e., show that sum-of-norms clustering with equal weights can recover a mixture of Gaussians even as the number of samples tends to infinity. Our proof relies on an interesting characterization of clusters computed by sum-of-norms clustering that was developed inside a proof of the agglomeration conjecture by Chiquet et al. Because we believe this theorem has independent interest, we restate and reprove the Chiquet et al.\ result herein.

Keywords: sum-of-norms clustering; convex clustering; recovery guarantee; mixture of Gaussians

Category 1: Applications -- Science and Engineering (Statistics )

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )


Download: [PDF]

Entry Submitted: 02/19/2019
Entry Accepted: 02/19/2019
Entry Last Modified: 02/19/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society