- Recovery of a mixture of Gaussians by sum-of-norms clustering Tao Jiang(tao.jianguwaterloo.ca) Stephen Vavasis(vavasisuwaterloo.ca) Chen Wen Zhai(sabrina.zhaiedu.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 ) Citation: Download: [PDF]Entry Submitted: 02/19/2019Entry Accepted: 02/19/2019Entry Last Modified: 02/19/2019Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.