TagsArticle Source
Sparsification of Graphs and Matrices
Abstract
Random graphs and expander graphs *can be viewed as *sparse approximations of complete graphs, with Ramanujan expanders providing the best possible approximations. We formalize this notion of approximation and ask how well an arbitrary 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. Our algorithms follow from the solution of a problem in linear algebra. Given an expression for 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 talk will draw connections between and provide useful context for the two talks that follow. This is joint work with Joshua Batson, Nikhil Srivastava and Shang-Hua Teng.