Lower Bounds for Oblivious Subspace Embeddings

Abstract

An oblivious subspace embedding (OSE) for some (\epsilon),(\delta \in (0,1/3)) and d ≤ m ≤ n is a distribution (\mathcal{D}) over (\mathbb{R}^{m×n}) such that (\underset {\Pi \sim \mathcal{D}} {Pr} (\forall x \in W, (1−\epsilon)|| x ||_2≤ || \Pi x ||_2≤(1+\epsilon)|| x||_2)≥1−\delta) for any linear subspace (W \subset \mathbb{R}^n) of dimension d. We prove any OSE with (\delta < 1/3) has (m = \Omega((d + log(1/\delta))/\epsilon^2)), which is optimal. Furthermore, if every (\Pi) in the support of (\mathcal{D}) is sparse, having at most s non-zero entries per column, we show tradeoff lower bounds between m and s.