Lower Bounds for Sparse Oblivious Subspace Embeddings

Abstract

An oblivious subspace embedding (OSE), characterized by parameters $m,n,d,\epsilon ,\delta$, is a random matrix $\Pi \in {\mathbb{R}}^{m\times n}$ such that for any $d$-dimensional subspace $T\subseteq {\mathbb{R}}^n$, ${\mathrm{Pr}}_{\Pi }[\forall x\in T,(1-\epsilon )\Vert x{\Vert }_2\le \Vert \Pi x{\Vert }_2\le (1+\epsilon )\Vert x{\Vert }_2]\ge 1-\delta$. For $\epsilon$ and $\delta$ at most a small constant, we show that any OSE with one nonzero entry in each column must satisfy that $m=\Omega (d^2/({\epsilon }^2\delta ))$, establishing the optimality of the classical Count-Sketch matrix. When an OSE has $1/(9\epsilon )$ nonzero entries in each column, we show it must hold that $m=\Omega ({\epsilon }^{O(\delta )}{d}^2)$, improving on the previous $\Omega ({\epsilon }^2{d}^2)$ lower bound due to Nelson and Nguyen (ICALP 2014).