Lower Bounds for Sparse Oblivious Subspace Embeddings

2021/12/21 by Yi Li, Li, Yi, Mingmou Liu +1 · 1 citation
Computer Science · Mathematics · #68R12 #Computational Geometry (cs.CG) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.1 #F.2.3 #FOS: Computer and information sciences #G.2 #Privacy-Preserving Technologies in Data #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.2112.10987

openalex publication_date 2021/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An oblivious subspace embedding (OSE), characterized by parameters m,n,d,ε,δ, is a random matrix Π∈ ℝ^{m× n} such that for any d-dimensional subspace T⊆ ℝⁿ, Pr_Π[∀ x∈ T, (1-ε)‖x‖₂ ≤ ‖Πx‖₂≤ (1+ε)‖x‖₂] ≥ 1-δ. For ε and δ at most a small constant, we show that any OSE with one nonzero entry in each column must satisfy that m = Ω(d²/(ε²δ)), 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 = Ω(ε^O(δ) d²), improving on the previous Ω(ε² d²) lower bound due to Nelson and Nguyen (ICALP 2014).

Cited by

• On the Adversarial Robustness of Online Importance Sampling

Related

• Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings
• Lower bounds for oblivious subspace embeddings
• Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
• Tight Bounds for ℓ_p Oblivious Subspace Embeddings
• Optimal Embedding Dimension for Sparse Subspace Embeddings