Sparsity Lower Bounds for Dimensionality Reducing Maps

Introduction

The last decade has witnessed a burgeoning interest in algorithms for large-scale data. A common feature in many of these works is the exploitation of data sparsity to achieve algorithmic efficiency, for example to have running times proportional to the actual complexity of the data rather than the dimension of the ambient space it lives in. This approach has found applications in compressed sensing [CT05, Don06], dimension reduction [BOR10, DKS10, KN10, KN12, WDL+09], and numerical linear algebra [CW12, MM12, MP12, NN12]. Given the success of these algorithms, it is important to understand their limitations. Until now, for most of these problems it is not known how far one can reduce the running time on sparse inputs. In this work we make a step towards understanding the performance of algorithms for sparse data and show several tight lower bounds.

In this work we provide three main contributions. We give near-optimal or optimal sparsity lower bounds for Johnson-Lindenstrauss transforms, matrices satisfying the restricted isometry property for use in compressed sensing, and subspace embeddings used in numerical linear algebra. These three contributions are discussed in Section 1.1, Section 1.2, and Section 1.3, respectively.

The following lemma, due to Johnson and Lindenstrauss [JL84], has been used widely in many areas of computer science to reduce data dimension.

Typically one uses the lemma in algorithm design by mapping some instance of a high-dimensional computational geometry problem to a lower dimension. The running time to solve the instance then becomes the time needed for the lower-dimensional problem, plus the time to perform the matrix-vector multiplications $Ax_{i}$; see [Ind01, Vem04] for further discussion. This latter step highlights the importance of having a JL matrix supporting fast matrix-vector multiplication. The original proofs of the JL lemma took $A$ to be a random dense matrix, e.g. with i.i.d. Gaussian, Rademacher, or even subgaussian entries [Ach03, AV06, DG03, FM88, IM98, JL84, Mat08]. The time to compute $Ax$ then becomes $O(m\cdot\|x\|_{0})$, where $x$ has $\|x\|_{0}\leq d$ non-zero entries.

A beautiful work of Ailon and Chazelle [AC09] described a construction of a JL matrix $A$ supporting matrix-vector multiplication in time $O(d\log d+m^{3})$, also with $m=O(\varepsilon^{-2}\log n)$. This was improved to $O(d\log d+m^{2+\gamma})$ [AL09] with the same $m$ for any constant $\gamma>0$, or to $O(d\log d)$ with $m=O(\varepsilon^{-2}\log n\log^{4}d)$ [AL11, KW11]. Thus if $\varepsilon^{-2}\log n\ll\sqrt{d}$ one can obtain nearly-linear $O(d\log d)$ embedding time with the same target dimension $m$ as the original JL lemma, or one can also obtain nearly-linear time for any setting of $\varepsilon,n$ by increasing $m$ slightly by $\polylog d$ factors.

While the previous paragraph may seem to present the end of the story, in fact note that the “nearly-linear” $O(d\log d)$ embedding time is actually much worse than the original $O(m\cdot\|x\|_{0})$ time of dense JL matrices when $\|x\|_{0}$ is very small, i.e. when $x$ is sparse. Indeed, in several applications we expect $x$ to be sparse. Consider the bag of words model in information retrieval: in for example an email spam collaborative filtering system for Yahoo! Mail [WDL+09], each email is treated as a $d$-dimensional vector where $d$ is the size of the lexicon. The $i$th entry of the vector is some weighted count of the number of occurrences of word $i$ (frequent words like “the” should be weighted less heavily). A machine learning algorithm is employed to learn a spam classifier, which involves dot products of email vectors with some learned classifier vector, and JL dimensionality reduction is used to speed up the repeated dot products that are computed during training. Note that in this scenario we expect $x$ to be sparse since most emails do not contain nearly every word in the lexicon. An even starker scenario is the turnstile streaming model, where the vectors $x$ may receive coordinate-wise updates in a data stream. In this case maintaining $Ax$ in a stream given some update of the form “add $v$ to $x_{i}$” requires adding $vAe_{i}$ to the compression $Ax$ stored in memory. Since $\|e_{i}\|=1$, we would not like to spend $O(d\log d)$ per streaming update.

The intuition behind all the works [AC09, AL09, AL11, KW11] to obtain $O(d\log d)$ embedding time was as follows. Picking $A$ to be a scaled sampling matrix (where each row has a $1$ in a random location) gives the correct expectation for $\|Ax\|_{2}^{2}$, but the variance may be too high. Indeed, the variance is high exactly when $x$ is sparse; consider the extreme case where $\|x\|_{0}=1$ so that sampling is not even expected to see the non-zero coordinate unless $m\geq d$. These works then all essentially proceed by randomly preconditioning $x$ to ensure that $x$ is very well-spread (i.e. far from sparse) with high probability, so that sampling works, and thus fundamentally cannot take advantage of input sparsity. One way of obtaining faster matrix-vector multiplication for sparse inputs is to have sparse JL matrices $A$. Indeed, if $A$ has at most $s$ non-zero entries per column then $Ax$ can be computed in $O(s\cdot\|x\|_{0}+m)$ time. A line of work [Ach03, Mat08, DKS10, BOR10, KN10, KN12] investigated the value $s$ achievable in a JL matrix, culminating in [KN12] showing that it is possible to simultaneously have $m=O(\varepsilon^{-2}\log n)$ and $s=O(\varepsilon^{-1}\log n)$. Such a sparse JL transform thus speeds up embeddings by a factor of roughly $1/\varepsilon$ without increasing the target dimension.

Note that if $m=n$ one can simply take $A$ to be the identity matrix which achieves $s=1$, and thus the restriction $m=O(n/\log(1/\varepsilon))$ is nearly optimal. Also note that we can assume $\varepsilon=\Omega(1/\sqrt{n})$ since otherwise $m=\Omega(n)$ is required in any JL matrix [Alo09], and thus the $m=O(n/\log(1/\varepsilon))$ restriction is no worse than requiring $m=O(n/\log n)$. Furthermore if all the entries of $A$ are required to be equal in magnitude, our lower bound holds as long as $m\leq n/10$.

Before our work, only a restricted lower bound of $s=\Omega(\min\{1/\varepsilon^{2},\varepsilon^{-1}\sqrt{\log_{m}d}\})$ had been shown [DKS10]. In fact this lower bound only applied to the distributional JL problem, a much stronger guarantee where one wants to design a distribution over $m\times d$ matrices such that any fixed vector $x$ has $\|Ax\|_{2}=(1\pm\varepsilon)\|x\|_{2}$ with probability $1-\delta$ over the choice of $A$. Indeed any distributional JL construction yields the JL lemma by setting $\delta=1/n^{2}$ and union bounding over all the $x_{i}-x_{j}$ difference vectors. Thus, aside from the weaker lower bound on $s$, [DKS10] only provided a lower bound against this stronger guarantee, and furthermore only for a certain restricted class of distributions that made certain independence assumptions amongst matrix entries, and also assumed certain bounds on the sum of fourth moments of matrix entries in each row.

2 Compressed sensing and the restricted isometry property

Another object of interest are matrices satisfying the restricted isometry property (RIP). Such matrices are widely used in compressed sensing.

For any integer $k>0$, a matrix $A$ is said to have the $k$-restricted isometry property with distortion $\delta_{k}$ if $(1-\delta_{k})\|x\|_{2}^{2}\leq\|Ax\|_{2}^{2}\leq(1+\delta_{k})\|x\|_{2}^{2}$ for all $x$ with $\|x\|_{0}\leq k$.

Another upside of sparse RIP matrices is that they allow faster algorithms for encoding $x\mapsto Ax$. If $A$ has $s$ non-zeroes per column and $x$ receives, for example, turnstile streaming updates, then the compression $Ax$ can be maintained on the fly in $O(s)$ time per update (assuming the non-zero entries of any column of $A$ can be recovered in $O(s)$ time).

We show as long as $k<n/\polylog n$, any $k$-RIP matrix with distortion $O(1)$ and $m=\Theta(k\log(n/k))$ rows with $s$ non-zero entries per column must have $s=\Omega(k\log(n/k))$. That is, RIP matrices with the optimal number of rows must be dense for almost the full range of $k$ up to $n$. This lower bound strongly rules out any hope for faster recovery and compression algorithms for compressed sensing by using sparse RIP matrices as mentioned above.

We note that any sparsity lower bound should fail as $k$ approaches $n$ since the $n\times n$ identity matrix trivially satisfies $k$-RIP for any $k$ and has column sparsity $1$. Thus, our lower bound holds for almost the full range of parameters for $k$.

3 Oblivious Subspace Embeddings

Sarlós showed in [Sar06] that OSE’s are useful for approximate least squares regression and low rank approximation, and they have also been shown useful for approximating statistical leverage scores [DMIMW12], an important concept in statistics and machine learning. See [CW12] for an overview of several applications of OSE’s.

The work of Sarlós picked $A$ with special structure so that $AS$ can be computed in time $O(nd\log n)$, namely by using the Fast Johnson-Lindenstrauss Transform of [AC09] (see also [Tro11]). Unfortunately the time is $O(nd\log n)$ even for sparse matrices $S$, and several applications require solving numerical linear algebra problems on sparse matrix inputs. For example in the Netflix matrix where rows are users and columns are movies, and $S_{i,j}$ is some rating score, $S$ is very sparse since most users rate only a tiny fraction of all movies [ZWSP08]. If $\nnz(S)$ denotes the number of non-zero entries of $S$, we would like running times closer to $O(\nnz(S))$ than $O(nd\log n)$ to multiply $A$ by $S$. Such a running time would be possible, for example, if $A$ only had $s=O(1)$ non-zero entries per column.

In a recent and surprising work, Clarkson and Woodruff [CW12] gave an OSE with $m=\poly(d/\varepsilon)$ and $s=1$, thus providing fast numerical linear algebra algorithms for sparse matrices. For example, the running time for least-squares regression becomes $O(\nnz(A)+\poly(d/\varepsilon))$. The dependence on $d,\varepsilon$ was improved in [NN12] to $m=O(d^{2}/\varepsilon^{2})$. The work [NN12] also showed how to obtain $m=O(d^{1+\gamma}/\varepsilon^{2})$, $s=O(1/\varepsilon)$ for any constant $\gamma>0$ (the constant in the big-Oh depends polynomially on $1/\gamma$), or $m=(d\polylog d)/\varepsilon^{2}$, $s=(\polylog d)/\varepsilon$. It is thus natural to ask whether one can obtain the best of both worlds: can there be an OSE with $m\approx d/\varepsilon^{2}$ and $s=1$?

In this work we show that any OSE such that all matrices in its support have $m$ rows and $s=1$ non-zero entries per column must have $m=\Omega(d^{2})$ if $n\geq 2d^{2}$. Thus for constant $\varepsilon$ and large $n$, the upper bound of [NN12] is optimal.

4 Organization

In Section 2 we prove our lower bound for the sparsity required in JL matrices. In Section 3 we give our sparsity lower bound for RIP matrices, and in Section 4 we give our lower bound on the number of rows for OSE’s having sparsity $1$. In Section 5 we give a lower bound involving $\delta_{k}$ on the number of rows in an RIP matrix, and in Section 6 we state an open problem.

JL Sparsity Lower Bound

In Section 2.1 we give the lower bound on $s$ in the case that all entries in $A$ are in $\{0,1/\sqrt{s},-1/\sqrt{s}\}$. In Section 2.2 we give our lower bound without making any assumption on the magnitudes of entries in $A$. Before proceeding further, we prove a couple lemmas used throughout this section, and also later in this paper. Throughout this section $A$ is always an $\varepsilon$-incoherent matrix.

For any $x\geq 2\varepsilon$, $A$ cannot have any row with at least $5/x$ entries greater than $\sqrt{x}$, nor can it have any row with at least $1/x$ entries less than $-\sqrt{x}$.

Proof. For the sake of contradiction, suppose $A$ did have such a row, say the $j$th row. Suppose $A_{j,i_{1}},\ldots,A_{j,i_{N}}>\sqrt{x}$ for some $x\geq 2\varepsilon$, where $N\geq 5/x$ (the case where they are each less than $-\sqrt{x}$ is argued identically). Let $v_{i}$ denote the $i$th column of $A$. Let $u_{i}$ be $v_{i}$ but with the $j$th coordinate replaced with $0$. Then for any $k_{1},k_{2}\in[N]$

and rearranging gives the contradiction $1/x\geq(N-1)/4>1/x$. $\blacksquare$

Let $s,q,r$ be positive reals with $q/r\geq 2$ and $s\leq q/e$. Then if $s\ln(q/s)\geq r$ it must be the case that $s=\Omega(r/\ln(q/r))$.

Proof. Define the function $f(s)=s\ln(q/s)$. Then $f^{\prime}(s)=\ln(q/(es))$ is increasing for $s\leq q/e$. Then since $q/r\geq 2$, for $s=cr\ln(q/r)$ for constant $c>0$ we have the equality $s\ln(q/s)=cr/\ln(q/r)\ln((q/r)\ln(q/r))=(c+o_{q/r}(1))r\ln(q/r)$, where the $o_{q/r}(1)$ term goes to zero as $q/r\rightarrow\infty$. Thus for $c$ sufficiently small we have that the $c+o_{q/r}(1)$ term must be less than $1$, so in order to have $f(s)\geq r$, since $f$ is increasing we must have $s=\Omega(r/\ln(q/r))$. $\blacksquare$

In this section we consider the case that all entries of $A$ are either $0$ or $\pm 1/\sqrt{s}$ and show a lower bound on $s$ in this case.

Suppose $m<n/10$ and all entries of $A$ are in $\{0,1/\sqrt{s},-1/\sqrt{s}\}$. Then $s\geq 1/(2\varepsilon)$.

Proof. For the sake of contradiction suppose $s<1/(2\varepsilon)$. There are $ns$ non-zero entries in $A$ and thus at least $ns/2$ of these entries have the same sign by the pigeonhole principle; wlog let us say $1/\sqrt{s}$ appears at least $ns/2$ times. Then again by pigeonhole some row $j$ of $A$ has $N=ns/(2m)$ values that are $1/\sqrt{s}$. The claim now follows by Lemma 3 with $x=1/\sqrt{s}$. $\blacksquare$

We now show how to improve the bound to the desired form.

Suppose $m<n/10$ and all entries of $A$ are in $\{0,1/\sqrt{s},-1/\sqrt{s}\}$. Then $s\geq\Omega(\varepsilon^{-1}\log n/\log(m/\log n))$.

Proof. We know $s\geq 1/(2\varepsilon)$ by Lemma 5. Let $t=2\varepsilon s\geq 1$. Every $v_{i}$ has $\binom{s}{t}$ subsets of size $t$ of non-zero coordinates. Thus by pigeonhole there exists a set of $t$ rows $i_{1},\ldots,i_{t}$ and $N=n\binom{s}{t}/(2^{t}\binom{m}{t})$ columns $v_{j_{1}},\ldots,v_{j_{N}}$ such that for each row all entries in those columns are $1/\sqrt{s}$ in magnitude and have the same sign (the signs may vary across rows). Letting $u_{j}$ be $v_{j}$ but with those $t$ coordinates set to $0$, we have

Suppose $s<c\varepsilon^{-1}\log n/\log(2em/n)$ for some small constant $c$ so that $n(s/(2em))^{t}\geq 2$. Then

Taking the natural logarithm of both sides gives

Define $q=2em$, $r=\varepsilon^{-1}\ln(\varepsilon n/4)/2$. Then $s\leq q/e$, since $s\leq m$. By [Alo09] we must have $m=\Omega(\varepsilon^{-2}\log n/\log(1/\varepsilon))$, so $q/r\geq 2$ for $\varepsilon$ smaller than some fixed constant. Thus by Lemma 4 we have $s=\Omega(r/\ln(q/r))$. The theorem follows since $\log(\varepsilon m/\log n)=\Theta(m/\log n)$ since $m=\Omega(\varepsilon^{-2}\log n/\log(1/\varepsilon))$ [Alo09]. $\blacksquare$

Suppose $m\leq\poly(1/\varepsilon)\cdot\log n<n/10$ and all entries of $A$ are in $\{0,1/\sqrt{s},-1/\sqrt{s}\}$. Then $s\geq\Omega(\varepsilon^{-1}\log n/\log(1/\varepsilon))$.

2 General matrices

Suppose $m<n/(20\ln(1/2\varepsilon))$. Then $s\geq 1/(4\varepsilon)$.

Proof. For the sake of contradiction suppose $s<1/(4\varepsilon)$. We know by Lemma 3 that for any $x\geq 2\varepsilon$, no row of $A$ can have more than $5/x$ entries of value at least $\sqrt{x}$ in magnitude and of the same sign. Define $S_{i}=\{j:A_{i,j}^{2}\geq 2\varepsilon\}$. Let $S_{i}^{+}$ be the subset of indices $j$ in $S_{i}$ with $A_{i,j}>0$, and define $S_{i}^{-}=S_{i}\backslash S_{i}^{+}$. Let $X$ denote the square of a random positive value from $S_{i}^{+}$. Then

We now show how to obtain the extra factor of $\log n/\log(1/\varepsilon)$ in the lower bound.

Now for these vectors $v_{i_{1}},\ldots,v_{i_{N}}$, let $S\subset[n]$ of size $t$ be the set of the largest coordinates (in magnitude) in each $v_{i_{j}}$. Define $u_{i_{j}}=(v_{i_{j}})_{[n]\backslash S}$; that is, we zero out the coordinates in $S$. Then for $j\neq k\in[N]$,

The last inequality used that $\|(v_{i_{j}})_{S}\|_{2}\geq\sqrt{t/s}$. Also we pick $t$ to ensure $t/s>2\varepsilon/(1-1/\sqrt{2})$ so that the right hand side of Eq. (1) is less than $-((1-1/\sqrt{2})/2)t/s=-Ct/s$. The penultimate inequality follows by Cauchy-Schwarz. Thus we have

However we also have $\|\sum_{j}u_{i_{j}}\|_{2}^{2}\geq 0$, which implies $s\geq C(N-1)t/2$ by rearranging Eq. (2). $\blacksquare$

Proof. By Lemma 8, $4\varepsilon s\geq 1$. Set $t=7\varepsilon s$ so that Lemma 9 applies. Then by Lemma 9, as long as $2^{t}\binom{m}{t}\binom{2(s+t)}{t}\leq n/2$,

where $C$ is as in Lemma 9. Taking the natural logarithm on both sides,

Define $r=\ln(7\varepsilon n/(4C))/(7\varepsilon),q=8e^{2}m/(49\varepsilon^{2})$. Thus we have $s\ln(q/s)\geq r$. We have that $s\leq q/e$ is always the case for $\varepsilon<1/2$ since then $q/e\geq m$ and we have that $s\leq m$. Also note for $\varepsilon$ smaller than some constant we have that $q/r>2$ since $m=\Omega(\log n)$ by [Alo09]. Thus by Lemma 4 we have $s\geq\Omega(r/\ln(q/r))$. Using that $\ln(\varepsilon n)=\Theta(\log n)$ since $\varepsilon>1/\sqrt{n}$, and that $2^{t}\binom{m}{t}\binom{2(s+t)}{t}\leq(8e^{2}m/(49\varepsilon^{2}s))\leq n/2$ for our setting of $t$ when $s=o(\varepsilon^{-1}\log n/\log(m/(\varepsilon^{-1}\log n)))$ gives $s=\Omega(\varepsilon^{-1}\log n/\log(\varepsilon^{-1}m/\log n))$. Since $m=\Omega(\varepsilon^{-2}\log n/\log(1/\varepsilon))$ [Alo09], this is equivalent to our lower bound in the theorem statement. $\blacksquare$

From Theorem 10, we can deduce that for constant $\varepsilon$, in order for the sparsity $s$ to be a constant independent of $n$, it must be the case that $m=n^{\Omega(1)}$. This fact rules out very sparse mappings even when we significantly increase the target dimension.

RIP Sparsity Lower Bound

Assume $k\geq 2$, $\delta_{k}<\delta$ for some fixed universal small constant $\delta>0$, $m<n/(64\log^{3}n)$. Then we must have $s=\Omega(\min\{k\log(n/k)/\log(m/(k\log(n/k))),m\})$.

a contradiction. Let a pattern at scale $t$ be a subset of size $u=\max\{2^{4-t}s/k,1\}$ of $[m]$ along with $u$ signs. There are $2^{-t-1}s/t^{2}\choose u$ patterns $P$ where $A_{v,i}^{2}\geq 2^{t-3}/s$ for all $v\in P$ and the signs of $A_{v,i}$ match the signs of $P$.

There are $2^{u}{m\choose u}$ possible patterns at scale $t$. By an averaging argument, there exists a scale $t$, and a pattern $P$ such that the number of columns of $A$ with this pattern is at least $z=n{2^{-t-1}s/t^{2}\choose u}/((\log s)2^{u}{m\choose u})$. Consider 2 cases.

Pick an arbitrary set of $k$ such columns. Consider the vector $v$ with $k$ ones at locations corresponding to those columns and zeroes everywhere else. We have $\|v\|_{2}^{2}=k$ and for each $j\in P$, we have

This contradicts the assumption that $\|Av\|_{2}^{2}\leq(1+\delta_{k})\|v\|_{2}^{2}$.

Case 2 (z<kz<k):

Consider the vector $v$ with $z$ ones at locations corresponding to those columns and zeroes everywhere else. We have $\|v\|_{2}^{2}=z$ and for each $j\in P$, we have $(Av)_{j}^{2}\geq z^{2}2^{t-3}/s$. Consider 2 subcases.

Case 2.1 (u=1u=1):

Then $z=\frac{n2^{-t-2}s/t^{2}}{(\log s)m}$, so

This contradicts the assumption that $\|Av\|_{2}^{2}\leq(1+\delta_{k})\|v\|_{2}^{2}$.

Case 2.2 (u=24−t​s/ku=2^{4-t}s/k):

Eq. (4) follows from $s<k\log(n/k)/(64\log(m/s))$. Eq. (5) follows from the fact that $f(t)=(\log(m/s)+\log e+t+2+2\log t)2^{-t}$ is monotonically decreasing for $t\geq 1$. Indeed,

Eq. (6) follows since $k<n/\log^{4/3}n<n/\log^{4/3}s$, which holds since $k\leq m\leq n/(64\log^{3}n)$. This contradicts the assumption of Case 2 that $z<k$.

Thus we have $s\geq\min\{k\log(n/k)/(64\log(m/s)),m/64\}$ as desired. If $s\geq m/64$ we are done. Otherwise we have $s\geq k\log(n/k)/(64\log(m/s))$. Define $q=m$, $r=k\log(n/k)/64$. Thus we have $s\log(q/s)\geq r$. We have $q/r\geq 2$ for $\delta_{k}$ smaller than some constant by Theorem 20, and we have $s<q/e=m/e$ since we assume we are in the case $s<m/64$. Thus by Lemma 4 we have $s=\Omega(r/\ln(q/r))$, which completes the proof of the theorem. $\blacksquare$

When $k\geq 2$, $\delta_{k}<\delta$ for some universal constant $\delta>0$, and the number of rows $m=\Theta(k\log(n/k))<n/(32\log^{3}n)$, we must have $s=\Omega(k\log(n/k))$.

The restriction $m=O(n/\log^{3}n)$ in Theorem 13 was relevant in Eq. (3). Note the choice of $t^{2}$ in the proof was just so that $\sum_{t}1/t^{2}$ converges. We could instead have chosen $t^{1+\gamma}$ and obtained a qualitatively similar result, but with the slightly milder restriction $m=O(n/\log^{2+\gamma}n)$, where $\gamma>0$ can be chosen as an arbitrary constant.

Oblivious Subspace Embedding Sparsity Lower Bound

In this section, we show a lower bound on the dimension of very sparse OSE’s.

Proof. Assume for the sake of contradiction that $m<d^{2}/214$. By Yao’s minimax principle, we only need to show there exists a distribution over subspaces such that any fixed matrix $A$ with column sparsity $1$ and too few rows would fail to preserve lengths of vectors in the subspace with probability more than $4/5$.

If we pick $i_{1},\ldots,i_{d}$ one by one. Conditioned on $i_{1},\ldots,i_{t-1}$, the probability that $a(i_{t})$ is heavy is at least $\frac{9}{10}-\frac{d}{n}\geq\frac{4}{5}$. Therefore, by a Chernoff bound, with probability at least $9/10$, the number of indices $i_{t}$ such that $a(i_{t})$ are heavy is at least $3d/4$.

We will show that conditioned on the number of such $i_{t}$ being at least $3d/4$, with probability at least $9/10$, two such indices collide. Let $j_{1},\ldots,j_{3d/4}$ be indices with $b(a(j_{t}))\geq\frac{n}{10m}$. Conditioned on $a(j_{1}),\ldots,a(j_{t-1})$, the probability that $j_{t}$ does not collide with any previous index is at most

Thus, the probability that no collision occurs is at most $e^{(-(3d/4)^{2}/(40m))+((3d/4)^{2}/n)}<1/10$. In other words, collision occurs with probability at least $9/10$. When collision occurs, the number of non-zero entries of $AM$, where $M$ is the matrix whose columns are $e_{i_{1}},\ldots,e_{i_{d}}$, is at most $d-1$ so it has rank at most $d-1$. Therefore, with probability at least $4/5$, $A$ maps some non-zero vector in the subspace to the zero vector (any vector $Mx$ for $x\in\ker(AM)$) and fails to preserve the length of all vectors in the subspace. $\blacksquare$

Lower Bound on Number of Rows for RIP Matrices

In this section we show a lower bound on the number of rows of any $k$-RIP matrix with distortion $\delta_{k}$. First we need the following form of the Chernoff bound.

This form of the Chernoff bound can then be used to show the existence of a large error-correcting code with high relative distance.

For any $0<\varepsilon\leq 1/2$ and integers $k,n$ with $1\leq k\leq\varepsilon n/2$, there exists a $q$-ary code with $q=n/k$ and block length $k$ of relative distance $1-\varepsilon$, and with size at least

for some absolute constant $C^{\prime}>0$.

Proof. We take a random code. That is, pick

Therefore by a union bound, a random multiset of $N$ codewords has relative distance $1-\varepsilon$ with positive probability (in which case it must also clearly be not just a multiset, but a set). $\blacksquare$

Before proving the main theorem of this section, we also need the following theorem of Alon [Alo09].

For any $0<\delta_{k}\leq 1/2$ and integers $k,n$ with $1\leq k\leq\delta_{k}n/2$, any $k$-RIP matrix with distortion $\delta_{k}$ must have $\Omega\left(\min\{n/\log(1/\delta_{k}),(k/(\delta_{k}\log(1/\delta_{k})))\log(n/k)\}\right)$ rows.

Proof. Let $C_{1},\ldots,C_{N}$ be a code as in Lemma 18 with block length $n/(k/2)$ and alphabet size $k/2$ with

Thus if we define $x_{1},\ldots,x_{N}$ by $x_{i}=Ay_{i}/\|Ay_{i}\|_{2}$, then the $x_{i}$ satisfy the requirements of Theorem 19 with inner products at most $O(\delta_{k})$ in magnitude. The lower bound on the number of rows of $A$ then follows. $\blacksquare$

It is also possible to obtain a lower bound on the number of rows of $A$ in Theorem 20 of the form $\Omega(\delta_{k}^{-2}k/\log(1/\delta_{k}))$. This is because a theorem of [KW11] shows that any such RIP matrix with $k=\Theta(\log n)$, when its column signs are flipped randomly, is a JL matrix for any set of $n$ points with high probability. We then know from Theorem 19 that a JL matrix must have $m=\Omega(\delta_{k}^{-2}\log n/\log(1/\delta_{k}))$ rows, which is $\Omega(\delta_{k}^{-2}k/\log(1/\delta_{k}))$.

Future Directions

For several applications the JL lemma is used as a black box to obtain dimensionality-reducing linear maps for other problems. For example, applying the JL lemma with distortion $O(\delta_{k})$ on a certain net with $N=O\binom{n}{k}\cdot O(1/\delta_{k})^{k}$ vectors yields a $k$-RIP matrix with distortion $\delta_{k}$ [BDDW08]. Note in this case, for constant $\delta_{k}$, the number of rows one obtains is the optimal $\Theta(\log N)=\Theta(k\log(n/k))$. Applying the distributional JL lemma with distortion $O(\varepsilon)$ to a certain net of size $2^{O(d)}$ yields an OSE with $m=O(d/\varepsilon^{2})$ rows to preserve $d$-dimensional subspaces (see [CW12, Fact 10], based on [AHK06]).

Applying the JL lemma in this black-box way using the sparse JL matrices of [KN12] yields a factor-$\varepsilon$ improvement in sparsity over using a random dense JL construction, with for example random Gaussian entries. However, some examples have shown that it is possible to do much better by not using the JL lemma statement as a black box, but rather by analyzing the sparsity required from the constructions in [KN12] “from scratch” for the problem at hand. For example, the work [NN12] showed that one can have column sparsity $O(1/\varepsilon)$ with $m=O(d^{1+\gamma}/\varepsilon^{2})$ rows in an OSE for any $\gamma>0$, which is much better than the column sparsity $O(d/\varepsilon)$ that is obtained by using the sparse JL theorem as a black box.

All entries of $A$ are in $\{0,1/\sqrt{s},-1/\sqrt{s}\}$. We write $A_{i,j}=\delta_{i,j}\sigma_{i,j}/\sqrt{s}$ where $\delta_{i,j}$ is an indicator random variable for the event $A_{i,j}\neq 0$, and the $\sigma_{i,j}$ are independent uniform $\pm 1$ r.v.’s.

For any $j\in[n]$, $\sum_{i=1}^{m}\delta_{i,j}=s$ with probability $1$.

Note that the resolution of this question will not just be in terms of the $\gamma_{2}$ functional. In particular, for constant $\delta_{k}$ we see that $m,s=\Theta((\gamma_{2}(V))^{2})$ is necessary and sufficient when $V$ is the set of all unit norm $k$-sparse vectors. Even increasing $m$ to $\Theta((\gamma_{2}(V))^{2+\gamma})$ does not decrease the lower bound on $s$ by much. Meanwhile for $V$ a unit sphere of a $d$-dimensional subspace, we can simultaneously have $m=O((\gamma_{2}(V))^{2+\gamma}/\varepsilon^{2})$, and $s=O(1/\varepsilon)$ not depending on $\gamma_{2}(V)$ at all.

References