Sparsity-Dimension Trade-Offs for 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$. When an OSE has $s\le 1/2.001\epsilon$ nonzero entries in each column, we show it must hold that $m=\Omega \left(d^2/({\epsilon }^2{s}^{1+O(\delta )})\right)$, which is the first lower bound with multiplicative factors of $d^2$ and $1/\epsilon$, improving on the previous $\Omega \left(d^2/s^{O(\delta )}\right)$ lower bound due to Li and Liu (PODS 2022). When an OSE has $s=\Omega (\log (1/\epsilon )/\epsilon )$ nonzero entries in each column, we show it must hold that $m=\Omega \left((d/\epsilon {)}^{1+1/4.001\epsilon s}/s^{O(\delta )}\right)$, which is the first lower bound with multiplicative factors of $d$ and $1/\epsilon$, improving on the previous $\Omega \left(d^{1+1/(16\epsilon s+4)}\right)$ lower bound due to Nelson and Nguyen (ICALP 2014). This second result is a special case of a more general trade-off among $d,\epsilon ,s,\delta$ and $m$.

arXiv commentMajor update. Now includes a general result of the tradeoff between m and s, improving on [NN14]