Clustering subgaussian mixtures by semidefinite programming

DOI10.1093/IMAIAI/IAX001zbMATH Open1381.62189arXiv1602.06612OpenAlexW2963496884MaRDI QIDQ4603713FDOQ4603713

Rachel Ward, Soledad Villar, Dustin G. Mixon

Publication date: 19 February 2018

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: We introduce a model-free relax-and-round algorithm for k-means clustering based on a semidefinite relaxation due to Peng and Wei. The algorithm interprets the SDP output as a denoised version of the original data and then rounds this output to a hard clustering. We provide a generic method for proving performance guarantees for this algorithm, and we analyze the algorithm in the context of subgaussian mixture models. We also study the fundamental limits of estimating Gaussian centers by k-means clustering in order to compare our approximation guarantee to the theoretically optimal k-means clustering solution.

Full work available at URL: https://arxiv.org/abs/1602.06612

Recommendations

• Probably certifiably correct \(k\)-means clustering
• A spectral algorithm for learning mixture models
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Partial recovery bounds for clustering with the relaxed \(K\)-means
• Improved Conic Reformulations for $K$-means Clustering

zbMATH Keywords

clusteringmachine learningsemidefinite programmingapproximation algorithm

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Semidefinite programming (90C22)

Cites Work

• SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
• Rank-reducibility of a symmetric matrix and sampling theory of minimum trace factor analysis
• Community detection in sparse networks via Grothendieck's inequality
• Recovery guarantees for exemplar-based clustering
• On the construction of highly symmetric tight frames and complex polytopes
• Problems of distance geometry and convex properties of quadratic maps
• On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
• Fast computation of low-rank matrix approximations
• Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 15th international workshop, APPROX 2012, and 16th international workshop, RANDOM 2012, Cambridge, MA, USA, August 15--17, 2012. Proceedings
• Title not available (Why is that?)
• A spectral algorithm for learning mixture models
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Polynomial Learning of Distribution Families
• The Spectral Method for General Mixture Models

Cited In (28)

• A Dimension Reduction Technique for Large-Scale Structured Sparse Optimization Problems with Application to Convex Clustering
• Clustering mixtures with almost optimal separation in polynomial time
• Improved Conic Reformulations for $K$-means Clustering
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
• Identifiability of nonparametric mixture models and Bayes optimal clustering
• Fused clustering mean estimation of central subspace
• Title not available (Why is that?)
• On the tightness of SDP relaxations of QCQPs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering
• Fundamental limits of low-rank matrix estimation with diverging aspect ratios
• Partial recovery bounds for clustering with the relaxed \(K\)-means
• On Convex Hulls of Epigraphs of QCQPs
• The Ratio-Cut Polytope and K-Means Clustering
• Model assisted variable clustering: minimax-optimal recovery and algorithms
• Title not available (Why is that?)
• Learning polynomial transformations via generalized tensor decompositions
• Covariate Regularized Community Detection in Sparse Graphs
• Title not available (Why is that?)
• Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
• Accelerated first-order methods for a class of semidefinite programs
• \(k\)-median: exact recovery in the extended stochastic ball model
• Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018
• An \({\ell_p}\) theory of PCA and spectral clustering
• Sharp optimal recovery in the two component Gaussian mixture model

Uses Software

• SDPNAL+

This page was built for publication: Clustering subgaussian mixtures by semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603713)