Relax, No Need to Round

DOI10.1145/2688073.2688116zbMath1364.62144arXiv1408.4045OpenAlexW1986790896MaRDI 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 optimizationclustering\(k\)-meansexact recovery\(k\)-medians

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Convex programming (90C25)

Related Items (23)

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

This page was built for publication: Relax, No Need to Round