Sharp kernel clustering algorithms and their associated Grothendieck inequalities

Subhash Khot, Assaf Naor

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (aij) with ∑ni=1nj=1 aij=0 and a (small) k × k symmetric positive semidefinite matrix B = (bij). The goal is to find a partition {S1,...,Sk} of {1,...n} which maximizes ∑ki=1ki=1 (∑(p,q)εSi×Sj apq)bij. We design a polynomial time approximation algorithm that achieves an approximation ratio of R(B)2/C(B), where R(B) and C(B) are geometric parameters that depend only on the matrix B, defined as follows: if bij = 〈vi,vj〉 is the Gram matrix representation of B for some v1,....,vkεℝk then R(B) is the minimum radius of a Euclidean ball containing the points {v1,...,vk}. The parameter C(B) is defined as the maximum over all measurable partitions {A1,...,Ak} of ℝk-1 of the quantity ∑ki=1kj=1nij 〈Zi, Zj〉where for iε{1,...,k} the vector Zi ε ℝk-1 is the Gaussian moment of Ai. We also show that for every ε > 0, achieving an approximation guarantee of is Unique Games hard.

Original languageEnglish (US)
Pages (from-to)269-300
Number of pages32
JournalRandom Structures and Algorithms
Issue number3
StatePublished - May 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


  • Approximation algorithms
  • Semidefinite programming
  • Unique Games hardness


Dive into the research topics of 'Sharp kernel clustering algorithms and their associated Grothendieck inequalities'. Together they form a unique fingerprint.

Cite this