# Lower bounds for oblivious subspace embeddings

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2013.

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

- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Hashing embeddings of optimal dimension, with applications to linear least squares](https://mlsanity.com/paper/2105.11815/) (2021)
- [Sketching Algorithms and Lower Bounds for Ridge Regression](https://mlsanity.com/paper/2204.06653/) (2022)
- [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)
- [Johnson-Lindenstrauss embeddings for noisy vectors -- taking advantage of the noise](https://mlsanity.com/paper/2209.01006/) (2022)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2306.06611/) (2023)
- [Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming](https://mlsanity.com/paper/2310.19068/) (2023)
- [The Space Complexity of Approximating Logistic Loss](https://mlsanity.com/paper/2412.02639/) (2024)
- [Unified Linear Parametric Map Modeling and Perception-aware Trajectory Planning for Mobile Robotics](https://mlsanity.com/paper/2507.09340/) (2025)

## Abstract (arXiv)

An oblivious subspace embedding (OSE) for some eps, delta in (0,1/3) and d <= m <= n is a distribution D over R^{m x n} such that for any linear subspace W of R^n of dimension d, Pr_{Pi ~ D}(for all x in W, (1-eps) |x|_2 <= |Pi x|_2 <= (1+eps)|x|_2) >= 1 - delta. We prove that any OSE with delta < 1/3 must have m = Omega((d + log(1/delta))/eps^2), which is optimal. Furthermore, if every Pi in the support of D is sparse, having at most s non-zero entries per column, then we show tradeoff lower bounds between m and s.