Fast Nearest Neighbor Preserving Embeddings
Johan Sivertsen
jovt@itu.dk

arXiv:1707.06867v1 [] 21 Jul 2017

July 24, 2017
Abstract
We show an analog to the Fast Johnson-Lindenstrauss Transform for
Nearest Neighbor Preserving Embeddings in `2 . These are sparse, randomized embeddings that preserve the (approximate) nearest neighbors.
The dimensionality of the embedding space is bounded not by the size
of the embedded set n, but by its doubling dimension λ. For most large
real-world datasets this will mean a considerably lower-dimensional embedding space than possible when preserving all distances. The resulting
embeddings can be used with existing approximate nearest neighbor data
structures to yield speed improvements.

1

Introduction

Many algorithmic problems become overwhelmingly difficult in high-dimensional
settings. One way of trying to combat this problem is to discover mappings that
preserve the metric relevant to solving a given problem, while embedding it into
a lower dimensional setting. Most famously Johnson and Lindenstrauss [12]
showed the lemma:
Lemma 1 (JL-Lemma[12]). For any integer d > 0, and any  > 0, δ ∈ (0, 1/2),
for k = Θ(−2 log(1/δ)) there exists a distribution Π such that for k ×d matrices
M ∼ Π, for any x ∈ Rd ,
P r [(1 − )kxk2 ≤ kM xk2 ≤ (1 + )kxk2 )] > 1 − δ
d
The JL-Lemma
 shows the existence of an embedding of any set X ⊆ R into
−2
k = O log |X|
dimensions while preserving `2 distances up to a multiplicative (1 ± ) distortion. Proofs can be found for many different M [8, 12, 6, 1],
including Gaussian matrices [12, 6] and {0, ±1} matrices[1]. In fact we might
use any sub-gaussian distribution to fill the matrix [11]. These low dimensional
embeddings can been used to speed up many fundamental high-dimensional
problems like closest pair, nearest neighbor or minimum spanning tree. They
can also be used to decrease the storage requirements of a dataset when we
only need to preserve norms. Further discussion and examples can be found for
instance in [18, 10]. It is known that if we want to preserve the norm for all
x ∈ X, the embedding dimension k = O(log |X|−2 ) is optimal, see [14, 15, 4].
However it might not be necessary to preserve norms for all all points in
X. If for example we are interested in nearest neighbor queries we require only

1

that neighbors remain close to each other, while far away points do not get too
close. This idea was introduced and formalized as Nearest Neighbor Preserving
Embeddings by Indyk and Naor [11], who also presented an embedding. Using a full Gaussian matrix they showed that nearest neighbor distance can be
preserved while embedding into fewer dimensions
 distance preserv than in the
log(2/)
where λX is the
ing setting. Specifically, k is bounded by O log λX 2
doubling constant of X. By removing the requirement that all distances be
preserved we can get k smaller than in the bounds discussed above [14, 15, 4].
Another line of research has focused on improving the speed of the embeddings by using sparse matrices while keeping the distortion low[13, 5, 1, 3]. Call
q < 1 the sparsity parameter. If each entry in the used matrix is 0 with probability 1 − q we can improve the embedding time from O(dk) to expected time
O(dkq) by sparse matrix multiplication. A classic sparse matrix construction
is the Fast Johnson Lindenstrauss Transform (FJLT) Φ : Rd → Rk [3]. In
this paper we show
 is a Nearest Neighbor Preserving embed that the FJLT
and sparsity parameter q = O(log2 n/d) for
ding with k = O log λX log(2/)
2


O d log d + −2 log3 n evaluation time.

2

Preliminaries

Definition 2 (Nearest Neighbor Preserving Embeddings [11]). Let , δ ∈ (0, 1),
and let X be a set of points in Rd . For any point x ∈ X let x0 denote the
point closest to x in X \ {x} under the `2 norm. We say that an embedding
Φ : Rd → Rk is nearest neighbor preserving with parameters (, δ) if for any
x ∈ X, the following properties hold with probability at least δ:
1.

min
z∈X\{x}

kΦx − Φzk2 ≤ (1 + )kx − x0 k2 , and

2. if kx − yk2 > (1 + 2)kx − x0 k2 for some y ∈ X then kΦx − Φyk >
(1 + )kx − x0 k2 .
Definition 3 (Fast Johnson-Lindenstrauss Transform [3]). Let an embedding Φ
be defined by a k × d matrix Φ := P HD as follows: D is a random ±1 diagonal
d × d matrix, H is the d-dimensional Walsh-Hadamard transform, and P is a
k × d matrix populated by setting
(
X ∼ N (0, q −1 )
w.p. q
pij =
.
0
w.p. 1 − q
Here the parameter q is called the sparsity parameter of the FJLT.
Definition 4 (Doubling constant λX ). Let B(x, r) denote the ball of radius r
centered at x. The doubling constant λX of a point set X ⊆ Rd is defined to
be the smallest integer λ such that for any x ∈ X, and any r > 0, the point set
B(x, r) ∩ X can be covered by at most λ balls B(z, r/2) where z ∈ X. We refer
to log2 λX as the doubling dimension of X.

3

Fast Nearest Neighbor Preserving Embeddings

Given the definitions above let us state the claim:
2

Theorem 5 (Fast Nearest Neighbor Preserving Embeddings). For any X ⊆
Rd ,  ∈ (0, 1) where |X| = n and δ ∈ (0, 1/2) for some


log (2/)
k=O
log
(1/δ)
log
λ
X
2
there exists a nearest neighbor preserving embedding Φ : Rd → Rk with parameters (, 1 − δ) requiring expected

O d log(d) + −2 log3 n
operations.
By picking δ we can fix the probability of successfully sampling an embedding
that is nearest neighbor preserving and close to the expected number of operations. Indyk and Naor presents a proof for embeddings that are constructed
using fully Gaussian matrices G (see [11, Theorem 4.1]). Requiring O(nd) operations to perform the mapping. Our contribution will be to show how their
techniques can be applied to sparse embeddings. We first identify the properties
of a map that are sufficient for the Indyk-Naor proof to hold, and then construct
sparse embeddings exhibiting the properties with a bounded probability of error.
Definition 6. Let  ∈ (0, 1). We say that a distribution over maps Φ = P HD :
Rd → Rk satisfies the Indyk-Naor property for a set X ⊆ Rd with loss η ≥ 0 if
with probability 1 − η over the choice of D, the map satisfies that for all x ∈ X,
y ∈ X ∪ {0}
2

(P1) PrP [kΦ(x − y)k2 6∈ (1 ± )kx − yk2 ] ≤ e−Ω(k ) , and
(P2) PrP [kΦxk2 ≤ kxk2 ] ≤ (3)k .
Note that the above probabilities are taken only over the choices of P .
By bounding η with a constant we will then be able to extend the proof
presented by Indyk and Naor to show the correctness of Theorem 5. We will
then need to increase k by a corresponding constant to make up for the η loss,
but the order of k remains unchanged.
We will show that the FJLT[3] satisfies the Indyk-Naor properties. The
first property to satisfy is the normal Johnson-Lindenstrauss property, but it
is required to hold also for all difference vectors possible from X. The second
property is stronger, when   1/3. We will be referring to P1 and P2 as the
Distortion and Shrinkage bound respectively.

3.1

Smoothness

We call a vector x ∈ Rd s-smooth if kxk∞ ≤ s kxk2 . Note that since H and D
are isometries kHDxk2 = kxk2 .
Definition 7. For any s > 0 we say that a given diagonal matrix D is in an
s-smooth setting if
∀x, y ∈ X ∪ {0}, kHD(x − y)k∞ ≤ skx − yk2 .

3

In this section we will bound
the probability of D not being in an s-smooth

q
log n
setting for s = O
, and then in Section 3.3 and 3.4 we show how the
d
Distortion and Shrinkage follow from smoothness.
Let us first consider a single vector z = (x − y) where x, y ∈ X ∪ {0}.
Assume kHDzk∞ ≥ skzk2 then there is some entry 1 ≤ i ≤ d such that
1
, then |(HDz)i b| ≥ s so we see
|(HDz)i | ≥ skzk2 . Let b = kzk
2
Pr[kHDzk∞ ≥ skzk2 ] = Pr[kHDzbk∞ ≥ s]
where zb is a unit vector. So without loss of generality we can focus on unit
vectors:
Lemma 8. Given a unit vector x in Rd ,
2

Pr[kHDxk∞ ≥ s] ≤ 2de−s

d/2

Proof. See [2] or [16](p.69). In short, we use:
E[esdu1 ] =

d
Y

E[esdhi xi ] =

d
Y
1
i

i

≤ exp(s2 d

d
X

2

√

(es

dxi

√

+ e−s

dxi

)

x2i /2)

i=1

=e

s2 dkxk22 /2

In a standard Chernoff bound.
As a small contribution we show a slightly better bound for our setting based
on approximating the kinchine inequality constants:
Lemma 9. Given a unit vector x in Rd ,
2

Pr[kHDxk∞ ≥ s] ≤ de−s

d/2.2

√
For s > 3/ d.
Proof. Let u = HDx = (u1 , .., ud )T , so u1 =
±d−1/2 . For all p ≥ 1:
"
Pr[|u1 | ≥ s] = Pr

d
X

p

±xi

i

Pd
i

hi xi where the hi are i.i.d

hP
pi
#
d
E
√ p
i ±xi
√
≥ ( ds) ≤
( ds)p

By the kinchine inequality, for p ≥ 9:
" d
p#
p
p
X
E
±xi
p/2.5kxk2
≤ Bp kxkp2 ≤
i
Γ( p+1 )

2
Since Bp = max{1, 2p−2/2 Γ(3/2)
} [17, 9] which is ≤
Hence:

4

p

p

p/2.5 for p ≥ 9.

(1)

Pr[|u1 | ≥ s] ≤



p p/2
2.5ds2

By setting p = max{9, s2 d)} we get:
2

Pr[|u1 | ≥ s] ≤ e−s

d/2.2

√
for s ≥ 3/ d. Union bound over u gives the claim.

3.2

Fixing s and q

Now let s = d−1/2

p

c ln(n2 d), then by Lemma 9 for x 6= y:

Pr[∃x, y ∈ X ∪ 0, kHD(x − y)k∞ ≥ skx − yk2 ] ≤

n2 d
ec ln(n2 d)/2.2

= e−c/2.2

If we fix s by setting c = 7 we observe that D is in
√ an s-smooth setting
with probability at least 19
20 . Recall that we used s ≥ 3/ d which holds in our
setting as long as n2 d ≥ 3.7. In the following
we will let Φ be a FJLT embedding

constructed by setting q = min c0 s2 , 1 where c0 > 0 is some universal constant.
We will then show that if D is s-smooth, this setting of q makes Φ = P DH
satisfy the distortion and shrinkage bounds.

3.3

Distortion bound

Lemma 10 (Distortion bound). For any x, y ∈ X ∪ {0} if D is in an s-smooth
setting, for  > 0:
Pr [|kΦ(x − y)k2 ∈
/ (1 ± )kx − yk2 ] ≤ e−Ω(k

2

)

Proof. The distortion bound is the main result in [3].

3.4

Shrinkage bound

The shrinkage bound is stronger than the distortion bound for large . We
will need it later to confine the probability of any of an infinite series of events
happening to a small constant.
Lemma 11 (Shrinkage bound). For a fixed vector x ∈ X, if D is in an s-smooth
setting, for  ∈ (0, 1):
k

Pr [kP HDxk2 ≤ kxk2 ] ≤ (3)
P

By the regular scaling of Gaussian with their standard deviation (See Lemma 16),
it is clear that for an upper bound on:
k
X
Pr[
yi2 ≤ t]
i

where the yi ∼ N (0, Zi /q) we only need to lower bound the Zi . I.e.
5

Lemma 12. If D is in an s-smooth setting and Zi ≥ q/2 for all i ∈ [k], then
∀t ≥ 0:
Pr[kP HDxk22 ≤ t] ≤ Pr[kGxk2 ≤ 2t]
Proof. For i ∈ {1, · · · , k} assume Zi ≥

q
2

and let Xi ∼ N (0, 1), then:

" k
#
X


Pr kP HDxk22 ≤ t = Pr
yi2 ≤ t
i=1



!2
r
hX
i
X
1
Xi
≤ t = Pr
≤ Pr 
Xi2 ≤ 2t .
2
Where the first equality follows from D being in an s-smooth setting and the
inequality from the bound on the Zi .
For our setting of q, Pr [∀i ∈ [k], Zi ≥ q/2] ≥ 19
20 (Lemma 3 of [2]). If we
combine this bound with Lemma 12 we are ready to prove Lemma 11.
Proof. Let z ∈ X and let x = zkzk−1
2 .
Pr [kP HDzk2 ≤ kzk2 ] = Pr [kP HDxk2 ≤ ] =
" k
#
X


2
2
2
2
Pr kP HDxk2 ≤  ≤ Pr
Xi ≤ 2

(by Lemma 12)

i

Where Xi ∼ N (0, 1). In general for s, t > 0 we know:

Pr

" k
X
i

h
P 2i
h
i E e−s Xi
P 2
Xi2 ≤ t = Pr e−s Xi ≥ e−st ≤
e−st
#

= est

k
Y

h
i
2
E e−sXi = est (1 + 2s)−k/2

i=1

h
i
2
Where the last step uses that E e−sXi =

√ 1
1+2s

for −1/2 ≤ s ≤ ∞.(See

[6])
Now to minimize we differentiate w.r.t s:
k
k
k
test (1 + 2s)− 2 + 2(− )est (1 + 2s)− 2 −1 = 0 ⇔ t = k(1 + 2s)−1
2
⇒ s = (k/t − 1)/2

k −k/2
)
≤ (et)k/2 . Now plug
So est (1 + 2s)−k/2 = e(k−t)/2 (k/t)−k/2 = e−t/2 ( et
2
in t = 2 and we have
" k
#
X
2
2
Pr
Xi ≤ 2 ≤ (2e2 )k/2 ≤ (3)k
i

6

3.5

Embedding properties

We have now seen how the Distortion and Shrinkage bounds follow from two
events:
First D must be in an s-smooth setting. Secondly all Zi must be within a
constant factor of q. By Lemma
q 9 the first event happens with probability at
2

least 19/20 when setting s = 7 lg(nd d) , assuming n2 d ≥ 3.7. By choosing q
corresponding to s as in[2], the second event occurs with probability at least
19/20(See Lemma 3 of [2]). For the chosen parameters Φ = P HD satisfies the
2
Indyk-Naor properties with probability 19
> 9/10.
20
We can then move on to prove Theorem 5 by showing:
Theorem 13 (Fast Nearest Neighbor Preserving Embeddings). For any X ⊆
Rd ,  ∈ (0, 1) there exists


log (2/)
log (1/δ) log λX
k=O
2
such that for every x ∈ X if x0 denotes the point closest to x in X \ {x} under
the `2 norm. with probability at least δ:
1.

min
z∈X\{x}

kΦx − Φzk2 ≤ (1 + )kx − x0 k2 , and

2. if kx − yk2 > (1 + 2)kx − x0 k2 for some y ∈ X then kΦx − Φyk >
(1 + )kx − x0 k2 .
Where Φ = P HD is a FJLT matrix, with expected
O d log(d) + −2 log3 (n) log(2/)



embedding time.
Proof. Let Φ = P HD follow Definition 3 with q = min{O(d−1 ln(n2 d)), 1} so Φ
satisfies the Indyk-Naor properties as pr. Definiton 6 with probability at least
9/10. The proof then follows from [11, Theorem 4.1]. For completeness we
include an extended version of the proof here. For familiar readers, the only
difference in this version is in making the spanning tree construction explicit.
Without loss of generality let x = 0 and kx0 k2 = 1. To show the first
property let y ∈ X satisfy kyk2 = 1, then by the distortion bound, Pr[kΦyk ≥
2
(1 + )] ≤ e−Ω(k ) . So for some universal C, setting k ≥ C ln(1/δ)/2 we get:
Pr[ min
z∈X\{x}

kΦx − Φzk2 > (1 + )kx − x0 k2 ] < δ/2

To show the second property we construct a spanning tree of (X \ B(x, 1 + 2))∪
{0} with 0 at the root. Let ri = 1 + (i + 2). Consider the annuli:
Xi = X ∩ B(0, ri+1 ) \ B(0, ri ), for i ≥ 1
By the definition of λX , for any i we can construct a minimal set Si ⊆ X such
that Xi ⊆ ∪t∈Si B(t, /4) and |Si | ≤ log2 ( 4r i ). The first level of the tree consists
of an edge between x and each t ∈ Si for all i ≥ 0. From each t a spanning tree
is build on the points in B(t, /4) with t at the root, as described in lemma 14.
7

r1
r2
r3

Figure 1: An illustration of the spanning tree construction used in the proof of
Theorem 13.
Figure 1 illustrates the construction. Some ordering is imposed on the t points
so points in overlapping balls are only spanned once.
We can then restate the second property as ∃i ≥ 0, ∃x ∈ Xi .kΦxk ≤ 1 + ,
at least one of two events took place:
√
1. ∃i ≥ 0, ∃t ∈ Si .kΦtk2 ≤ 1 +  + 4 (1 + i)
√
2. ∃i ≥ 0, ∃t ∈ Si , ∃x ∈ B(t, 4 ) ∩ X.Φx ∈
/ B(Φt, (1 + i) 4 )
Since ktk2 ≥ ri −


4

there is some constant C such that:
(
√
1 − /8 for i ≤ 1/2
kΦtk
1 + (1 + i)/4 + 
√
≤
=
ktk2
1 + (2 + i) − /4
C/ i for i > 1/2

Fix some i. Using the distortion and shrinkage bounds:
i
h
√
Pr ∃t ∈ Si , kΦtk2 ≤ 1 + (1 + i)/4 + 
( log (4r /)
2
λx 2 i e−ck for i ≤ 1/2
√
≤
log (4r /)
λx 2 i (3C/ i)k for i > 1/2
( 0 2
e−c k for i ≤ 1/2
≤ −c0 k
i
for i > 1/2

00

For k ≥ c2 log(2/) log(λX ) where c00 is some universal constant. For the
second event lemma 14 gives:
√ 
0

2 (4ri /4) e−ck(1+i) ≤ e−c k(1+i)
Pr[∃t, ∃y ∈ B(t, )∩X, Φy ∈
/ B(Φt, (1+ i) )] ≤ λlog
x
4
4
8

So there is some c000 where the first event is most likely. Hence:
(
000
2
2e−c k for i ≤ 1/2
Pr[∃x ∈ Xi .kΦxk2 ≤ 1 + ] ≤
000
2i−c k for i > 1/2
Summing over all the i we get:
Pr[∃i ≥ 0, ∃x ∈ Xi .kΦXk2 ≤ 1 + ] =

∞
X

Pr[∃x ∈ Xi .kΦxk2 ≤ 1 + ]

i

≤

X
000
2 −c000 k2
e
2i−c k ≤ δ/2
+
2

2
i>1/

for some k ≥ log(1/δ) c̃2 log(2/) log(λX ) where c̃ is some large enough constant. The number of operations required for embedding x is O(d) for the
diagonal matrix D, O(d log d) for H using the Walsh-Hadamard transform [7]
and finally O (|P |) where |P | is the number of non-zero entries. By our setting
of q, |P | ∼ Bin(kd, q) so
E [|P |] = kdq
= O(−2 log(λX ) log(2/) log2 (n))
= O(−2 log3 (n) log(2/epsilon))

Lemma 14. Let X be a subset of the unit ball in Rd , including 0. Then there
exists universal constants c, C > 0 such that for  > 0 and k ≥ C log λX :
2

Pr[∃x ∈ X, kP HDxk2 ≥ (1 + )] ≤ e−ck(1+) .
Proof. The proof is given in [11, Lemma 4.2]. We include a spanning tree
version here for completeness. We build a spanning tree T on X with root 0 in
the following way: Define sets for each possible level of the tree, L0 , L1 , . . . ⊆ X.
Let L0 = 0. To build Lj+1 , for every point t ∈ Lj let St be the minimal size set
such that ∪s∈St B(t, 2−j−1 ) ∩ X covers all of B(t, 2−j ) ∩ X. By the definition
of doubling constant we know that |St | ≤ λX . Connect t to every point in St ,
if some St sets overlap only a single connection is made to avoid cycles. Let
Lj+1 = ∪t∈Lj St . We observe that 0 < |Lj | ≤ λjX .
Now let E(T ) denote the edges in T . Let Ej be the subset of E(T ) with
one node in Lj and the other in Lj+1 , by the construction of the tree ∀e ∈ Ej
we have kek2 ≤ 2−j+1 . For every x ∈ X denote the unique path from 0 to
x in T by p(x) ⊆ E(T ). For 0 ≤ j ≤ |p(x)| let pj (x) ∈ Lj be the vertex on
the
P∞path at level j, for j > |p(x)| let pj (x) = x. We can then compose x as
j=0 (pj+1 (x) − pj (x)), the first |p(x)| steps corresponding to edges in E(T ),

9

and the remaining steps having 0 contribution. The argument then follows [11]:
Pr[∃x ∈X, kP HDxk2 ≥ (1 + )]
"

 −j #
(1 + ) 3
≤ Pr ∃x ∈ X, ∃j ≥ 0, kP HD(pj+1 (x) − pj (x))k2 ≥
3
2
"
#


∞
−j
X
1+ 3
=
Pr ∃e ∈ Ej , kP HDek2 ≥
3
2
j=0
#
"
 j
∞
X
1+ 4
kek2
≤
Pr ∃e ∈ Ej , kP HDek2 ≥
6
3
j=0
"
#
 j
∞
X
1+ 4
2j
≤
λX Pr kP HDxk2 ≥ 1 +
− 1 ,for any unit vector x
6
3
j=0
≤

∞
X

2

−ck(1+)
λ2j
Xe

(4/3)2j /100

2

≤ e−ck(1+)

j=0

For k ≥ C log λX + 1. Crucially the second last step uses that|E(T )| = |X| − 1.
We can then use Lemma 9 to see that D is in a smooth setting with constant
19
. The last step then follows from
probability, for our setting of s at least 20
Lemma 10.

4

Conclusion and future work

In this paper we present embeddings that combine the low dimensional embedding space achieved by Nearest Neighbor Preserving Embeddings [11] with a
speedup of the embedding runtime achieved by a Fast-JL construction [3]. This
results in embeddings that are faster than fully Gaussian Nearest Neighbor Preserving Embeddings and use fewer dimensions than any Johnson-Lindenstrauss
type embedding.
The benefit of Nearest Neighbor Preserving Embeddings generally depends
on the difference between n = |X| and λX . While λX is always upper bounded
by n it can often be much smaller, this helps to explain why some datasets
can be successfully embedded into much fewer dimensions, and much faster,
than theoretical results looking only on |X| can explain. For datasets with low
doubling dimension we can expect to find fast embeddings into a low number
of dimensions, even if the dataset is very large.
While the number of rows in the embedding matrix is independent of n, the
sparsity of the matrix is not. This happens because we must ensure that all
O(n2 ) possible edges in the constructed spanning trees used in lemma 14 are
smooth. Future work could focus on alternative constructions using closer to
O(n) edges or other ways of increasing the sparsity.
Acknowledgements
The author would like to thank Anupam Gupta for much fruitful discussion
during the writing of this paper.

10

References
[1] Dimitris Achlioptas. Database-friendly random projections: Johnsonlindenstrauss with binary coins. Journal of Computer and System Sciences,
66(4):671 – 687, 2003. Special Issue on {PODS} 2001.
[2] N I R Ailon and Bernard Chazelle. THE FAST JOHNSONLINDENSTRAUSS TRANSFORM AND APPROXIMATE NEAREST NEIGHBORS. 39(1):302–322, 2009.
[3] Nir Ailon and Bernard Chazelle. The fast Johnson-Lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput., 39(1):302–322,
2009.
[4] N. Alon and B. Klartag. Optimal compression of approximate inner products and dimension reduction. ArXiv e-prints, October 2016.
[5] Anirban Dasgupta, Ravi Kumar, and Tamás Sarlos. A sparse johnson: Lindenstrauss transform. In Proceedings of the Forty-second ACM Symposium
on Theory of Computing, STOC ’10, pages 341–350, New York, NY, USA,
2010. ACM.
[6] Sanjoy Dasgupta and Anupam Gupta. An Elementary Proof of a Theorem of Johnson and Lindenstrauss. Random Structures and Algorithms,
22(1):60–65, 2003.
[7] B. J. Fino and V. R. Algazi. Unified matrix treatment of the fast walshhadamard transform. IEEE Trans. Comput., 25(11):1142–1146, November
1976.
[8] P Frankl and H Maehara. The johnson-lindenstrauss lemma and the
sphericity of some graphs. Journal of Combinatorial Theory, Series B,
44(3):355 – 362, 1988.
[9] Uffe Haagerup. The best constants in the khintchine inequality. Studia
Mathematica, 70(3):231–283, 1981.
[10] Piotr Indyk. Algorithmic applications of low-distortion geometric embedding. In Poceedings of the 42nd Annual Symposium on Foundations of
Computer Science (FOCS), pages 10–33, 2001.
[11] Piotr Indyk and Assaf Naor. Nearest-neighbor-preserving embeddings.
ACM Trans. Algorithms, 3(3):Art. 31, 12, 2007.
[12] William B Johnson and Joram Lindenstrauss. Extensions of Lipschitz
mappings into a Hilbert space. Contemporary mathematics, 26(January
1984):189–206, 1984.
[13] Daniel M. Kane and Jelani Nelson. Sparser johnson-lindenstrauss transforms. J. ACM, 61(1):4:1–4:23, 2014.
[14] Kasper Green Larsen and Jelani Nelson. The johnson-lindenstrauss lemma
is optimal for linear dimensionality reduction. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of
11

LIPIcs, pages 82:1–82:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
[15] Kasper Green Larsen and Jelani Nelson. Optimality of the johnsonlindenstrauss lemma. CoRR, abs/1609.02094, 2016.
[16] Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press,
2005.
[17] Fedor L. Nazarov and Anatoliy N. Podkorytov. Ball, Haagerup, and Distribution Functions, pages 247–267. Birkhäuser Basel, Basel, 2000.
[18] Santosh S. Vempala. The Random Projection Method, volume 65 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science.
American Mathematical Society, 2004.
[19] Vladimir M Zolotarev. One-dimensional stable distributions, volume 65.
American Mathematical Soc., 1986.

5

Appendix: Properties of Gaussians

Lemma 15. Let X ∼ N (0, x) and Y ∼ N (0, y). Then ∀t > 0:
y ≥ x ⇒ Pr[X 2 ≤ t] ≥ Pr[Y 2 ≤ t]
2

2

y ≤ x ⇒ Pr[X ≤ t] ≤ Pr[y ≤ t]

(2)
(3)

With equality exactly when x = y.
Proof. Let y ≥ x:
√
t] − Pr[X ≤ − t] ≥
√
√
Pr[Y ≤ t] − Pr[X ≤ − t] ≥
√
√
Pr[Y ≤ t] − Pr[Y ≤ − t] = Pr[Y 2 ≤ t]

Pr[X 2 ≤ t] = Pr[X ≤

√

(4)
(5)
(6)

Similarly in the other direction when y ≤ x.
We can generalize to sums of such variables:
Pk
Lemma 16. For any integer k ≥ 1. Let X = i=1 Xi2 where Xi ∼ N (0, xi )
Pk
and Y = i=1 Yi2 where Yi ∼ N (0, yi ). Then if yi ≥ xi for all i ∈ {1, · · · , k}
we have:
Pr[Y ≤ t] ≤ Pr[X ≤ t].
Proof. We show
proof by induction. Define a new variable Sl =
P
Pk a standard
k−l
2
2
X
+
Y
.
As
a base case set l = 1:
i
j=k−l+1 j
i=1
Pr[S1 ≤ t] = Pr[Yk2 +

k−1
X

Xi2 ≤ t] ≤ Pr[S0 ≤ t].

i=1

By fixing Xi2 for 1 ≤ i ≤ k − 1 and using lemma. 15. And generally for all
integers l > 0 up to l = k:
12

Pr[Sl ≤ t] = Pr[Sl−1 ≤ t]
By fixing everything but the l’th variable and using lemma. 15. We arrive at
Pr[Y ≤ t] = Pr[Sk ≤ t] ≤ Pr[S0 ≤ t] = Pr[X ≤ t].
Lemma 17 (2-stable Gaussians). Let X, X1 , .., Xd ∼ N (0, σ 2 ) and u ∈ Rd ,
then:
d
X
ui Xi ∼ kuk2 X ∼ N (0, σ 2 kuk22 )
i=1

Proof. See [19].

13

