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.
