2014/01/01 by Joshua Batson, Daniel A. Spielman, Nikhil Srivastava · 4 citations
Mathematics · Engineering · Computer Science · #Graph theory and applications #Sparse and Compressive Sensing Techniques #Matrix Theory and Algorithms
paper · doi:10.1137/130949117
A sparsifier of a graph is a sparse graph that approximates it. A spectral sparsifier is one that approximates it spectrally, which means that their Laplacian matrices have similar quadratic forms. We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. In particular, we prove that for every ε ∈ (0,1) and every undirected, weighted graph G = (V,E,w) on n vertices, there exists a weighted graph H=(V,F,w) with at most \lceil (n-1)/ε2\rceil edges such that for every x ∈ \RV, (1-ε)2 ⋅ xT LG x ≤ xT LH x ≤ (1+ε)2 ⋅ xT LG x, where LG and LH are the Laplacian matrices of G and H, respectively. We give an elementary deterministic polynomial time algorithm for constructing H. This result is a special case of a significantly more general theorem which provides sparse approximations of general positive semidefinite matrices: given any real matrix Bn× m and ε∈ (0,1), there is a nonnegative diagonal matrix Sm× m with at most \lceil n/ε2\rceil nonzero entries such that (1-ε)2 BBT \preceq BSBT \preceq (1+ε)2 BBT.