Twice-ramanujan sparsifiers

By Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava. Symposium on the Theory of Computing, 2008

580 citations recorded by the source corpus.

We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every d > 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 ⌈d(n-1)⌉ edges such that for every x ∈ R^V, [x^T L_G x ≤ x^T L_H x ≤ ((d+1+2√d)/(d+1-2√d)) • x^T L_G x] where L_G and L_H are the Laplacian matrices of G and H, respectively. Thus, H approximates G spectrally at least as well as a Ramanujan expander with dn/2 edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing H.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/f1a2ec7363fbdfff3e84a88d2401d1862e3ef146

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. David P. Woodruff
2. Dan Feldman
3. Daniel A. Spielman
4. Nikhil Srivastava
5. Peilin Zhong
6. Shang-Hua Teng
7. Adam W. Marcus
8. Andrew McGregor

In Discrete Mathematics and Combinatorics

1. Adam W. Marcus
2. David P. Woodruff
3. Daniel A. Spielman
4. Roman Vershynin
5. Nikhil Srivastava
6. Garving K. Luli
7. Arie Israel
8. Dan Feldman

In Geometry and Topology

1. David P. Woodruff
2. Daniel A. Spielman
3. Nikhil Srivastava
4. Adam W. Marcus
5. Dan Feldman
6. Roman Vershynin
7. Garving K. Luli
8. Arie Israel

Citations in the corpus

• Sobolev extension by linear operators (2012, methodology): “On the other hand, the remarkable work of BatsonSpielman-Srivastava [1] on “sparsification” gives hope that bounded-depth ξ’s may exist.”
• Learning from untrusted data (2016, background): “Robust mean estimation.”
• Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees (2013, methodology): “The above theorem is a strengthening of the univariate barrier function argument for characteristic polynomials introduced in [2].”
• Optimal principal component analysis in distributed and streaming models (2015, methodology): “[11] J.”
• Graph sparsification by effective resistances (2008, background): “In addition to the graph sparsifiers of [5, 4, 23], there is a large body of work on sparse [3, 2] and low-rank [14, 2, 22, 10, 11] approximations for general matrices.”
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, methodology): “Family 5 uses a variation on the algorithm introduced in [7] and extended in [18] for stable rank.”
• The Marcinkiewicz-Type Discretization Theorems (2017, unknown): “The authors of [1] control the change of the maximal and minimal eigenvalues of a matrix, when they add a rank one matrix of the form wG(x).”
• Interlacing families II: Mixed characteristic polynomials and the Kadison{Singer problem (2013, methodology): “We do this in Section 5 through a multivariate generalization of the barrier function argument of Batson, Spielman, and Srivastava [10].”
• Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems (2006, background): “In particular, Spielman and Srivastava [SS08] construct sparsifiers with c 2 = 1, but these constructions require the solution of linear equations in Laplacian matrices, and so can not be used to help speed up the algorithms in this paper.”
• Introduction to the non-asymptotic analysis of random matrices (2010, methodology): “The argument in [Batson-Spielman-Srivastava] suggests a new method in RMT for the extreme eigenvalues.”
• A unified framework for approximating and clustering data (2011, background): “1 below in time O(nd(2) + d/ε(2)), with high probability, while [4] provide a deterministic construction in O(nd(4)/ε(2)) time.”
• Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, background): “The sparsifiers of [12, 63, 64, 10] are not linear and do not appear to be mergeable.”
• An elementary proof of the restricted invertibility theorem (2009, methodology): “As the latter matrix is obtained from A by the addition of a rank one positive semi-definite matrix, their eigenvalues interlace [1]: λ1 ≥ λ1 ≥ λ2 ≥ · · · ≥ λk ≥ λk+1.”
• Deterministic algorithms for matrix completion (2014, background): “[1] which provide very good guarantees, but are not extremely efficient.”