# Lower Bounds for Sparse Oblivious Subspace Embeddings

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Dec 2021.

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

- [Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity](https://mlsanity.com/paper/2411.08773/) (2024)
- [Sparse Dimensionality Reduction Revisited](https://mlsanity.com/paper/2302.06165/) (2023)

## Abstract (arXiv)

An oblivious subspace embedding (OSE), characterized by parameters m,n,d,ε,δ, is a random matrix Pi∈ ℝm× n such that for any d-dimensional subspace Tsubseteq ℝn, Pr_Pi[forall x∈ T, (1-ε)|x|2 ≤ |Pi x|2≤ (1+ε)|x|2] ≥ 1-δ. For ε and δ at most a small constant, we show that any OSE with one nonzero entry in each column must satisfy that m = Omega(d2/(ε2δ)), establishing the optimality of the classical Count-Sketch matrix. When an OSE has 1/(9ε) nonzero entries in each column, we show it must hold that m = Omega(εO(δ) d2), improving on the previous Omega(ε2 d2) lower bound due to Nelson and Nguyen (ICALP 2014).