Sharp kernel clustering algorithms and their associated Grothendieck inequalities

DOI10.1002/RSA.20398MaRDI QIDQ4921885zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Assaf Naor

Publication date 28 May 2013

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20398

zbMATH Keywords

approximation algorithmssemidefinite programmingunique games hardness

Mathematics Subject Classification ID

Approximation algorithms (68W25) Semidefinite programming (90C22) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Sharp kernel clustering algorithms and their associated Grothendieck inequalities
• The sharpness of some cluster set results
• A sharp version of Kahan's theorem on clustered eigenvalues
• Concentration of kernel matrices with application to kernel spectral clustering
• The geometry of kernelized spectral clustering
• Minkowski-type theorems and least-squares clustering
• Kernel Approximation on Algebraic Varieties
• Sharp \(L^{p}\) bounds on spectral clusters for Lipschitz metrics
• Sharp Kernels and Canonical Subspaces (Revised)
• Sharp inequalities of singular values of smooth kernels

Cites work

• A proof of the Grothendieck inequality
• Limit theorems for polylinear forms
• Near-optimal algorithms for unique games
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(6)

• Grothendieck constant is norm of Strassen matrix multiplication tensor
• Low correlation noise stability of symmetric sets
• New perspectives on k-support and cluster norms
• Approximate kernel clustering
• Solution of the propeller conjecture in R^3
• Sharp kernel clustering algorithms and their associated Grothendieck inequalities

This page was built for publication: Sharp kernel clustering algorithms and their associated Grothendieck inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4921885)