Sharp kernel clustering algorithms and their associated Grothendieck inequalities

In the kernel clustering problem we are given a (large) $n\times n$ symmetric positive semidefinite matrix $A=(a_{ij})$ with $\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0$anda(small)$k\times k$symmetricpositivesemidefinitematrix$B=(b_{ij})$\mathrm{.}Thegoalistofindapartition${S_1,…,S_k}$of${1,… n}$whichmaximizes$ \sum_{i=1}^k\sum_{j=1}^k (\sum_{(p,q)\in S_i\times S_j}a_{pq})b_{ij}$. We design a polynomial time approximation algorithm that achieves an approximation ratio of $\frac{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 $b_{ij}=<v_i,v_j>$ is the Gram matrix representation of $B$ for some $v_1,\mathrm{.}\mathrm{.}\mathrm{.},v_k\in {\mathbb{R}}^k$ then $R(B)$ is the minimum radius of a Euclidean ball containing the points $\{v_1,\mathrm{.}\mathrm{.}\mathrm{.},v_k\}$. The parameter $C(B)$ is defined as the maximum over all measurable partitions $\{A_1,\mathrm{.}\mathrm{.}\mathrm{.},A_k\}$ of ${\mathbb{R}}^{k-1}$ of the quantity ${\sum }_{i=1}^k{\sum }_{j=1}^k{b}_{ij}<z_i,z_j>$, where for $i\in {1,…,k}$thevector$z_i\in \R^{k-1}$istheGaussianmomentof$A_i$, i.e., $z_i=\frac{1}{(2\pi {)}^{(k-1)\mathrm{/}2}}{\int }_{A_i}x{e}^{-\mathrm{\parallel }x{\mathrm{\parallel }}_2^2\mathrm{/}2}dx$. We also show that for every $\text{eps}>0$, achieving an approximation guarantee of $(1-\text{e})\frac{R(B{)}^2}{C(B)}$ is Unique Games hard.