Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering

DOI10.1007/s10208-019-09421-3zbMath1445.90109arXiv1806.11429OpenAlexW2963057284MaRDI QIDQ2189394

Thomas Strohmer, Shuyang Ling

Publication date: 15 June 2020

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingunsupervised learningcommunity detectionspectral clusteringgraph partitiongraph Laplacian

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Optimality conditions and duality in mathematical programming (90C46) Combinatorial optimization (90C27) Semi-infinite programming (90C34)

Related Items

The Ratio-Cut Polytope and K-Means Clustering, Unnamed Item, \(k\)-median: exact recovery in the extended stochastic ball model, Unnamed Item, When do birds of a feather flock together? \(k\)-means, proximity, and conic programming, A Performance Guarantee for Spectral Clustering

Uses Software

• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spectra of graphs
• Spectral clustering and the high-dimensional stochastic blockmodel
• User-friendly tail bounds for sums of random matrices
• A variational approach to the consistency of spectral clustering
• NP-hardness of Euclidean sum-of-squares clustering
• Probably certifiably correct \(k\)-means clustering
• On semidefinite relaxations for the block model
• Random Laplacian matrices and convex relaxations
• When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
• Consistency of spectral clustering in stochastic block models
• Consistency of spectral clustering
• Diffusion maps
• From graph to manifold Laplacian: the convergence rate
• Lectures on Modern Convex Optimization
• Exact Recovery in the Stochastic Block Model
• Relax, No Need to Round
• Improved Spectral-Norm Bounds for Clustering
• The Planar k-Means Problem is NP-Hard
• Community Detection and Stochastic Block Models
• Clustering subgaussian mixtures by semidefinite programming
• Spectral convergence of the connection Laplacian from random samples
• Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps
• Least squares quantization in PCM
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Learning Theory
• The Rotation of Eigenvectors by a Perturbation. III
• Expander flows, geometric embeddings and graph partitioning