Lower bounds for oblivious subspace embeddings

2013/08/15 by Nelson, Jelani, Nguyen, Huy L. · 1 citation
#Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1308.3280

Abstract

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ⁿ of dimension d, Pr_{Pi ~ D}(for all x in W, (1-eps) |x|₂ <= |Pi x|₂ <= (1+eps)|x|₂) >= 1 - delta. We prove that any OSE with delta < 1/3 must have m = Omega((d + log(1/delta))/eps²), 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.

Cited by

• Unified Linear Parametric Map Modeling and Perception-aware Trajectory Planning for Mobile Robotics

Related

• Lower Bounds for Sparse Oblivious Subspace Embeddings
• Tight Bounds for ℓ_p Oblivious Subspace Embeddings
• Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings
• Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace\n embeddings