Spectral Sparsification of Graphs and Approximations of Matrices

780 views · Published 17 August 2016 · 1:17:26 · Indexed 14 November 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

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.

More from this channel