Spectral Sparsification of Graphs and Approximations of Matrices
Room:
CS 3310 Speaker: Daniel Spielman
Affiliation: Yale University
Expander graphs can be viewed as sparse approximations of complete graphs,
with Ramanujan expanders providing the best possible approximation.
We formalize this notion of approximation and ask how
well a given graph can be approximated by a sparse graph.
We prove that every graph can be approximated by a sparse graph
almost as well as the complete graphs are approximated by
the Ramanujan expanders: our approximations employ at most
twice as many edges to achieve the same approximation factor.
We also present an efficient randomized algorithm for constructing
sparse approximations that only uses a logarithmic factor more edges
than optimal.
Our algorithms follow from the solution of a problem in linear
algebra. Given any expression of a rank-n symmetric matrix A as a sum
of rank-1 symmetric matrices, we show that A can be well approximated
by a weighted sum of only O(n) of those rank-1 matrices.
This is joint work with Joshua Batson, Nikhil Srivastava and Shang-Hua
Teng.
Event Date: