[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

Combinatorics & Theoretical Computer Science Seminar

Note: Different Location and Time:

Ali Kemal Sinop
UC Berkeley
www.cs.cmu.edu/~asinop

Tuesday, June 23, 2015
6045 S. Kenwood
TTIC - 530

Title: How to Round Subspaces: A New Spectral Clustering Algorithm
 
Abstract:
Consider the problem of approximating a $k$-dimensional linear subspace with another {$k$-piecewise} constant subspace in spectral norm. This problem is at the heart of many spectral methods used in data clustering and graph partitioning.  Our main contribution is a new spectral clustering algorithm: It can recover a $k$-partition such that the subspace corresponding to the span of its indicator vectors is $O(\sqrt{opt})$ close to the original subspace in spectral norm, with $opt$ being the minimum possible. Moreover our algorithm does
not impose any restriction on the cluster sizes. Previously, no algorithm was known which could find a $k$-partition closer than $o(k \cdot opt)$.
We present two applications for our algorithm. First one finds a disjoint union of $k$-expanders which approximate a given graph in spectral norm. The second one is for approximating the $k$-partition whose clusters have expansion at most $\phi_k$ on graphs satisfying $\phi_k \le O(\lambda_{k+1})$ where $\lambda_{k+1}$ is the $(k+1)^{th}$ eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required $\phi_k \le O(\lambda_{k+1}/k)$.
 
Host: Prof. Madhur Tulsiani
 
(Refreshments will be served prior to the talk at 2:45 p.m. in TTIC – 526)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150618/68c00bf7/attachment.htm