TY - GEN

T1 - Sharp kernel clustering algorithms and their associated Grothendieck inequalities

AU - Khot, Subhash

AU - Naor, Assaf

PY - 2010/5/6

Y1 - 2010/5/6

N2 - In the kernel clustering problem we are given a (large) n x n symmetric positive semidefinite matrix A = (aij) with ∑i=1 n ∑j=1n aij = 0 and a (small) k x k symmetric positive semidefinite matrix B = (bij). The goal is to find a partition {S1 , . . . , Sk} of {1 , . . . n} which maximizes ∑i=1k ∑j=1k (∑(p, q) ∈ Si x Sj apq) bij. We design a polynomial time approximation algorithm that achieves an approximation ratio of 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 bij = 〈vi,vj〉 is the Gram matrix representation of B for some v1 , . . . , vk ∈ ℝk then R(B) is the minimum radius of a Euclidean ball containing the points {v 1 , . . . , vk}. The parameter C(B) is defined as the maximum over all measurable partitions {A1 , . . . , Ak} of ℝk-1 of the quantity ∑i=1k ∑j=1k bij(zi, zj), where for i ∈ {1 , . . . , k} the vector zi ∈ ℝk-1 is the Gaussian moment of Ai, 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)2/C(B) is Unique Games hard.

AB - In the kernel clustering problem we are given a (large) n x n symmetric positive semidefinite matrix A = (aij) with ∑i=1 n ∑j=1n aij = 0 and a (small) k x k symmetric positive semidefinite matrix B = (bij). The goal is to find a partition {S1 , . . . , Sk} of {1 , . . . n} which maximizes ∑i=1k ∑j=1k (∑(p, q) ∈ Si x Sj apq) bij. We design a polynomial time approximation algorithm that achieves an approximation ratio of 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 bij = 〈vi,vj〉 is the Gram matrix representation of B for some v1 , . . . , vk ∈ ℝk then R(B) is the minimum radius of a Euclidean ball containing the points {v 1 , . . . , vk}. The parameter C(B) is defined as the maximum over all measurable partitions {A1 , . . . , Ak} of ℝk-1 of the quantity ∑i=1k ∑j=1k bij(zi, zj), where for i ∈ {1 , . . . , k} the vector zi ∈ ℝk-1 is the Gaussian moment of Ai, 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)2/C(B) is Unique Games hard.

UR - http://www.scopus.com/inward/record.url?scp=77951697840&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951697840&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:77951697840

SN - 9780898717013

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 664

EP - 683

BT - Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 2010 through 19 January 2010

ER -