# Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra

arXiv: https://arxiv.org/abs/2305.05826 · HTML: https://mlsanity.com/paper/2305.05826/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2023.

## Built on by (most cited first, 1 of 1)

- [Faster Spectral Density Estimation and Sparsification in the Nuclear Norm](https://mlsanity.com/paper/2406.07521/) (2024)

## Abstract (arXiv)

Let mathbf S ∈ mathbb Rn × n satisfy |mathbf 1-mathbf S|2≤ε n, where mathbf 1 is the all ones matrix and |·|2 is the spectral norm. It is well-known that there exists such an mathbf S with just O(n/ε2) non-zero entries: we can let mathbf S be the scaled adjacency matrix of a Ramanujan expander graph. We show that such an mathbf S yields a universal sparsifier for any positive semidefinite (PSD) matrix. In particular, for any PSD mathbf A ∈ ℝn× n with entries bounded in magnitude by 1, |mathbf A - mathbf Acircmathbf S|2 ≤ ε n, where circ denotes the entrywise (Hadamard) product. Our techniques also give universal sparsifiers for non-PSD matrices. In this case, letting mathbf S be the scaled adjacency matrix of a Ramanujan graph with tilde O(n/ε4) edges, we have |mathbf A - mathbf A circ mathbf S |2 ≤ ε · max(n,|mathbf A|1), where |mathbf A|1 is the nuclear norm. We show that the above bounds for both PSD and non-PSD matrices are tight up to log factors. Since mathbf A circ mathbf S can be constructed deterministically, our result for PSD matrices derandomizes and improves upon known results for randomized matrix sparsification, which require randomly sampling O(fracn log nε2) entries. We also leverage our results to give the first deterministic algorithms for several problems related to singular value approximation that run in faster than matrix multiplication time. Finally, if mathbf A ∈ -1,0,1n × n is PSD, we show that tilde A with |mathbf A - tilde A|2 ≤ ε n can be obtained by deterministically reading tilde O(n/ε) entries of mathbf A. This improves the 1/ε dependence on our result for general PSD matrices and is near-optimal.