mlsanityData to 14 Oct 2026

Clustering subgaussian mixtures by semidefinite programming

arXiv 1602.06612 ↗First posted 22 Feb 2016stat.ML cs.DS cs.ITcited by 19

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). First posted on arXiv 22 Feb 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 5; 2023: 2; 2024: 1; 2025: 2; 2026: 4.

19 papers.

Sort:

  1. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  2. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  3. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  4. 2023Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programmingcited by 9
  5. 2021Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimizationcited by 6
  6. 2022Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clusteringcited by 6
  7. 2021Robust Model Selection and Nearly-Proper Learning for GMMscited by 3
  8. 2022Tight Bounds on the Hardness of Learning Simple Nonparametric Mixturescited by 3
  9. 2022Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous Datacited by 2
  10. 2022Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimizationcited by 1
  11. 2022Sketch-and-solve approaches to k-means clustering by semidefinite programmingcited by 1
  12. 2024The inexact power augmented Lagrangian method for constrained nonconvex optimizationcited by 1
7 more
  1. 2026Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transformscited by 1
  2. 2026The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids Itcited by 1
  3. 2023Semidefinite programming on population clustering: a global analysiscited by 0
  4. 2025Convex Clustering Redefined: Robust Learning with the Median of Means Estimatorcited by 0
  5. 2025BalLOT: Balanced k-means clustering with optimal transportcited by 0
  6. 2026The Condition-Number Principle for Prototype Clusteringcited by 0
  7. 2026GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimizationcited by 0