# How to round subspaces: a new spectral clustering algorithm

 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.