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[articlemathrsfs, amsmath, amssymbemptydocumentalign*_i=1^n_j=1^n a_ij=0align*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[articlemathrsfs, amsmath, amssymbemptydocumentalign*_i=1^k_j=1^k (_(p, q)S_i× S_ja_pq)b_ijalign*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[articlemathrsfs, amsmath, amssymbemptydocumentalign*R(B)^2C(B)align*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[articlemathrsfs, amsmath, amssymbemptydocumentalign*v_1, …, v_kR^kalign*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[articlemathrsfs, amsmath, amssymbemptydocumentalign*R^k-1align*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[articlemathrsfs, amsmath, amssymbemptydocumentalign*_i=1^k_j=1^k b_ijz_i, z_jalign*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[articlemathrsfs, amsmath, amssymbemptydocumentalign*z_iR^k-1align*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[articlemathrsfs, amsmath, amssymbemptydocumentalign*z_i=1(2π)^(k-1)/2_A_ixe^-\|x\|_2^2/2dxalign*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[articlemathrsfs, amsmath, amssymbemptydocumentalign*(1-ε)R(B)^2C(B)align*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