Clustering subgaussian mixtures by semidefinite programming
From MaRDI portal
Publication:4603713
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.
Recommendations
Cites work
- A probabilistic analysis of EM for mixtures of separated, spherical Gaussians
- A spectral algorithm for learning mixture models
- Approximating K‐means‐type Clustering via Semidefinite Programming
- 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
- Community detection in sparse networks via Grothendieck's inequality
- Fast computation of low-rank matrix approximations
- 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
- Polynomial Learning of Distribution Families
- Problems of distance geometry and convex properties of quadratic maps
- Rank-reducibility of a symmetric matrix and sampling theory of minimum trace factor analysis
- Recovery guarantees for exemplar-based clustering
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- The Spectral Method for General Mixture Models
Cited in
(33)- Fundamental limits of low-rank matrix estimation with diverging aspect ratios
- Clustering mixtures with almost optimal separation in polynomial time
- On Convex Hulls of Epigraphs of QCQPs
- Diffusion \(K\)-means clustering on manifolds: provable exact recovery via semidefinite relaxations
- Efficient, certifiably optimal clustering with applications to latent variable graphical models
- scientific article; zbMATH DE number 7370526 (Why is no real title available?)
- Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018
- Learning polynomial transformations via generalized tensor decompositions
- Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
- Model assisted variable clustering: minimax-optimal recovery and algorithms
- Improved Conic Reformulations for $K$-means Clustering
- On the tightness of SDP relaxations of QCQPs
- SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering
- Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
- Learning by unsupervised nonlinear diffusion
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
- \(k\)-median: exact recovery in the extended stochastic ball model
- Probably certifiably correct \(k\)-means clustering
- scientific article; zbMATH DE number 1124647 (Why is no real title available?)
- Partial recovery bounds for clustering with the relaxed \(K\)-means
- Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
- Sketch-and-solve approaches to \(k\)-means clustering by semidefinite programming
- Fused clustering mean estimation of central subspace
- scientific article; zbMATH DE number 7255037 (Why is no real title available?)
- The ratio-cut polytope and K-means clustering
- A dimension reduction technique for large-scale structured sparse optimization problems with application to convex clustering
- Identifiability of nonparametric mixture models and Bayes optimal clustering
- Covariate regularized community detection in sparse graphs
- scientific article; zbMATH DE number 7307486 (Why is no real title available?)
- Accelerated first-order methods for a class of semidefinite programs
- Recovery guarantees for exemplar-based clustering
- An \({\ell_p}\) theory of PCA and spectral clustering
- Sharp optimal recovery in the two component Gaussian mixture model
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)
