Spectral sparsification

Abstract

We survey recent literature focused on the following spectral sparsification question: Given an integer n and > 0, does there exist a function N(n; ) such that for every collection of C1; : : : ;Cm of n n real symmetric positive semidefinite matrices whose sum is the identity, there exists a weighted subset of size N(n; ) whose sum has eigenvalues lying between 1 and 1 + ? We present the algorithms for solving this problem given in [4, 8, 10]. These algorithms obtain N(n; ) = O(n= 2), which is optimal up to constant factors, through use of the barrier method, a proof technique involving potential functions which control the locations of the eigenvalues of a matrix under certain matrix updates. We then survey the applications of this sparsification result and its proof techniques to graph sparsification [4, 10], low-rank matrix approximation [8], and estimating the covariance of certain distributions of random matrices [32, 26]. We end our survey by examining a multivariate generalization of the barrier method used in Marcus, Spielman, and Srivastava’s recent proof [19] of the Kadison-Singer conjecture.