Seminar: March 8
Daniel Spielman, Yale University
Spectral Sparsification of Graphs and Approximations of Matrices
It turns out that Ramanujan expanders are the best sparse spectral approximations of complete graphs. We prove that every graph can be approximated almost as well by a sparse graph as the complete graphs are by Ramanujan expanders. We also present an efficient randomized algorithm for constructing sparse approximations which 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.