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.