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 \(\mathcal{A}=\{A_1,A_2,\ldots,A_r\}\subseteq \mathbb{R}^{n\times n}\), given any subset \(T\subseteq [r]\), our goal is to find sparse weights \(\mu_i\in\mathbb{R}_{\ge 0}\) such that \((1-\varepsilon)\sum_{i\in T} A_i \;\preceq\; \sum_{i\in T} \mu_i A_i \;\preceq\; (1+\varepsilon)\sum_{i\in T} A_i\). This generalizes spectral sparsification of graphs which corresponds to \(\mathcal{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., \(\mathbb{F}_2^n\)). 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 \(\mathcal{A}\)) theory of PSD matrix sparsification based on a new parameter \(N^*(\mathcal{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(\varepsilon^{-2} N^*(\mathcal{A}) (\log n) (\log r))\) matrices and is constructible in randomized polynomial time. We also show that we need \(N^*(\mathcal{A})\) elements to sparsify for any \(\varepsilon \lt 0.99\). As the main application of our framework, we prove that any Cayley graph can be sparsified to \(O(\varepsilon^{-2}\log^4 N)\) generators. Previously, a non-trivial bound on Cayley sparsifiers was known only in the case when the group is \(\mathbb{F}_2^n\).