### Abstract

In the kernel clustering problem we are given a (large) n x n symmetric positive semidefinite matrix A = (a_{ij}) with ∑_{i=1} ^{n} ∑_{j=1}^{n} a_{ij} = 0 and a (small) k x k symmetric positive semidefinite matrix B = (b_{ij}). The goal is to find a partition {S_{1} , . . . , S_{k}} of {1 , . . . n} which maximizes ∑_{i=1}^{k} ∑_{j=1}^{k} (∑_{(p, q) ∈ Si x Sj} a_{pq}) b_{ij}. 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 b_{ij} = 〈v_{i},v_{j}〉 is the Gram matrix representation of B for some v_{1} , . . . , v_{k} ∈ ℝ^{k} then R(B) is the minimum radius of a Euclidean ball containing the points {v _{1} , . . . , v_{k}}. The parameter C(B) is defined as the maximum over all measurable partitions {A_{1} , . . . , A_{k}} of ℝ^{k-1} of the quantity ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij}(z_{i}, z_{j}), where for i ∈ {1 , . . . , k} the vector z_{i} ∈ ℝ^{k-1} is the Gaussian moment of A_{i}, 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 664-683 |

Number of pages | 20 |

State | Published - May 6 2010 |

Event | 21st Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, United States Duration: Jan 17 2010 → Jan 19 2010 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 21st Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | Austin, TX |

Period | 1/17/10 → 1/19/10 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Sharp kernel clustering algorithms and their associated Grothendieck inequalities'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 664-683). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).