Sharp kernel clustering algorithms and their associated Grothendieck inequalities. Issue 3 (29th February 2012) - Khot, Subhash; Naor, Assaf
Abstract In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (aij) with <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0\end{align*}\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg1v9zc8s7" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> and a (small) k × k symmetric positive semidefinite matrix B = (bij). The goal is to find a partition {S1, …, Sk} of {1, …n} which maximizes <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\sum_{i=1}^k\sum_{j=1}^k \left(\sum_{(p, q)\in S_i\times S_j}a_{pq}\right)b_{ij}\end{align*}\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg1v9zc8rp" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />. We design a polynomial time approximation algorithm that achieves an approximation ratio of <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\frac{R(B)^2}{C(B)}\end{align*}\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg1v9zc91m" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, 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 <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}v_1, \ldots, v_k\in \mathbb{R}^k\end{align*}\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg1v9zc902" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> 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} of <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathbb{R}^{k-1}\end{align*}\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg1v9zc8xf" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> of the quantity <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\sum_{i=1}^k\sum_{j=1}^k b_{ij}\langle z_i, z_j\rangle\end{align*}\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg1v9zc8ts" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, where for i∈{1, …, k} the vector <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}z_i\in \mathbb{R}^{k-1}\end{align*}\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg1v9zc991" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> is the Gaussian moment of Ai, i.e., <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}z_i=\frac{1}{(2\pi)^{(k-1)/2}}\int_{A_i}xe^{-\|x\|_2^2/2}dx\end{align*}\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg1v9zc96c" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />. We also show that for every ε > 0, achieving an approximation guarantee of <![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}(1-\varepsilon)\frac{R(B)^2}{C(B)}\end{align*}\end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg1v9zc95t" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> is Unique Games hard. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013