Sharp kernel clustering algorithms and their associated Grothendieck inequalities

In the kernel clustering problem we are given a (large) n x n symmetric positive semidefinite matrix A = (a_ij) with ∑_i=1 ⁿ ∑_j=1ⁿ a_ij = 0 and a (small) k x k symmetric positive semidefinite matrix B = (b_ij). The goal is to find a partition {S₁ , . . . , S_k} of {1 , . . . n} which maximizes ∑_i=1^k ∑_j=1^k (∑_{(p, q) ∈ Si x 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 ∑_i=1^k ∑_j=1^k b_ij(z_i, z_j), where for i ∈ {1 , . . . , k} the vector z_i ∈ ℝ^k-1 is the Gaussian moment of A_i, i.e., z _i = 1/(2π)^{(k -1)/2} ∫_Ai xe ^-∥x∥22/2 dx. We also show that for every ε > 0, achieving an approximation guarantee of (1 - ε) R(B)²/C(B) is Unique Games hard.