Spectral Sparsification of Graphs and Approximations of Matrices

We introduce a notion of what it means for one graph to be a good spectral approximation of another. This induces the problem of spectral sparsification: finding a sparse graph that is a good spectral approximation of a given graph.

It turns out that Ramanujan expanders are the best sparse spectral approximations of complete graphs. We show that every graph may be approximated almost as well by a sparse graph as the complete graphs are by Ramanujan graphs. We also present an efficient randomized algorithm for construction 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 a rank-n symmetric matrix A that is expressed 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.

发言人详细信息

Daniel Alan Spielman received his B.A. in Mathematics and Computer Science from Yale in 1992, and his Ph.D in Applied Mathematics from M.I.T. in 1995. He spent a year as a NSF Mathematical Sciences Postdoc in the Computer Science Department at U.C. Berkeley, and then taught in the Applied Mathematics Department at M.I.T. until 2005. Since 2006, he has been a Professor of Applied Mathematics and Computer Science at Yale University.

The awards he has received include the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 Godel Prize and the 2009 Fulkerson Prize. His main research interests include the design and analysis of algorithms,graph theory, machine learning, error-correcting codes and combinatorial scientific computing.

日期：
演讲者：
Dan Alan Spielman
所属机构：
Yale