Lower bounds for oblivious subspace embeddings

Introduction

A subspace embedding for some $\varepsilon\in(0,1/3)$ and linear subspace $W$ is a matrix $\Pi$ satisfying

A simple argument then shows that if one instead computes

A recent line of work sought to improve the $O(nd\log n)$ term above to a quantity that depends only on the sparsity of the matrix $A$ as opposed to its ambient dimension. The works give an OSE with $m=O(d^{2}/\varepsilon^{2})$ where every $\Pi$ in the support of the OSE has only $s=1$ non-zero entry per column. The work also showed how to achieve $m=O(d^{1+\gamma}/\varepsilon^{2}),s=\poly(1/\gamma)/\varepsilon$ for any constant $\gamma>0$. Using these OSE’s together with other optimizations (for details see the reductions in ), these works imply approximate regression algorithms running in time $O(\nnz(A)+(d^{3}\log d)/\varepsilon^{2})$ (the $s=1$ case), or $O_{\gamma}(\nnz(A)/\varepsilon+d^{\omega+\gamma}/\varepsilon^{2})$ or $O_{\gamma}((\nnz(A)+d^{2})\log(1/\varepsilon)+d^{\omega+\gamma})$ (the case of larger $s$). Interestingly the algorithm which yields the last bound only requires an OSE with distortion $(1+\varepsilon_{0})$ for constant $\varepsilon_{0}$, while still approximately the least squares optimum up to $1+\varepsilon$.

As seen above we now have several upper bounds, though our understanding of lower bounds for the OSE problem is lacking. Any subspace embedding, and thus any OSE, must have $m\geq d$ since otherwise some non-zero vector in the subspace will be in the kernel of $\Pi$ and thus not have its norm preserved. Furthermore, it quite readily follows from the works that any OSE must have $m=\Omega(\min\{n,\log(d/\delta)/\varepsilon^{2}\})$ (see Corollary 5). Thus the best known lower bound to date is $m=\Omega(\min\{n,d+\varepsilon^{-2}\log(d/\delta)\})$, while the best upper bound is $m=O(\min\{n,(d+\log(1/\delta))/\varepsilon^{2}\})$ (the OSE supported only on the $n\times n$ identity matrix is indeed an OSE with $\varepsilon=\delta=0$). We remark that although some problems can make use of OSE’s with distortion $1+\varepsilon_{0}$ for some constant $\varepsilon_{0}$ to achieve $(1+\varepsilon)$-approximation to the final problem, this is not always true (e.g. no such reduction is known for approximating leverage scores). Thus it is important to understand the required dependence on $\varepsilon$.

We show that for any $\varepsilon,\delta\in(0,1/3)$, any OSE with distortion $1+\varepsilon$ and error probability $\delta$ must have $m=\Omega(\min\{n,(d+\log(1/\delta))/\varepsilon^{2}\})$, which is optimal.

We also make progress in understanding the tradeoff between $m$ and $s$. The work observed via a simple reduction to nonuniform balls and bins that any OSE with $s=1$ must have $m=\Omega(d^{2})$. Also recall the upper bound of of $m=O(d^{1+\gamma}/\varepsilon^{2}),s=\poly(1/\gamma)/\varepsilon$ for any constant $\gamma>0$.

Our contribution II:

We show that for $\delta$ a fixed constant and $n>100d^{2}$, any OSE with $m=o(\varepsilon^{2}d^{2})$ must have $s=\Omega(1/\varepsilon)$. Thus a phase transition exists between sparsity $s=1$ and super-constant sparsity somewhere around $m$ being $d^{2}$. We also show that for $m<d^{1+\gamma}$ and $\gamma\in((10\log\log d)/(\alpha\log d),\alpha/4)$ and $2/(\varepsilon\gamma)<d^{1-\alpha}$, for any constant $\alpha>0$, it must hold that $s=\Omega(\alpha/(\varepsilon\gamma))$. Thus the $s=\poly(1/\gamma)/\varepsilon$ dependence of is correct (although our lower bound requires $m<d^{1+\gamma}$ as opposed to $m<d^{1+\gamma}/\varepsilon^{2}$).

Our proof in the first contribution follows Yao’s minimax principle combined with concentration arguments and Cauchy’s interlacing theorem. Our proof in the second contribution uses a bound for nonuniform balls and bins and the simple fact that for any distribution over unit vectors, two i.i.d. samples are not negatively correlated in expectation.

1 Notation

Dimension lower bound

Let $U\in O^{n\times d}$ be such that the columns of $U$ form an o.n. basis for a $d$-dimensional linear subspace $W$. Then the condition in Eq. (1) is equivalent to all singular values of $\Pi U$ lying in the interval $[1-\varepsilon,1+\varepsilon]$. Let $\kappa(A)$ denote the condition number of matrix $A$, i.e. its largest singular value divided by its smallest singular value, so that for any such $U$ an OSE has $\kappa(\Pi U)\leq 1+\varepsilon$ with probability $1-\delta$ over the randomness of $\Pi$. Thus $\mathcal{D}$ being an OSE implies the condition

We now show a lower bound for $m$ in any distribution $\mathcal{D}$ satisfying Eq. (2) with $\delta<1/3$. Our proof will use a couple lemmas. The first is quite similar to the Johnson-Lindenstrauss lemma itself. Without the appearance of the matrix $D$, it would follow from the the analyses in using Gaussian symmetry.

Let the columns of $U\in O^{n\times m}$ span $E$, and let $u_{i}$ denote the $i$th row of $U$. Let the singular values of $D$ be $\sigma_{1}^{2},\ldots,\sigma_{n}^{2}$. The random unit vector $u$ can be generated as $g/\|g\|$ for a multivariate Gaussian $g$ with identity covariance matrix. Then

and $\|DUU^{T}D\|\leq\|D\|^{2}\cdot\|UU^{T}\|=\sigma_{max}^{2}$. Therefore by the Hanson-Wright inequality,

Similarly $\E\|g\|^{2}=n$ and $\|g\|$ is also the product of a matrix with orthonormal columns (the identity matrix), a diagonal matrix with $\sigma_{min}=\sigma_{max}=1$ (the identity matrix), and a multivariate gaussian. The analysis above thus implies

Therefore with probability $1-C(e^{-\Omega(\varepsilon^{2}n)}+e^{-\Omega(\varepsilon^{2}m)})$ for some constant $C>0$,

We also need the following lemma, which is a special case of Cauchy’s interlacing theorem.

Lastly, we need the following theorem and corollary, which follows from . A similar conclusion can be obtained using , but requiring the assumption that $d<n^{1-\gamma}$ for some constant $\gamma>0$.

Then $m\gtrsim\min\left\{n,\varepsilon^{-2}\log(t/\delta)\right\}$.

The proof uses Yao’s minimax principle. That is, let $\mathcal{U}$ be an arbitrary distribution over $t$-tuples of vectors in $S^{n-1}$. Then

The work [9, Theorem 9] gave a particular distribution $\mathcal{U}_{hard}$ for the case $t=1$ so that no $\Pi_{0}$ can satisfy Eq. (5) unless $m\gtrsim\min\{n,\varepsilon^{-2}\log(1/\delta)\}$. In particular, it showed that the left hand side of Eq. (5) is at most $1-e^{-O(\varepsilon^{2}m+1)}$ as long as $m\leq n/2$ in the case $t=1$. For larger $t$, we simply let the hard distribution be $\mathcal{U}_{hard}^{\otimes t}$, i.e. the $t$-fold product distribution of $\mathcal{U}_{hard}$. Then the left hand side of Eq. (5) is at most $(1-e^{-C(\varepsilon^{2}m+1)})^{t}$. Let $\delta^{\prime}=e^{-C(\varepsilon^{2}m+1)}$. Thus $\mathcal{D}$ cannot satisfy the property in the hypothesis of the lemma if $(1-\delta^{\prime})^{t}<1-\delta$. We have $(1-\delta^{\prime})^{t}\leq e^{-t\delta^{\prime}}$, and furthermore $e^{-x}=1-\Theta(x)$ for $0<x<1/2$. Thus we must have $t\delta^{\prime}=O(\delta)$, i.e. $e^{-C(\varepsilon^{2}m+1)}=\delta^{\prime}=O(\delta/t)$. Rerranging terms proves the theorem. ∎

Now we prove the main theorem of this section.

Let $\mathcal{D}$ be any OSE with $\varepsilon,\delta<1/3$. Then $m=\Omega(\min\{n,d/\varepsilon^{2}\})$.

We assume $d/\varepsilon^{2}\leq cn$ for some constant $c>0$. Our proof uses Yao’s minimax principle. Thus we must construct a distribution $\mathcal{U}_{hard}$ such that

Let $\Pi_{0}=LDW^{T}$ be the singular value decomposition (SVD) of $\Pi_{0}$, i.e. $L\in O^{m\times n},W\in O^{n\times n}$, and $D$ is $n\times n$ with $D_{i,i}\geq 0$ for all $1\leq i\leq m$, and all other entries of $D$ are $0$. Note that $W^{T}U$ is distributed identically as $U$, which is identically distributed as $W^{\prime}U$ where $W^{\prime}$ is an $n\times n$ block diagonal matrix with two blocks. The upper-left block of $W^{\prime}$ is a random rotation $M\in O^{m\times m}$ according to Haar measure. The bottom-right block of $W^{\prime}$ is the $(n-m)\times(n-m)$ identity matrix. Thus it is equivalent to analyze the singular values of the matrix $LDW^{\prime}U$. Also note that left multiplication by $L$ does not alter singular values, and the singular values of $DW^{\prime}U$ and $D^{\prime}MA^{T}U$ are identical, where $A$ is the $n\times m$ matrix whose columns are $e_{1},\ldots,e_{m}$. Also $D^{\prime}$ is an $m\times m$ diagonal matrix with $D^{\prime}_{i,i}=D_{i,i}$. Thus we wish to show that if $m$ is sufficiently small, then

Henceforth in this proof we assume for the sake of contradiction that $m\leq c\cdot\min\{d/\varepsilon^{2},n\}$ for some small positive constant $c>0$. Also note that we may assume by Corollary 5 that $m=\Omega(\min\{n,\varepsilon^{-2}\log(d/\delta)\})$.

Assume that with probability strictly larger than $2/3$ over the choice of $U$, we can find unit vectors $z_{1},z_{2}$ so that $\|A^{T}Uz_{1}\|/\|A^{T}Uz_{2}\|>1+\varepsilon$. Now suppose we have such $z_{1},z_{2}$. Define $y_{1}=A^{T}Uz_{1}/\|A^{T}Uz_{1}\|,y_{2}=A^{T}Uz_{2}/\|A^{T}Uz_{2}\|$. Then a random $M\in O^{m\times m}$ has the same distribution as $M^{\prime}T$, where $M^{\prime}$ is i.i.d. as $M$, and $T$ can be any distribution over $O^{m\times m}$, so we write $M=M^{\prime}T$. $T$ may even depend on $U$, since $M^{\prime}U$ will then still be independent of $U$ and a random rotation (according to Haar measure). Let $T$ be the $m\times m$ identity matrix with probability $1/2$, and $R_{y_{1},y_{2}}$ with probability $1/2$ where $R_{y_{1},y_{2}}$ is the reflection across the bisector of $y_{1},y_{2}$ in the plane containing these two vectors, so that $R_{y_{1},y_{2}}y_{1}=y_{2},R_{y_{1},y_{2}}y_{2}=y_{1}$. Now note that for any fixed choice of $M^{\prime}$ it must be the case that $\|D^{\prime}M^{\prime}y_{1}\|\geq\|D^{\prime}M^{\prime}y_{2}\|$ or $\|D^{\prime}M^{\prime}y_{2}\|\geq\|D^{\prime}M^{\prime}y_{1}\|$. Thus $\|D^{\prime}M^{\prime}Ty_{1}\|\geq\|D^{\prime}M^{\prime}Ty_{2}\|$ occurs with probability $1/2$ over $T$, and the reverse inequality occurs with probability $1/2$. Thus for this fixed $U$ for which we found such $z_{1},z_{2}$, over the randomness of $M^{\prime},T$ we have $\kappa(D^{\prime}MA^{T}U)\geq\|D^{\prime}MA^{T}Uz_{1}\|/\|D^{\prime}MA^{T}Uz_{2}\|$ is greater than $1+\varepsilon$ with probability at least $1/2$. Since such $z_{1},z_{2}$ exist with probability larger than $2/3$ over chioce of $U$, we have established Eq. (7). It just remains to establish the existence of such $z_{1},z_{2}$.

Also note $E^{T}u/\|E^{T}u\|$ is uniformly random in $S^{m-1}$, and also $B^{T}C$ has orthonormal rows since $B^{T}CC^{T}B=B^{T}B=I$, and thus again by Lemma 2 with $E$ being the row space of $B^{T}C$ and $D=\Lambda$, we have $\|B^{T}C\Lambda E^{T}u\|=\Theta(\|E^{T}u\|\cdot\sqrt{d/m})=\Theta(\sqrt{d/n})$ with probability $1-e^{-\Omega(d)}$.

For $c$ small, the above is bigger than $(1+\varepsilon)^{2}(1+C_{2}\varepsilon)^{2}m/n$ as desired.

Case 2 (c​d/ε≤m≤c​d/ε2cd/\varepsilon\leq m\leq cd/\varepsilon^{2}):

Sparsity Lower Bound

If $n\geq 100d^{2}$ and $m\leq\varepsilon^{2}d(d-1)/32$, then $s=\Omega(1/\varepsilon)$.

Let $\mathcal{P}$ be a distribution over vectors of norm at most 1 and $u$ and $v$ be independent samples from $\mathcal{P}$. Then $\E\left\langle u,v\right\rangle\geq 0$.

Let $\delta=\E\left\langle u,v\right\rangle$. Assume for the sake of contradiction that $\delta<0$. Take $t$ samples $u_{1},\ldots,u_{t}$ from $\mathcal{P}$. By linearity of expectation, we have $0\leq\E(\sum_{i}u_{i})^{2}\leq t+t(t-1)\delta$. This is a contradiction because the RHS tends to $-\infty$ as $t\rightarrow\infty$. ∎

Let $X$ be a random variable bounded by $1$ and $\E X\geq 0$. Then for any $0<\delta<1$, we have $\Pr(X\leq-\delta)\leq 1/(1+\delta)$.

We prove the contrapositive. If $\Pr(X\leq-\delta)>1/(1+\delta)$, then

Let $u_{i}$ be the $i$ column of $\Pi U$, $r_{i}$ and $z_{i}$ be the index and the value of the coordinate of the maximum absolute value of $u_{i}$, and $v_{i}$ be $u_{i}$ with the coordinate at position $r_{i}$ removed. Let $p_{2j-1}$(respectively, $p_{2j}$) be the fractions columns of $\Pi$ whose entry of maximum absolute value is on row $j$ and is positive (respectively, negative). Let $C_{i,j}$ be the indicator variable indicating whether $r_{i}=r_{j}$ and $z_{i}$ and $z_{j}$ are of the same sign. Let $E=\E C_{1,2}=\sum_{i=1}^{2m}p_{i}^{2}$. Let $C=\sum_{i<j\leq d}C_{i,j}$. We have

If $i_{1},i_{2},i_{3},i_{4}$ are distinct then $C_{i_{1},i_{2}},C_{i_{3},i_{4}}$ are independent. If the pairs $(i_{1},i_{2})$ and $(i_{3},i_{4})$ share one index then $\Pr(C_{i_{1},i_{2}}=1\wedge C_{i_{3},i_{4}}=1)=\sum_{i}p_{i}^{3}$ and $\Pr(C_{i_{1},i_{2}}=1\wedge C_{i_{3},i_{4}}=0)=\sum_{i}p_{i}^{2}(1-p_{i})$. Thus for this case,

Thus, with probability at least $1-O(\varepsilon)$, we have $C\geq 4\varepsilon^{-2}$. We now argue that there exist $1/\varepsilon$ pairwise-disjoint pairs $(a_{i},b_{i})$ such that $r_{a_{i}}=r_{b_{i}}$ and $z_{a_{i}}$ and $z_{b_{i}}$ are of the same sign. Indeed, let $d_{2j-1}$ (respectively, $d_{2j}$) be the number of $u_{i}$’s with $r_{i}=j$ and $z_{i}$ being positive (respectively, negative). Wlog, assume that $d_{1},\ldots,d_{t}$ are all the $d_{i}$’s that are at least 2. We can always get at least $\sum_{i=1}^{t}(d_{i}-1)/2$ disjoint pairs. We have

For each pair $(a_{i},b_{i})$, by Lemmas 8 and 9, $\Pr[\langle v_{a_{i}},v_{b_{i}}\rangle\leq-\varepsilon]\leq\frac{1}{1+\varepsilon}$ and these events for different $i$’s are independent so with probability at least $1-(1+\varepsilon)^{-1/\varepsilon}\geq 1-e^{\varepsilon/2-1}$, there exists some $i$ such that $\langle v_{a_{i}},v_{b_{i}}\rangle>-\varepsilon$. For $\Pi$ to be a subspace embedding for the column span of $U$, it must be the case, for all $i$, that $\|u_{i}\|=\|\Pi Ue_{i}\|\geq 1-\varepsilon$. We have $|z_{i}|\geq s^{-1/2}\|u_{i}\|\geq s^{-1/2}(1-\varepsilon)~\forall i$. Therefore, $\langle u_{a_{i}},u_{b_{i}}\rangle\geq s^{-1}(1-\varepsilon)^{2}-\varepsilon$. We have

However, $\|\Pi U\|\leq 1+\varepsilon$ so $s\geq(1-\varepsilon)^{2}/(5\varepsilon)$. ∎

2 Lower bound in terms of mm

For $n\geq 100d^{2}$, $\frac{20\log\log d}{\log d}<\gamma<1/12$ and $\varepsilon=1/2$, if $m\leq d^{1+\gamma}$, then $s=\Omega(1/\gamma)$.

We first prove a standard bound for a certain balls and bins problem. The proof is included for completeness.

Let $\alpha$ be a constant in $(0,1)$. Consider the problem of throwing $d$ balls independently and uniformly at random at $m\leq d^{1+\gamma}$ bins with $\frac{10\log\log d}{\alpha\log d}<\gamma<1/12$. With probability at least $99/100$, at least $d^{1-\alpha}/2$ bins have load at least $\alpha/(2\gamma)$.

Let $X_{i}$ be the indicator r.v. for bin $i$ having $t=\alpha/(2\gamma)$ balls, and $X\mathbin{\stackrel{{\scriptstyle\rm def}}{{=}}}\sum_{i}X_{i}$. Then

Thus, $\E X\geq d^{1-\alpha}$. Because $X_{i}$’s are negatively correlated,

Thus, with probability $1-4d^{\alpha-1}$, there exist $d^{1-\alpha}/2$ bins with at least $\alpha/(2\gamma)$ balls. ∎

Next we prove a slightly weaker bound for the non-uniform version of the problem.

Consider the problem of throwing $d$ balls independently at $m\leq d^{1+\gamma}$ bins. In each throw, bin $i$ receives the ball with probability $p_{i}$. With probability at least $99/100$, there exist $d^{1-\alpha}/2$ disjoint groups of balls of size $\alpha/(4\gamma)$ each such that all balls in the same group land in the same bin.

The following procedure is inspired by the alias method, a constant time algorithm for sampling from a given discrete distribution (see e.g. ). We define a set of $m$ virtual bins with equal probabilities of receiving a ball as follows. The following invariant is maintained: in the $i$th step, there are $m-i+1$ values $p_{1},\ldots,p_{m-i+1}$ satisfying $\sum_{j}p_{j}=(m-i+1)/m$. In the $i$th step, we create the $i$th virtual bin as follows. Pick the smallest $p_{j}$ and the largest $p_{k}$. Notice that $p_{j}\leq 1/m\leq p_{k}$. Form a new virtual bin from $p_{j}$ and $1/m-p_{j}$ probability mass from $p_{k}$. Remove $p_{j}$ from the collection and replace $p_{k}$ with $p_{k}+p_{j}-1/m$.

By Lemma 11, there exist $d^{1-\alpha}/2$ virtual bins receiving at least $\alpha/(2\gamma)$ balls. Since each virtual bin receives probability mass from at most 2 bins, there exist $d^{1-\alpha}/2$ groups of balls of size at least $\alpha/(4\gamma)$ such that all balls in the same group land in the same bin. ∎

Finally we use the above bound for balls and bins to prove the lower bound. Let $p_{i}$ be the fraction of columns of $\Pi$ whose coordinate of largest absolute value is on row $i$. By Lemma 12, there exist a row $i$ and $\alpha/(4\gamma)$ columns of $\Pi U$ such that the coordinates of maximum absolute value of those columns all lie on row $i$. $\Pi$ is a subspace embedding for the column span of $U$ only if $\|\Pi Ue_{j}\|\in[1/2,3/2]~\forall j$. The columns of $\Pi U$ are $s$ sparse so for any column of $\Pi U$, the largest absolute value of its coordinates is at least $s^{-1/2}/2$. Therefore, $\|e_{i}^{T}\Pi U\|^{2}\geq\alpha/(16\gamma s)$. Because $\|\Pi U\|\leq 3/2$, it must be the case that $s=\Omega(\alpha/\gamma)$.

3 Combining both types of lower bounds

For $n\geq 100d^{2}$, $m<d^{1+\gamma}$, $\alpha\in(0,1)$, $\frac{10\log\log d}{\alpha\log d}<\gamma<\alpha/4$, $0<\varepsilon<1/2$, and $2/(\varepsilon\gamma)<d^{1-\alpha}$, we must have $s=\Omega(\alpha/(\varepsilon\gamma))$.

Let $u_{i}$ be the $i$ column of $\Pi U$, $r_{i}$ and $z_{i}$ be the index and the value of the coordinate of the maximum absolute value of $u_{i}$, and $v_{i}$ be $u_{i}$ with the coordinate at position $r_{i}$ removed. Fix $t=\alpha/(4\gamma)$. Let $p_{2i-1}$ (respectively, $p_{2i}$) be the fractions of columns of $\Pi$ whose largest entry is on row $i$ and positive (respectively, negative). By Lemma 12, there exist $d^{1-\alpha}/2$ disjoint groups of $t$ columns of $\Pi U$ such that the columns in the same group have the entries with maximum absolute values on the same row. Consider one such group $G=\{u_{i_{1}},\ldots,u_{i_{t}}\}$. By Lemma 8 and linearity of expectation, $\E\sum_{u_{i},u_{j}\in G,i\neq j}\left\langle v_{i},v_{j}\right\rangle\geq 0$. Furthermore, $\sum_{u_{i},u_{j}\in G,i\neq j}\langle v_{i},v_{j}\rangle\leq t(t-1)$. Thus, by Lemma 9, $\Pr(\sum_{u_{i},u_{j}\in G,i\neq j}\left\langle v_{i},v_{j}\right\rangle\leq-t(t-1)(\varepsilon\gamma))\leq\frac{1}{1+\varepsilon\gamma}$. This event happens independently for different groups, so with probability at least $1-(1+\varepsilon\gamma)^{-1/(\varepsilon\gamma)}\geq 1-e^{\varepsilon\gamma/2-1}$, there exists a group $G$ such that

The matrix $\Pi$ is a subspace embedding for the column span of $U$ only if for all $i$, we have $\|u_{i}\|=|\Pi Ue_{i}\|\geq(1-\varepsilon)$. We have $|z_{i}|\geq s^{-1/2}\|u_{i}\|\geq s^{-1/2}(1-\varepsilon)$. Thus, $\sum_{u_{i},u_{j}\in G,i\neq j}\langle u_{i},u_{j}\rangle\geq t(t-1)((1-\varepsilon)^{2}s^{-1}-\varepsilon\gamma)$. We have

Because $\|\Pi U\|\leq 1+\varepsilon$, we must have $s\geq\frac{(\alpha/\gamma-4)(1-\varepsilon)^{2}}{(16+\alpha)\varepsilon}$. ∎

References