Relax, No Need to Round

DOI10.1145/2688073.2688116zbMath1364.62144arXiv1408.4045MaRDI QIDQ2989030

Rachel Ward, Ravishankar Krishnaswamy, Afonso S. Bandeira, Soledad Villar, Pranjal Awasthi, Moses Charikar

Publication date: 19 May 2017

Published in: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

convex optimization; clustering; \(k\)-means; exact recovery; \(k\)-medians

Mathematics Subject Classification ID

62H30: Classification and discrimination; cluster analysis (statistical aspects)

90C25: Convex programming

Related Items

Unnamed Item, Improved Conic Reformulations for $K$-means Clustering, Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization, Non-convex clustering via proximal alternating linearized minimization method, Unnamed Item, Local Versions of Sum-of-Norms Clustering, The Ratio-Cut Polytope and K-Means Clustering, Discrete facility location in machine learning, SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering, Memory-Efficient Structured Convex Optimization via Extreme Point Sampling, Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model, Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance, \(k\)-median: exact recovery in the extended stochastic ball model, Probably certifiably correct \(k\)-means clustering, A note on probably certifiably correct algorithms, Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018, On semidefinite relaxations for the block model, Near-optimal large-scale k-medoids clustering, An \({\ell_p}\) theory of PCA and spectral clustering, Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering, When do birds of a feather flock together? \(k\)-means, proximity, and conic programming, Partial recovery bounds for clustering with the relaxed \(K\)-means, Efficient, certifiably optimal clustering with applications to latent variable graphical models