{"ID":2883862,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.08169","arxiv_id":"2508.08169","title":"Sparsifying Sums of Positive Semidefinite Matrices","abstract":"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\\} \\subset \\mathbb{R}^{n \\times n}$, given any subset $T \\subseteq [r]$, our goal is to find sparse weights $μ\\in \\mathbb{R}_{\\geq 0}^r$ such that $(1 - ε) \\sum_{i \\in T} A_i \\preceq \\sum_{i \\in T} μ_i A_i \\preceq (1 + ε) \\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(ε^{-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 $ε\u003c 0.99$. As the main application of our framework, we prove that any Cayley graph can be sparsified to $O(ε^{-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$.","short_abstract":"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\\} \\subset \\mathbb{R}^{n \\times n}$, given any subset $T \\subseteq [r]$, our goal is to find sparse weights $μ\\in \\mathbb{R}_...","url_abs":"https://arxiv.org/abs/2508.08169","url_pdf":"https://arxiv.org/pdf/2508.08169v2","authors":"[\"Arpon Basu\",\"Pravesh K. Kothari\",\"Yang P. Liu\",\"Raghu Meka\"]","published":"2025-08-11T16:45:44Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}