The Hidden Convexity of Spectral Clustering
summary
Shows that K-way spectral clustering is recovered exactly by maximizing a contrast F(u)=sum_i G(u·x_i) on the sphere when G(√t) is strictly convex (plus a mild derivative condition), with the change-of-variables to the simplex revealing the hidden convexity so maxima sit at cluster directions. Proposes a fixed-point gradient iteration (generalizing tensor power) that enumerates the ±basis vectors, tolerates small perturbations, and achieves superlinear (e.g. cubic for fourth-moment/ICA) convergence; validated on concentric-ring toy data and image segmentation.
AI-written summary · about
chapters (19)
- 0:00Intro
- 1:36What is spectral clustering?
- 2:21Spectral bi-clustering of a graph
- 4:03Spectral (bi)clustering of data
- 5:37Multi-way clustering with k-means
- 8:29Allowable contrast functions
- 9:49Algorithms
- 11:21Image segmentation
- 12:11Spectral embedding into an orthogonal basis
- 14:11Hidden orthogonal basis structure
- 15:19Geometric recovery
- 17:49Hidden convexity
- 21:56More generally: Hidden Basis Recovery
- 24:41What makes tensor power iteration work?
- 25:53More examples: ICA
- 28:42Our results: Practical algorithm to find hidden basis
- 29:33Gradient iteration
- 37:30An interesting phenomenon
- 38:05Summary
related talks
37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures
01h 31mUnsupervised Learning
49mGeneralized Cheeger Inequalities and Constrained Clustering
27mOptimal Spectral Recovery Of A Planted Vector In A Subspace
01h 02mTheory and Big Data
29mApproximating Spherical Gaussian Mixtures
26mMathematical Approaches to Clustering
34mSubspace Clustering using Ensembles of K-Subspaces