Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings

An oblivious subspace embedding (OSE), characterized by parameters m,n,d ,∈,δ, is a random matrix ∏∈ ℝ m x n such that for any d -dimensional subspace T ⊆ ⊏ n , Pr ∏[ [∀ x ∈ T , (1-∈)|| x || 2 ≤(1+∈)|| x || 2 ] ≥(1-δ). When an OSE has s ≤ 1/2.001≬ nonzero entries in each column, we show it must hold that m = Ω( d 2 /(∈ 2 s 1+O(δ )), which is the first lower bound with multiplicative factors of d 2 and 1/∈, improving on the previous Ω( d 2 / s O(δ) ) lower bound due to Li and Liu (PODS 2022). When an OSE has s =Ω(log(1/∈)/∈) nonzero entries in each column, we show it must hold that m = Ω(( d /∈)1+1/4.001∈ s / s O(δ) ), which is the first lower bound with multiplicative factors of d and 1/𘆘, improving on the previous Ω ( d 1+1/(16∈ s +4) ) lower bound due to Nelson and Nguyên (ICALP 2014). This second result is a special case of a more general trade-off among d ,∈, s ,δ and m .