Exact Recovery via Convex Relaxations
summary
Convex relaxations often recover exact clusterings under random models: experiments show a pairwise LP is integral 88% of the time, strengthened to 100% for protein and NLP instances; for synthetic concentric-ball data a K‑median LP is integral for cluster separation Δ > 2+ε (radius 1), while the K‑means LP can fail but a K‑means SDP is integral given larger Δ and high ambient dimension. Proofs use LP/SDP dual certificates; an SDP for multi‑reference alignment exhibits an unexplained rank‑recovery phenomenon.
AI-written summary · about
chapters (15)
- 0:00Intro
- 3:03Can relaxations be integral?
- 6:07Integrality of convex relaxations
- 11:00(Semi)-random graph partitioning
- 13:13Planted Correlation Clustering
- 14:47Thesis
- 18:26Distribution on inputs [Nellore, Ward 14]
- 21:35Lloyd's method can fail
- 25:22K-median LP relaxation
- 29:06k-means LP relaxation
- 34:26Results
- 38:21Proof Strategy
- 40:05Failure of k-means LP
- 41:19k-means SDP analysis
- 43:35Multireference alignment
related talks
47mLearning Probabilistic Models for Graph Partitioning in the Presence of Noise
40mMonte Carlo Approximation Certificates for K-Means Clustering
43mComputational and Statistical Tradeoffs via Convex Relaxation
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
40mThe Trimmed Lasso: Sparse Recovery Guarantees And Practical Optimization
25mLucky Talk: From Coding to Clustering
35mLocal Statistics, Semidefinite Programming, and Community Detection II
34mA Polynomial Time Algorithm for Lossy Population Recovery