Home Page




Editorial Board

Special Issues

Open Source Software

Proceedings (PMLR)

Data (DMLR)

Transactions (TMLR)




Frequently Asked Questions

Contact Us

RSS Feed

Recovery of a Mixture of Gaussians by Sum-of-Norms Clustering

Tao Jiang, Stephen Vavasis, Chen Wen Zhai; 21(225):1−16, 2020.


Sum-of-norms clustering is a method for assigning $n$ points in $\mathbf{R}^d$ to $K$ clusters, $1\le K\le n$, using convex optimization. Recently, Panahi (2017) 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, that is, show that sum-of-norms clustering 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. (2017). Because we believe this theorem has independent interest, we restate and reprove the Chiquet et al. (2017) result herein.

© JMLR 2020. (edit, beta)