Sharp kernel clustering algorithms and their associated Grothendieck inequalities

Subhash Khot, Assaf Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In the kernel clustering problem we are given a (large) n x n symmetric positive semidefinite matrix A = (aij) with ∑i=1 nj=1n aij = 0 and a (small) k x k symmetric positive semidefinite matrix B = (bij). The goal is to find a partition {S1 , . . . , Sk} of {1 , . . . n} which maximizes ∑i=1kj=1k (∑(p, q) ∈ Si x 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 {v 1 , . . . , vk}. The parameter C(B) is defined as the maximum over all measurable partitions {A1 , . . . , Ak} of ℝk-1 of the quantity ∑i=1kj=1k bij(zi, zj), where for i ∈ {1 , . . . , k} the vector zi ∈ ℝk-1 is the Gaussian moment of Ai, i.e., z i = 1/(2π)(k -1)/2Ai xe -∥x∥22/2 dx. We also show that for every ε > 0, achieving an approximation guarantee of (1 - ε) R(B)2/C(B) is Unique Games hard.

Original languageEnglish (US)
Title of host publicationProceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
Pages664-683
Number of pages20
StatePublished - 2010
Event21st Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, United States
Duration: Jan 17 2010Jan 19 2010

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other21st Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityAustin, TX
Period1/17/101/19/10

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

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

Cite this