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)- Recovery guarantees for exemplar-based clustering
- The ratio-cut polytope and K-means clustering
- Clustering mixtures with almost optimal separation in polynomial time
- Covariate regularized community detection in sparse graphs
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
- Improved Conic Reformulations for $K$-means Clustering
- Identifiability of nonparametric mixture models and Bayes optimal clustering
- Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
- Probably certifiably correct k-means clustering
- Fused clustering mean estimation of central subspace
- On the tightness of SDP relaxations of QCQPs
- scientific article; zbMATH DE number 7370526 (Why is no real title available?)
- scientific article; zbMATH DE number 7255037 (Why is no real title available?)
- A dimension reduction technique for large-scale structured sparse optimization problems with application to convex clustering
- SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering
- Fundamental limits of low-rank matrix estimation with diverging aspect ratios
- Diffusion \(K\)-means clustering on manifolds: provable exact recovery via semidefinite relaxations
- Sketch-and-solve approaches to \(k\)-means clustering by semidefinite programming
- Partial recovery bounds for clustering with the relaxed \(K\)-means
- Model assisted variable clustering: minimax-optimal recovery and algorithms
- On Convex Hulls of Epigraphs of QCQPs
- scientific article; zbMATH DE number 7307486 (Why is no real title available?)
- Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
- Learning by unsupervised nonlinear diffusion
- Learning polynomial transformations via generalized tensor decompositions
- Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
- scientific article; zbMATH DE number 1124647 (Why is no real title available?)
- 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
- Efficient, certifiably optimal clustering with applications to latent variable graphical models
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)
