Sparsifying Sums of Positive Semidefinite Matrices

In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices A = {A₁, A₂, . . ., A_r} ⊂ ℝ^n×n, given any subset T ⊆ [r], our goal is to find sparse weights µ ∈ ℝ^r_≥0 such that (1 − ε) Σ _i∈T A_i ≼ Σ _i∈T µ_iA_i ≼ (1 + ε) Σ _i∈T A_i. This generalizes spectral sparsification of graphs which corresponds to A being the set of Laplacians of edges. It also captures sparsifying Cayley graphs by choosing a subset of generators. The former has been extensively studied with optimal sparsifiers known. The latter has received attention recently and was solved for a few special groups (e.g., Fⁿ₂ ). Prior work shows any sum of PSD matrices can be sparsified down to O(n) elements. This bound however turns out to be too coarse and in particular yields no non-trivial bound for building Cayley sparsifiers for Cayley graphs. In this work, we develop a new, instance-specific (i.e., specific to a given collection A) theory of PSD matrix sparsification based on a new parameter N^∗(A) which we call connectivity threshold that generalizes the threshold of the number of edges required to make a graph connected. Our main result gives a sparsifier that uses at most O(ε⁻²N^∗(A)(log n)(log r)) matrices and is constructible in randomized polynomial time. We also show that we need N^∗(A) elements to sparsify for any ε < 0.99. As the main application of our framework, we prove that any Cayley graph can be sparsified to O(ε⁻² log⁴ N) generators.