Lower Bounds for Sparse Oblivious Subspace Embeddings

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).