# Beyond Worst-Case Dimensionality Reduction for Sparse Vectors

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 55 references that are in the map.
- First posted on arXiv 27 Feb 2025.

## Builds on (most cited first, 23 of 23)

- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction](https://mlsanity.com/paper/1411.2404/) (2014)
- [The Fine-Grained Hardness of Sparse Linear Regression](https://mlsanity.com/paper/2106.03131/) (2021)
- [Optimal terminal dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1810.09250/) (2018)
- [Approximate Sparse Linear Regression](https://mlsanity.com/paper/1609.08739/) (2016)
- [Hardness and Algorithms for Robust and Sparse Optimization](https://mlsanity.com/paper/2206.14354/) (2022)
- [Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions](https://mlsanity.com/paper/1811.03591/) (2018)
- [Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering](https://mlsanity.com/paper/2107.01804/) (2021)
- [Terminal Embeddings in Sublinear Time](https://mlsanity.com/paper/2110.08691/) (2021)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Terminal Embeddings](https://mlsanity.com/paper/1603.02321/) (2016)
- [Streaming Euclidean Max-Cut: Dimension vs Data Reduction](https://mlsanity.com/paper/2211.05293/) (2022)
- [Moderate Dimension Reduction for k-Center Clustering](https://mlsanity.com/paper/2312.01391/) (2023)
- [Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution](https://mlsanity.com/paper/2105.05984/) (2021)
- [Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution](https://mlsanity.com/paper/2107.07625/) (2021)
- [Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More](https://mlsanity.com/paper/2403.20326/) (2024)

## Abstract (arXiv)

We study beyond worst-case dimensionality reduction for s-sparse vectors. Our work is divided into two parts, each focusing on a different facet of beyond worst-case analysis: We first consider average-case guarantees. A folklore upper bound based on the birthday-paradox states: For any collection X of s-sparse vectors in ℝd, there exists a linear map to ℝO(s2) which exactly preserves the norm of 99% of the vectors in X in any ℓp norm (as opposed to the usual setting where guarantees hold for all vectors). We give lower bounds showing that this is indeed optimal in many settings: any oblivious linear map satisfying similar average-case guarantees must map to Omega(s2) dimensions. The same lower bound also holds for a wide class of smooth maps, including `encoder-decoder schemes', where we compare the norm of the original vector to that of a smooth function of the embedding. These lower bounds reveal a separation result, as an upper bound of O(s log(d)) is possible if we instead use arbitrary (possibly non-smooth) functions, e.g., via compressed sensing algorithms. Given these lower bounds, we specialize to sparse non-negative vectors. For a dataset X of non-negative s-sparse vectors and any p ≥ 1, we can non-linearly embed X to O(slog(|X|s)/ε2) dimensions while preserving all pairwise distances in ℓp norm up to 1± ε, with no dependence on p. Surprisingly, the non-negativity assumption enables much smaller embeddings than arbitrary sparse vectors, where the best known bounds suffer exponential dependence. Our map also guarantees exact dimensionality reduction for ℓ∞ by embedding into O(slog |X|) dimensions, which is tight. We show that both the non-linearity of f and the non-negativity of X are necessary, and provide downstream algorithmic improvements.