Clustering subgaussian mixtures by semidefinite programming

DOI10.1093/imaiai/iax001zbMath1381.62189arXiv1602.06612OpenAlexW2963496884MaRDI QIDQ4603713

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)

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

zbMATH Keywords

semidefinite programmingclusteringapproximation algorithmmachine learning

Mathematics Subject Classification ID

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

Related Items

On Convex Hulls of Epigraphs of QCQPs ⋮ On the tightness of SDP relaxations of QCQPs ⋮ The Ratio-Cut Polytope and K-Means Clustering ⋮ Unnamed Item ⋮ Improved Conic Reformulations for $K$-means Clustering ⋮ Unnamed Item ⋮ Model assisted variable clustering: minimax-optimal recovery and algorithms ⋮ \(k\)-median: exact recovery in the extended stochastic ball model ⋮ Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering ⋮ SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering ⋮ Unnamed Item ⋮ Identifiability of nonparametric mixture models and Bayes optimal clustering ⋮ Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018 ⋮ When do birds of a feather flock together? \(k\)-means, proximity, and conic programming ⋮ Partial recovery bounds for clustering with the relaxed \(K\)-means ⋮ Unnamed Item ⋮ Covariate Regularized Community Detection in Sparse Graphs ⋮ Unnamed Item ⋮ Sharp optimal recovery in the two component Gaussian mixture model ⋮ An \({\ell_p}\) theory of PCA and spectral clustering ⋮ Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model ⋮ A Dimension Reduction Technique for Large-Scale Structured Sparse Optimization Problems with Application to Convex Clustering

Uses Software

• SDPNAL+

Cites Work

• Unnamed Item
• 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
• SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
• A spectral algorithm for learning mixture models
• Community detection in sparse networks via Grothendieck's inequality
• Rank-reducibility of a symmetric matrix and sampling theory of minimum trace factor analysis
• Recovery guarantees for exemplar-based clustering
• Problems of distance geometry and convex properties of quadratic maps
• On the construction of highly symmetric tight frames and complex polytopes
• On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
• Fast computation of low-rank matrix approximations
• The Spectral Method for General Mixture Models
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Polynomial Learning of Distribution Families