Computer Science/Discrete Mathematics Seminar II | |

Topic: | How to round subspaces: a new spectral clustering algorithm |

Speaker: | Ali Kemal Sinop |

Affiliation: | Simons Institute for the Theory of Computing, Berkeley |

Date: | Tuesday, February 10 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | http://video.ias.edu/csdm/2015/0210-AliKemalSinop |

Given a $k$-dimensional linear subspace, consider the problem of approximating it (with respect to the spectral norm) in terms of another subspace spanned by the indicators of a $k$-partition of the coordinates. This is known as the spectral clustering problem, first introduced by [Kannan, Kumar]. It is a generalization of the standard $k$-means problem, which corresponds to the Frobenius norm. In this talk, I will present a new spectral clustering algorithm. Our algorithm finds a partition with spectral norm $O(\sqrt{OPT})$, where $OPT$ is best possible: Previously, no $o(k OPT)$ algorithm was known. I will also talk about various applications; such as decomposing a graph into disjoint union of expanders, finding a partition which minimizes the maximum expansion and so on.