# Sparsifying sums of norms

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

## Key facts

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

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

- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Sparsifying Suprema of Gaussian Processes](https://mlsanity.com/paper/2411.14664/) (2024)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)

## Abstract (arXiv)

For any norms N1,ldots,Nm on ℝn and N(x) := N1(x)+cdots+Nm(x), we show there is a sparsified norm tildeN(x) = w1 N1(x) + cdots + wm Nm(x) such that |N(x) - tildeN(x)| ≤ ε N(x) for all x ∈ ℝn, where w1,ldots,wm are non-negative weights, of which only O(ε-2 n log(n/ε) (log n)2.5 ) are non-zero. Additionally, if N is poly(n)-equivalent to the Euclidean norm on ℝn, then such weights can be found with high probability in time O(m (log n)O(1) + poly(n)) T, where T is the time required to evaluate a norm Ni. This immediately yields analogous statements for sparsifying sums of symmetric submodular functions. More generally, we show how to sparsify sums of pth powers of norms when the sum is p-uniformly smooth.