Sharp kernel clustering algorithms and their associated Grothendieck inequalities
Subhash Khot, Assaf Naor · 2010
In the kernel clustering problem we are given a (large) n×n symmetric positive semidefinite matrix A=(ai j) with ∑n ∑nj=1 i=1 ai j = 0 and a (small) k×k symmetric positive semidefinite matrix B=(bi j). The goal is to find a partition{S 1,..., S k} of{1,... n} which maximizes ∑k ∑ ( ∑ kj=1 i=1 (p,q)∈S i×S j apq bi j. 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 bi j= 〈vi, v j 〉 is the Gram matrix representation of B for some v1,...,vk∈R 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} ofR k−1 of the quantity ∑k ∑kj=1 i=1 bi j〈zi, z j〉, where for i∈{1,..., k} the vector zi∈R k−1 1 is the Gaussian moment of Ai, i.e., zi= (2π)(k−1)/2 ∫ xe−‖x‖2 2 /2dx. We also show that for everyε>0, achieving an approximation guarantee of (1−ε) R(B)2 C(B)