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.