Sharp kernel clustering algorithms and their associated Grothendieck inequalities. Issue 3 (29th February 2012)

• Record Type: Journal Article
• Authors: Khot, Subhash; Naor, Assaf
• Is Part Of: Random structures & algorithms. Volume 42:Issue 3(2013)
• Page Start: 269
• Page End: 300
• Publication Date: 2012-02-29
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20398
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>In the kernel clustering problem we are given a (large) <italic>n</italic> × <italic>n</italic> symmetric positive semidefinite matrix <italic>A</italic> = (<italic>a</italic><sub><italic>i</italic><italic>j</italic></sub>) with <tex-math notation="LaTeX"><![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}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1v9zc8s7" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> and a (small) <italic>k</italic> × <italic>k</italic> symmetric positive semidefinite matrix <italic>B</italic> = (<italic>b</italic><sub><italic>i</italic><italic>j</italic></sub>). The goal is to find a partition {<italic>S</italic><sub>1</sub>, …, <italic>S</italic><sub><italic>k</italic></sub>} of {1, …<italic>n</italic>} which maximizes <tex-math notation="LaTeX"><![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}]]></tex-math><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 <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\frac{R(B)^2}{C(B)}\end{align*}\end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1v9zc91m" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, where <italic>R</italic>(<italic>B</italic>) and <italic>C</italic>(<italic>B</italic>) are geometric parameters that depend only on the matrix <italic>B</italic>, defined as follows: if <italic>b</italic><sub><italic>i</italic><italic>j</italic></sub> = 〈<italic>v</italic><sub><italic>i</italic></sub>, <italic>v</italic><sub><italic>j</italic></sub>〉 is the Gram matrix representation of <italic>B</italic> for some <tex-math notation="LaTeX"><![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}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1v9zc902" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> then <italic>R</italic>(<italic>B</italic>) is the minimum radius of a Euclidean ball containing the points {<italic>v</italic><sub>1</sub>, …, <italic>v</italic><sub><italic>k</italic></sub>}. The parameter <italic>C</italic>(<italic>B</italic>) is defined as the maximum over all measurable partitions {<italic>A</italic><sub>1</sub>, …, <italic>A</italic><sub><italic>k</italic></sub>} of <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathbb{R}^{k-1}\end{align*}\end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1v9zc8xf" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> of the quantity <tex-math notation="LaTeX"><![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}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1v9zc8ts" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, where for <italic>i</italic>∈{1, …, <italic>k</italic>} the vector <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}z_i\in \mathbb{R}^{k-1}\end{align*}\end{document}]]></tex-math><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 <italic>A</italic><sub><italic>i</italic></sub>, i.e., <tex-math notation="LaTeX"><![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}]]></tex-math><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 <tex-math notation="LaTeX"><![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}]]></tex-math><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</p> </abstract>