mlsanityData to 14 Oct 2026

Lower bounds for oblivious subspace embeddings

arXiv 1308.3280 ↗First posted 15 Aug 2013cs.DM cs.CG math.PRcited by 11

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 2; 2023: 5; 2024: 2; 2025: 1.

11 papers.

  1. 2023Optimal Embedding Dimension for Sparse Subspace Embeddingscited by 11
  2. 2023Optimal Sketching Bounds for Sparse Linear Regressioncited by 6
  3. 2021Hashing embeddings of optimal dimension, with applications to linear least squarescited by 4
  4. 2022Sketching Algorithms and Lower Bounds for Ridge Regressioncited by 4
  5. 2024Optimal Oblivious Subspace Embeddings with Near-optimal Sparsitycited by 4
  6. 2023Sparse Dimensionality Reduction Revisitedcited by 1
  7. 2022Johnson-Lindenstrauss embeddings for noisy vectors -- taking advantage of the noisecited by 0
  8. 2023Learning the Positions in CountSketchcited by 0
  9. 2023Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streamingcited by 0
  10. 2024The Space Complexity of Approximating Logistic Losscited by 0
  11. 2025Unified Linear Parametric Map Modeling and Perception-aware Trajectory Planning for Mobile Roboticscited by 0