# Comparison of Matrix Norm Sparsification

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2022.

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

- [SpaRG: Sparsely Reconstructed Graphs for Generalizable fMRI Analysis](https://mlsanity.com/paper/2410.07201/) (2024)

## Abstract (arXiv)

A well-known approach in the design of efficient algorithms, called matrix sparsification, approximates a matrix A with a sparse matrix A'. Achlioptas and McSherry [2007] initiated a long line of work on spectral-norm sparsification, which aims to guarantee that |A'-A|≤ ε |A| for error parameter ε>0. Various forms of matrix approximation motivate considering this problem with a guarantee according to the Schatten p-norm for general p, which includes the spectral norm as the special case p=∞. We investigate the relation between fixed but different pneq q, that is, whether sparsification in the Schatten p-norm implies (existentially and/or algorithmically) sparsification in the Schatten q-norm with similar sparsity. An affirmative answer could be tremendously useful, as it will identify which value of p to focus on. Our main finding is a surprising contrast between this question and the analogous case of ℓp-norm sparsification for vectors: For vectors, the answer is affirmative for p<q and negative for p>q, but for matrices we answer negatively for almost all sufficiently distinct pneq q. In addition, our explicit constructions may be of independent interest.