Sparsifying Sums of Positive Semidefinite Matrices
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911349317042176 |
|---|---|
| author | Basu, Arpon Kothari, Pravesh K. Liu, Yang P. Meka, Raghu |
| author_facet | Basu, Arpon Kothari, Pravesh K. Liu, Yang P. Meka, Raghu |
| contents | 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 $ε< 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08169 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sparsifying Sums of Positive Semidefinite Matrices Basu, Arpon Kothari, Pravesh K. Liu, Yang P. Meka, Raghu Data Structures and Algorithms 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 $ε< 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$. |
| title | Sparsifying Sums of Positive Semidefinite Matrices |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.08169 |