Sharp kernel clustering algorithms and their associated Grothendieck inequalities

In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (a_ij) with ∑ⁿ_i=1 ∑ⁿ_j=1 a_ij=0 and a (small) k × k symmetric positive semidefinite matrix B = (b_ij). The goal is to find a partition {S₁,...,S_k} of {1,...n} which maximizes ∑^k_i=1 ∑^k_i=1 (∑_{(p,q)εSi×Sj} a_pq)b_ij. We design a polynomial time approximation algorithm that achieves an approximation ratio of R(B)²/C(B), where R(B) and C(B) are geometric parameters that depend only on the matrix B, defined as follows: if b_ij = 〈v_i,v_j〉 is the Gram matrix representation of B for some v₁,....,v_kεℝ^k then R(B) is the minimum radius of a Euclidean ball containing the points {v₁,...,v_k}. The parameter C(B) is defined as the maximum over all measurable partitions {A₁,...,A_k} of ℝ^k-1 of the quantity ∑^k_i=1 ∑^k_j=1n_ij 〈Z_i, Z_j〉where for iε{1,...,k} the vector Z_i ε ℝ^k-1 is the Gaussian moment of A_i. We also show that for every ε > 0, achieving an approximation guarantee of is Unique Games hard.