On Using Toeplitz and Circulant Matrices for
Johnson-Lindenstrauss Transforms

arXiv:1706.10110v2 [math.FA] 8 Nov 2017

Casper Benjamin Freksen∗

Kasper Green Larsen∗

Abstract
The Johnson-Lindenstrauss lemma is one of the corner stone results in dimensionality reduction.
It says that given N , for any set of N vectors X ⊂ Rn , there exists a mapping f : X → Rm
such that f (X) preserves all pairwise distances between vectors in X to within (1 ± ε) if m =
O(ε−2 lg N ). Much effort has gone into developing fast embedding algorithms, with the Fast JohnsonLindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The
current fastest algorithm that yields the optimal m = O(ε−2 lg N ) dimensions has an embedding
time of O(n lg n + ε−2 lg3 N ). An exciting approach towards improving this, due to Hinrichs and
Vybíral, is to use a random m × n Toeplitz matrix for the embedding. Using Fast Fourier Transform,
the embedding of a vector can then be computed in O(n lg m) time. The big question is of course
whether m = O(ε−2 lg N ) dimensions suffice for this technique. If so, this would end a decades long
quest to obtain faster and faster Johnson-Lindenstrauss transforms. The current best analysis of
the embedding of Hinrichs and Vybíral shows that m = O(ε−2 lg2 N ) dimensions suffices. The main
result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e.,
there exists a set of N vectors requiring m = Ω(ε−2 lg2 N ) for the Toeplitz approach to work.

1

Introduction

The performance of many geometric algorithms depends heavily on the dimension of the input data. A
widely used technique to combat this “curse of dimensionality”, is to preprocess the input via dimensionality reduction while approximately preserving important geometric properties. Running the algorithm
on the lower dimensional data then uses less resources (time, space, etc.) and an approximate result for
the high dimensional data can be derived from the low dimensional result.
Dimensionality reduction approximately preserving pairwise Euclidean distances has found uses in a
wide variety of applications, including: Nearest-neighbour search [2, 12], clustering [6, 8], linear programming [22], streaming algorithms [19], compressed sensing [7, 11], numerical linear algebra [25], graph
sparsification [20], and differential privacy [5]. See more applications in [21, 14]. The most fundamental
result in this regime is the Johnson-Lindenstrauss (JL) lemma [15], which says the following:
Theorem 1 (Johnson-Lindenstrauss lemma). Let X ⊂ Rn be a set of N vectors, then for any 0 < ε <
1/2, there exists a map f : X → Rm for some m = O(ε−2 lg N ) such that
∀x, y ∈ X, (1 − ε)kx − yk22 ≤ kf (x) − f (y)k22 ≤ (1 + ε)kx − yk22 .
This result dates back to 1984 and says that to preserve pairwise Euclidean distances amongst a set
of N points/vectors in Rn to within a factor (1 ± ε), it suffices to use just m = O(ε−2 lg N ) dimensions.
The bound on m was very recently proven optimal [18].
The standard technique for constructing a map with the properties of Theorem 1 is the following:
Let A be an m × n matrix with entries independently sampled as either N (0, 1) random variables (as
in [10]) or Rademacher (uniform among {−1, +1}) random variables (as in [1]). Once such entries have
been drawn, let f : Rn → Rm be defined as:
1
f (x) = √ Ax.
m

∗ This research is supported by a Villum Young Investigator Grant, an AUFF Starting Grant and MADALGO, Center
for Massive Data Algorithmics, a Center of the Danish National Research Foundation, grant DNRF84. Department of
Computer Science, Aarhus University. {cfreksen,larsen}@cs.au.dk.

1

To prove that the map f satisfies the guarantees in Theorem 1, it is first shown that for any vector x,
the probability that kf (x)k22 is not within (1 ± ε)kxk22 is less than 1/N 2 . This probability is called the
error probability and denoted δ. Using linearity of f and a union bound over all pairs x, y ∈ X, the
probability that all pairwise distances (i.e. the norm of the vector x − y) are preserved can be shown to
be at least 1/2.

1.1

Time Complexity

Examining the classic Johnson-Lindenstrauss reduction above, we see that to embed a vector, we need to
multiply with a dense matrix and the embedding time becomes O(nm) (or equivalently O(nε−2 lg N )).
This may be prohibitively large for many applications (recall one prime usage of dimensionality reduction
is to speed up algorithms), and much research has been devoted to obtaining faster embedding time.
Fast Johnson-Lindenstrauss Transform. Ailon and Chazelle [2] were the first to address the question of faster Johnson-Lindenstrauss transforms. In their seminal paper, they introduced the so-called
Fast Johnson-Lindenstrauss transform for speeding up dimensionality reduction. The basic idea in their
paper is to first “precondition” the input data by multiplying with a diagonal matrix with random
signs, followed by multiplying with a Hadamard matrix. This has the effect of “spreading” out the
mass of the input vectors, allowing for the dense matrix A above to be replaced with a sparse matrix.
Since we can multiply with a Hadamard matrix using Fast Fourier Transform, this gives an embedding time of O(n lg n + ε−2 lg3 N ) for embedding into the optimal m = O(ε−2 lg N ) dimensions. For
m = ε−2 lg N ≤ n1/2−γ for any constant γ > 0, the embedding complexity was improved even further
down to O(n lg m) in [3].
Another approach to achieve the O(n lg m) embedding time, but without the restriction on ε−2 lg N ≤
1/2−γ
n
, is to sacrifice the target dimension. This was done in [4] and later improved in [17], where the
embedding complexity was O(n lg m) at the cost of an increased target dimension m = O(ε−2 lg N lg4 n).
Sparse Vectors. Another approach to improve the performance of JL transforms, is to assume the
input data is sparse, i.e. has few non-zero coordinates. Designing an algorithm based on the work in [24],
Dasgupta et al. [9] achieved an embedding complexity of O(kxk0 ε−1 lg2 (mN ) lg N ), where kxk0 = |{i |
xi 6= 0}|. This was later improved to O(kxk0 ε−1 lg N ) in [16].
Toeplitz Matrices. Finally, another very exciting approach is to use Toeplitz matrices or partial
circulant matrices for the embedding. We first introduce the terminology.
An m × n Toeplitz matrix is an m × n matrix, where every entry on a diagonal has the same value:


t0
t1
t2
· · · tn−1
 t−1
t0
t1
· · · tn−2 


 t−2
t−1
t0
· · · tn−3 



.. 
..
..
..
..

.
. 
.
.
.
t−(m−1)

t−(m−2)

t−(m−3)

···

tn−m

A partial circulant matrix is a special kind of Toeplitz matrix, where every row, except the first, is the
previous row rotated once:


t0
t1
t2
· · · tn−1
 tn−1
t0
t1
· · · tn−2 


 tn−2
tn−1
t0
· · · tn−3 



.. 
..
..
..
..

.
. 
.
.
.
tn−(m−1) tn−(m−2) tn−(m−3) · · · tn−m

Hinrichs and Vybíral [13] proposed the following algorithm for generating a JL embedding based on a
Toeplitz matrix1 : Let t−(m−1) , t−(m−2) , . . . , tn−1 and d1 , . . . , dn be i.i.d. Rademacher random variables,
and T be a Toeplitz matrix defined from t−(m−1) , t−(m−2) , . . . , tn−1 such that entry (i, j) takes values
1 [13]

uses a partial circulant matrix but notes that a Toeplitz matrix could be used as well.

2

Table 1: Comparison of the performances of various Johnson-Lindenstrauss transform algorithms. N is
the number of input vectors, n is the dimension of the input vectors, m is the dimension of the output
vectors, ε is the distortion.
Type

Embedding time

Target dimension (m)

Ref.

Random projection
Sparse
Sparse
FFT
FFT
FFT
Toeplitz
Toeplitz

O(nm)
O(kxk0 ε−1 lg2 (mN ) lg N )
O(kxk0 ε−1 lg N )
O(n lg n + m lg2 N )
O(n lg m)
O(n lg m)
O(n lg m)
O(n lg m)

O(ε−2 lg N )
O(ε−2 lg N )
O(ε−2 lg N )
O(ε−2 lg N )
O(ε−2 lg N )
O(ε−2 lg N lg4 n)
O(ε−2 lg3 N )
O(ε−2 lg2 N )

[10]
[9]
[16]
[2]
[3]
[17]
[13]
[23]

Notes

m ≤ n1/2−γ

tj−i for i = 1, . . . , m and j = 1, . . . , n. Let D be an n × n diagonal matrix with the random variable di
giving the i’th diagonal entry. Define the map f as
1
f (x) = √ T Dx.
m
Multiplying with a Toeplitz matrix corresponds to computing a convolution and can be done using
Fast Fourier Transform. By appropriately blocking the input coordinates, the complexity of embedding
a vector x is just O(n lg m) for any target dimension m. The big question is of course, how low can the
target dimension m be, while preserving the distances between vectors up to a factor of 1 ± ε?
In the original paper [13], the authors proved that setting the target dimension to m = O(ε−2 lg3 (1/δ)),
the norm of any vector would be preserved to within (1 ± ε) with probability at least 1 − δ. Setting
δ = 1/N 2 , a union bound over all pairwise difference vectors (as in the classic construction) shows that
dimension m = O(ε−2 lg3 N ) suffices. Later, the analysis was refined in [23], which lowered the target
dimension to m = O(ε−2 lg2 (1/δ)) for preserving norms to within (1 ± ε) with probability 1 − δ. Again,
setting δ = 1/N 2 , this gives m = O(ε−2 lg2 N ) target dimension. Now if the analysis could be tightened
even further to give the optimal m = O(ε−2 lg N ) dimensions, this would end the decades long quest for
faster and faster embedding algorithms!
Our Contribution. Our main result unfortunately shows that the analysis of Vybíral [23] cannot be
tightened to give an even lower target dimensionality. More specifically, we prove that the upper bound
given in [23] is optimal:
Theorem 2. Let T and D be the m × n Toeplitz and n × n diagonal matrix in the embedding proposed
by [13]. For all 0 < ε < C, where C is a universal constant, and any desired error probability δ > 0, if
the following holds for every unit vector x ∈ Rn :
"
#
2
1
√ T Dx − 1 < ε > 1 − δ,
Pr
m
2
then it must be the case that m = Ω(ε−2 lg2 (1/δ)).
While Theorem 2 already shows that one cannot tighten the analysis of Vybíral for preserving the
norm of just one vector, Theorem 2 does leave open the possibility that one would not need to union
bound over all N 2 pairs of difference vectors when trying to preserve all pairwise distances amongst a
set of N vectors. It could still be the case that there somehow was a strong positive correlation between
distances being preserved (though this seems extremely unlikely, and would be something not seen in
any previous approach to JL). To complete the picture, we indeed show that this is not the case, at least
for N somewhat smaller than the dimension n:
Theorem 3. Let T and D be the m × n Toeplitz and n × n diagonal matrix in the embedding proposed
by [13]. For all 0 < ε < C, where C is a universal constant, if the following holds for every set of N
3

vectors X ⊂ Rn :
"

Pr ∀x, y ∈ X :

1
1
√ T Dx − √ T Dy
m
m

2
2

− kx −

yk22

≤ εkx −

yk22

#

= Ω(1),

then it must be the case that either m = Ω(ε−2 lg2 N ) or m = Ω(n/N ).
We remark that our proofs also work if we replace T be a partial circulant matrix (which was also
proposed in [13]). Furthermore, we expect that minor technical manipulations to our proof would also
show the above theorems when the entries of T and D are N (0, 1) distributed rather than Rademacher
(this was also proposed in [13]).

2

Lower Bound for One Vector

Let T be m× n Toeplitz matrix defined from random variables t−(m−1) , t−(m−2) , . . . , tn−1 such that entry
(i, j) takes values tj−i for i = 1, . . . , m and j = 1, . . . , n. Let D be an n × n diagonal matrix with the
random variable di giving the i’th diagonal entry. This section shows the following:
Theorem 4. Let T be m × n Toeplitz and D n × n diagonal. If t−(m−1) , t−(m−2) , . . . , tn−1 and d1 , . . . , dn
are independently distributed Rademacher random variables for i = −(m − 1), . . . , n − 1 and j = 1, . . . , n,
then for all 0 < ε < C, where C is a universal constant, there exists a unit vector x ∈ Rn such that
"
#
2
√
1
√ T Dx − 1 > ε ≥ 2−O(ε m) .
Pr
m
2
√
and furthermore, all but the first O( m) coordinates of x are 0.
It follows from Theorem 4 that if we want to have probability
√ at least 1 − δ of preserving the norm of
any unit vector x to within (1 ± ε), it must be the case that ε m = Ω(lg(1/δ)), i.e. m = Ω(ε−2 lg2 (1/δ)).
This is precisely the statement of Theorem 2. Thus we set out to prove Theorem 4.
To prove Theorem 4, we wish to invoke the Paley-Zygmund inequality, which states, that if X is a
non-negative random variable with finite variance and 0 ≤ θ ≤ 1, then
Pr[X > θE[X]] ≥ (1 − θ)2

E2 [X]
.
E[X 2 ]

We carefully choose a unit vector x, and define the random variable for Paley-Zygmund to be the
k’th moment of the difference between the norm of x transformed and 1.
Proof. Let k be an even positive integer less than m/4 and define s := 4k. Note that
√ s ≤ m.√ Let x be
an arbitrary n-dimensional unit vector such that the first s coordinates are in {−1/ s, +1/ s}, while
the remaining n − s coordinates are 0. Define the random variable parameterized by k
Zk :=

1
√ T Dx
m

2
2

−1

!k

.

Since k is even, the random variable Zk is non-negative.
We wish to lower bound E[Zk ] and upper bound E[Zk2 ] in order to invoke Paley-Zygmund. The
bounds we prove are as follows:
√
Lemma 5. If k ≤ m, then the random variable Zk satisfies:
and

E[Zk ] ≥ m−k/2 k k 2−O(k)

E[Zk2 ] ≤ m−k k 2k 2O(k) .

4

Before proving Lemma 5 we show how to use it together with Paley-Zygmund to complete the proof
of Theorem 4.
We start by invoking Paley-Zygmund and then rewriting the expectations according to Lemma 5,
Pr[Zk > E[Zk ]/2] ≥ (1/4)

E2 [Zk ]
=⇒
E[Zk2 ]

E2 [Zk ]
=⇒
> (E[Zk ]/2)1/k ] ≥ (1/4)
E[Zk2 ]
#
2
1
k
√ T Dx − 1 >
√
≥ 2−O(k) .
m
C
0 m
2
1/k

Pr[Zk

Pr

"

√
Here C0 is some constant√
greater than 0. For any 0 < ε < 1/C
√0 , we can now set k such that k/(C0 m) =
ε, i.e. we choose k = εC0 m. This choice of k satisfies k ≤ m as required by Lemma 5. We have thus
shown that:
#
"
2
√
1
√ T Dx − 1 > ε ≥ 2−O(ε m) .
Pr
m
2

Remark. Theorem 4 can easily be extended to partial circulant matrices. The difference between partial
circulant and Toeplitz matrices is the√
dependence between the values in the first m and last m columns.
However, as only the first s = 4k ≤ 4 m entries in x are nonzero, the last m columns are ignored, and
so partial circulant and Toeplitz matrices behave identically in our proof.
Proof of Lemma 5. Before we prove the two bounds in Lemma 5 individually, we rewrite E[Zk ], as this
benefits both proofs.

!k 
2
1
E[Zk ] = E  √ T Dx − 1 
m
2

k 
2 

m
n
X
 1 X

 

tj−i dj xj   − 1 
= E




m i=1 j=1


1

= E 
m


m
X
i=1




n
X
j=1





t2j−i d2j x2j  + 

n
X

X

j=1 h∈{1,...,n}\{j}

 

n
m
n
X
 1 X X 2 2 2
= E
tj−i dj xj − x2j  + 
m i=1
j=1
j=1


 1
= E 
m

1
= k
m

m X
n
X

X

i=1 j=1 h∈{1,...,n}\{j}

X

k 

tj−i th−i dj dh xj xh  − 1 

X

h∈{1,...,n}\{j}

k 

tj−i th−i dj dh xj xh  

S∈([m]×[n]×[n])k |∀(i,j,h)∈S:h6=j



E

Y

(i,j,h)∈S



k 

tj−i th−i dj dh xj xh  



tj−i th−i dj dh xj xh 

Observe that for j > s or h > s the product becomes 0, as either xj or xh is 0. By removing all these
terms, we simplify the sum to


X
Y
1
tj−i th−i dj dh xj xh 
E[Zk ] = k
E
m
k
S∈([m]×[s]×[s]) |∀(i,j,h)∈S:h6=j

5

(i,j,h)∈S

Observe for an S ∈ ([m] × [s] × [s])k , that the value E
following two things are true:

hQ

(i,j,h)∈S tj−i th−i dj dh xj xh

i

is 0 if one of the

• A dj occurs an odd number of times in the product.
• A variable ta occurs an odd number of times in the product.
To see this, note that by the independence of the random variables, we can write the expectation of the
product, as a product of expectations where each term in the product has all the occurrences of the same
random variable. Since the dj ’s and ta ’s are Rademachers, the expectation of any odd power of one of
these random variables is 0. Thush if just a single random variable
amongst the dj ’s and ta ’s occurs an
i
Q
=
0.
Similarly, we observe that if every
odd number of times, we have E
t
t
d
d
x
x
(i,j,h)∈S j−i h−i j h j h
random variable occurs an even number of times, then the expectation of the product is exactly 1/sk
since each xj also occurs an even number of times. If Γk denotes the number of tuples S ∈ ([m]×[s]×[s])k
such that ∀(i, j, h) ∈ S we have h 6= j and furthermore:
• For all columns a ∈ [s], |{(i, j, h) ∈ S | j = a ∨ h = a}| mod 2 = 0.
• For all diagonals a ∈ {−(m − 1), . . . , s − 1}, |{(i, j, h) ∈ S | j − i = a ∨ h − i = a}| mod 2 = 0.
Then we conclude
E[Zk ] =

Γk
.
sk m k

(1)

Note that Zk2 = Z2k . Therefore,
E[Zk2 ] = E[Z2k ] =

Γ2k
.
2k
s m2k

(2)

To complete the proof of Lemma 5 we need lower and upper bounds for Γk and Γ2k . The bounds we
prove are
√
Lemma 6. If k ≤ m, then Γk and Γ2k satisfy:
Γk = mk/2 sk k k 2−O(k)
Γ2k = mk s2k k 2k 2O(k) .

and

The proofs of the two bounds in Lemma 6 are in Sections 2.1 and 2.2.
Substituting the bounds from Lemma 6 in (1) and (2) we get
E[Zk ] = m−k/2 k k 2−O(k)
E[Zk2 ] = m−k k 2k 2−O(k) ,
which are the bounds we sought for Lemma 5.

2.1

Lower Bounding Γk

We first recall that the definition of Γk is the number of tuples S ∈ ([m] × [s] × [s])k satisfying that
∀(i, j, h) ∈ S we have h 6= j and furthermore:
• For all columns a ∈ [s], |{(i, j, h) ∈ S | j = a ∨ h = a}| mod 2 = 0.
• For all diagonals a ∈ {−(m − 1), . . . , s − 1}, |{(i, j, h) ∈ S | j − i = a ∨ h − i = a}| mod 2 = 0.
We view a triple (i, j, h) ∈ ([m] × [s] × [s]) as two entries (i, j) and (i, h) in an m × s matrix.
Furthermore, when we say that a triple touches a column or diagonal, a matrix entry of the triple lie on
that column or diagonal, so (i, j, h) touches columns j and h and diagonals j − i and h − i. Similarly, we
say that a tuple S ∈ ([m] × [s] × [s])k touches a given column or diagonal l times, if l triples in S touches
that column or diagonal.
We intent to prove a lower bound for Γk by constructing a big family of tuples F ⊆ ([m] × [s] × [s])k ,
where each tuple satisfies, that each column and diagonal touched by that tuple is touched exactly twice.
As each column and diagonal is touched an even number of times, the number of tuples in the family is
a lower bound for Γk .
6

Proof of Γk = mk/2 sk k k 2−O(k) . We describe how to construct a family of tuples F ⊆ ([m] × [s] × [s])k
satisfying that ∀S ∈ F, ∀(i, j, h) ∈ S we have h 6= j and furthermore:
• For all columns a ∈ [s], |{(i, j, h) ∈ S | j = a ∨ h = a}| ∈ {0, 2}.
• For all diagonals a ∈ {−(m − 1), . . . , s − 1}, |{(i, j, h) ∈ S | j − i = a ∨ h − i = a}| ∈ {0, 2}.
From this and the definition of Γk it is clear that |F | ≤ Γk .
When constructing an S ∈ F, we view S as consisting of two halves S1 and S2 , such that S1 touches
exactly the same columns and diagonals as S2 and both S1 and S2 touches each column and diagonal at
most once. To capture this, we give the following definition, where S is meant to be the family of such
halves S1 and S2 .
Definition 7. Let S be the set of all tuples S ∈ ([m] × [s] × [s])k/2 such that
• ∀(i, j, h) ∈ S, j 6= h
• For all columns a ∈ [s], |{(i, j, h) ∈ S | j = a ∨ h = a}| ≤ 1
• For all diagonals a ∈ {−(m − 1), . . . , s − 1}, |{(i, j, h) ∈ S | j − i = a ∨ h − i = a}| ≤ 1
Definition 7 mimics the definition of Γk , and the first item in Definition 7 ensures that the triples in
a tuple in S are of the same form as in Γk . The final two items ensure that each column and diagonal,
respectively, is touched at most once. This is exactly the properties we wanted of S1 and S2 individually.
We can now construct F as all pairs of (half) tuples S1 , S2 ∈ S, such that S1 touches exactly the
same columns and diagonals as S2 . To capture that S1 and S2 touch the same columns and diagonals,
we introduce the notion of a signature. A signature of Si is the set of columns and diagonals touched by
Si .
To have S1 and S2 touch exactly the same columns and diagonals, it is necessary and sufficient that
they have the same signature.
We introduce the following notation: B denotes the number of signatures with at least one member,
and by enumerating the signatures, we let bi denote the number of (half) tuples in S with signature i.
We recall that a (half) tuple S1 ∈ S touches each column and diagonal at most once, and if S1 and
S2 share the same signature, they touch exactly the same columns and diagonals. Therefore, using ◦ to
mean concatenation, S = S1 ◦ S2 ∈ F, as each column and diagonal touched is touched exactly twice.
Therefore |F | is a lower bound for Γk . Note that for a given signature i, the number of choices of S1 and
S2 with that signature is b2i . This gives the following inequality,
Γk ≥ |F | =

B
X

b2i .

i=1

We now apply the Cauchy-Schwarz inequality:
B
X
i=1

b2i

B
X
i=1

B
B
X
X
2
b2i ≥
=⇒
bi
1 ≥
2

i=1

i=1

PB

2

i=1 bi
PB 2
i=1 1

=⇒ Γk ≥

|S|2
.
B

(3)

To get a lower bound on |S|2 /B (and in turn Γk ), we need a lower bound on |S| and an upper bound
on B. These bounds are stated in the following lemmas
Lemma 8. |S| = Ω(mk/2 sk 2−k ).

 k/2 s 
Lemma 9. B = O m+s
k/2 s
k

Before proving any of these lemmas, we show that they together with (3) give the desired lower bound
on Γk :
 k 2k −2k

m s 2
(k/2)k/2 k k
Ω(mk/2 sk 2−k )2

=
Ω
.
(4)
Γk = 


(m + s)k/2 sk/2 sk
k/2 s
s
O m+s
k/2
k
7

Because s = 4k, we have
we can simplify (4),

(k/2)k/2
sk/2

= 2−Θ(k) , and because s ≤ m:

mk
(m+s)(k/2)

= mk/2 2−Θ(k) . With this

Γk = mk/2 sk k k 2−O(k) .
which is the lower bound we sought.
Proof of Lemma 8. Recall that S ⊆ ([m] × [s] × [s])k/2 is the set of (half) tuples that touch each column
and diagonal at most once, and, for each triple (i, j, h) in these (half) tuples, we have j 6= h.
We prove Lemma 8 by analysing how we can create a large number of distinct S ∈ S by choosing the
triples in S iteratively.
For each triple, we choose a row and two distinct entries on this row. We choose the row among any
of the m rows.
However, because S ∈ S, when choosing entries on the row, we cannot choose entries that lie on
columns or diagonals touched by previously chosen triples. Instead we choose the two entries among
any of the other entries. Therefore, whenever we choose a triple, this triple prevents at most four row
entries from being chosen for every subsequent triple, as the two diagonals and two columns touched by
the chosen triple intersect with at most four entries on the rows of the subsequent triples. This leads to
the following recurrence, describing a lower bound for the number of triples
(
r · c · (c − 1) · F (r, c − 4, t − 1) if t > 0
F (r, c, t) =
(5)
1
otherwise
where r is the number of rows to choose from, c is the minimum number of choosable entries in any row,
and t is the number of triples left to choose.
Inspecting (5), we can see that F can equivalently be defined as
F (r, c, t) = rt

t−1
Y
i=0

If t ≤

c
8

(c − 4i)(c − 1 − 4i).

(6)

then the terms inside the product in (6) are greater than 2c , so we can bound F from below:
F (r, c, t) ≥ rt

1
c 2t
= rt c2t t .
2
4

We now insert the values for r, c and t to find a lower bound for |S|, noting that s = 4k ensures that
t ≤ 8c :
1
k
≥ mk/2 sk k/2 =⇒ |S| = Ω(mk/2 sk 2−k ).
|S| ≥ F m, s,
2
4
Proof of Lemma 9. Recall that for at triple S ∈ S we define the signature as the set of columns and
diagonals touched by S. Furthermore, viewing a triple (i, j, h) ∈ ([m] × [s] × [s]) as the two entries (i, j)
and (i, h) in an m × s matrix, we define the left endpoint as (i, min{j, h} and the right endpoint as
(i, max{j, h}).
The claim to prove is


 
m + s k/2 s
B=O
s
.
k/2
k

This is proven by first showing an upper bound on the number of choices for the diagonals of left
endpoints, then diagonals of right endpoints and finally for columns.
In an m × smatrix there are m + s different diagonals and as the chosen diagonals have to be distinct,
there are m+s
k/2 choices for the diagonals corresponding to left endpoints in a triple.
As the right endpoint of a triple has to be in the same row as the left endpoint, there are at most
s choices for the diagonal corresponding to the right endpoint when the left endpoint has been chosen
(which it has in our case). This gives a total of sk/2 choices for diagonals corresponding to right endpoints.
Finally, there are s columns to choose
 from and the chosen columns have to be distinct, and so the
total number of choices of columns is ks .
The product of these number of choices gives the upper bound sought.
8

Upper Bounding Γ2k

2.2

Proof. Recall that Γ2k is defined as the number of tuples S ∈ ([m] × [s] × [s])2k such that ∀(i, j, h) ∈ S
we have h 6= j and furthermore:
• For all columns a ∈ [s], |{(i, j, h) ∈ S | j = a ∨ h = a}| mod 2 = 0.
• For all diagonals a ∈ {−(m − 1), . . . , s − 1}, |{(i, j, h) ∈ S | j − i = a ∨ h − i = a}| mod 2 = 0.
Let F ⊆ ([m] × [s] × [s])2k be the family of tuples satisfying these conditions, and so |F | = Γ2k .
To prove an upper bound on Γ2k , we show how to encode a tuple S ∈ F using at most k lg m +
2k lg s + 2k lg k + O(k) bits, such that S can be decoded from this encoding. Since any S ∈ F can be
encoded using k lg m + 2k lg s + 2k lg k + O(k) bits and |F | = Γ2k , we can conclude:
Γ2k = 2k lg m+2k lg s+2k lg k+O(k) = mk s2k k 2k 2O(k) .
Let σ denote the encoding function and σ −1 denote the decoding function. If S ∈ F and t ∈ S, σ(t)
denotes the encoding of the triple t, σ(S) denotes the encoding of the entire tuple S, and σ(F ) denotes
the image of σ.
A tuple S ∈ F consists of triples t1 , t2 , . . . , t2k such that S = t1 ◦ t2 ◦ · · · ◦ t2k . To encode S ∈ F we
encode each of the triples and store them in the same order: σ(S) = σ(t1 ) ◦ σ(t2 ) ◦ · · · ◦ σ(t2k ).
We will first describe a graph view of a tuple S which will be useful for encoding and decoding, then
we will show an encoding algorithm and finally a decoding algorithm.
Graph A tuple S ∈ F forms a (multi)graph structure, where every triple (i, j, h) ∈ S is a vertex. Since
S ∈ F, there lies an even number of triple endpoints on each diagonal. We can thus pair endpoints lying
on the same diagonal, such that every endpoint is paired with exactly one other endpoint. When two
triples have endpoints that are paired, the triples have an edge between them in the graph. As every
triple has two endpoints, every vertex has degree two, and so the graph consists entirely of simple cycles
of length at least two.
Encoding To encode an S ∈ F, we first encode each cycle by itself by defining the σ(t)’s for the triples
t in the cycle. After this, we order the defined σ(t)’s as the t’s were ordered in the input.
1. For each cycle we perform the following:
(a) We pick any vertex t = (i, j, h) of the cycle and give it the type head. Define σ(t) as the
concatenation of its type head, its row i, and two columns j and h. This uses lg m+2 lg s+O(1)
bits.
(b) We iterate through the cycle starting after head and give vertices, except the last, type mid.
The last vertex just before head is given the type last.
(c) For each triple t of type mid we store its type and two columns explicitly. However, instead
of storing its row we store the index of its predecessor in the cycle order as well as how
they are connected: If we typed tr just before ts when iterating through the cycle, when
encoding ts we store r as well as whether tr and ts are connected by the left or right endpoint
in tr and left or right endpoint in ts . So define σ(t) as the concatenation of mid, the two
columns, the predecessor index and how it is connected to the predecessor. All in all we spend
lg k + 2 lg s + O(1) bits encoding each mid.

(d) Finally, to encode the triple t, which is typed last, we define σ(t) as the concatenation of its
type, its predecessors index, how it is connected to its predecessor, and the column of the
endpoint on the predecessor’s diagonal. We thus spend lg k + lg s + O(1) bits to encode a last.
However, since s = 4k the number of bits per encoded last is equivalent to 2 lg k + O(1), which
turns out to simplify the analysis later.
Note that for each triple, the type is encoded in the first 2 bits2 in the encoding of the triple. This
will be important during decoding.
2 To

encode the type in 2 bits we could use the following scheme: 00 = head, 01 = mid, 10 = last, and 11 is unused.

9

2. After encoding all cycles, we order the encoded triples in the same order as the triples in the input,
and output the concatenation of the encoded triples: σ(t1 ) ◦ σ(t2 ) ◦ · · · ◦ σ(t2k ).
To analyse the number of bits needed in total, we look at the average number of bits per triple inside
a cycle. Since all cycles have a length of at least two, each cycle has a head and a last triple. These two
use an average of lg2m + lg s + lg k + O(1) bits.
√ We now claim that the number of bits per mid is bounded
by this average. Recall that we assumed m ≥ k and s = 4k:
√
lg m
lg m
m ≥ k =⇒
≥ lg k =⇒
+ lg s + lg k + 2 ≥ lg k + 2 lg s =⇒
2
2
lg m
+ lg s + lg k + O(1) ≥ |mid|.
2

Since the average of all 2k triples is at most lg2m + lg s + lg k + O(1) bits, the number of bits for all
triples is at most k lg m + 2k lg s + 2k lg k + O(k).
Decoding We now show how to decode any σ(S) ∈ σ(F ) such that σ −1 (σ(S)) = S.
First we need to extract the encodings of the individual triples, then we decode each cycle, and finally
we restore the order of triples. The following steps describes this algorithm in more detail.
1. We first extract the individual σ(ti )’s, by iterating through the bit string σ(S). By looking at the
type in the first two bits of an encoded triple we know the length of the encoded triple. From this
we can extract σ(ti ) as well as know where σ(ti+1 ) begins.
2. We now wish to decode each cycle to get the row and two columns of every triple, so do the
following for each head ti :
(a) t ← ti
(b) Look at the first two bits in t to determine its type, and while t is not a last, do:
i. If t is a head, the row and two columns are stored explicitly.
ii. If t is a mid, the two columns are stored explicitly. From the reference to t’s predecessor,
we can calculate the diagonal shared between t and its predecessor. This is can be done as
we have stored which endpoint (left or right) of the predecessor lies on the diagonal, and
as we decode in the same order as we encoded, we have already decoded the predecessor.
We know which of t’s columns the shared diagonal intersects, and so we can calculate the
row.
If the predecessor is a head, take note of which diagonal is shared with it.
iii. t ← the triple that has t as its predecessor.
(c) t is now a last, so we know the predecessor’s index as well as a column. However, as the graph
consists of cycles rather than just linked lists, last shares a diagonal with its predecessor as
well as sharing a diagonal with head. We have noted which diagonal has already been used
for head, so the other diagonal head touches is shared with last.
From these two diagonals and the column, it is possible to calculate the row by the intersection
between the predecessor diagonal and the column, and the other column by the intersection
of the row and the other diagonal.
3. Finally order the triples as they were, when the encoded versions were extracted in step 1.

3

Lower Bound for N Vectors

In this section, we generalize the result of Section 2 to obtain a lower bound for preserving all pairwise
distances amongst a set of N vectors. Our proof uses Theorem 4 as a building block. Recall that
Theorem 4 guarantees that there is a vector x such that
"
#
2
√
1
√ T Dx − 1 > ε ≥ 2−O(ε m) .
Pr
m
2
10

√
Moreover, the vector x has non-zeroes only in the first O( m) coordinates. From such a vector x, define
x→i as the vector having its j’th coordinate equal to the (j − i)’th coordinate of x if j > i and otherwise
its j’th coordinate√is 0. In words, x→i is just x with all coordinates shifted by i.
For i ≤ n − O( m) (i small enough that all the non-zero coordinates of x stay within the n coordin√
ates), we see that T Dx and T Dx→i have the exact same distribution. Furthermore, if i ≥ m + C m
for a big enough constant C, T Dx and T Dx→i are independent. To see this, observe that the only
random variables amongst t−(m−1) , . . . , tn−1 that are multiplied with a non-zero coordinate of x in T Dx
are t−(m−1) , . . . , tO(√m) . Similarly, only random variables d1 , . . . , dO(√m) amongst d1 , . . . , dn are multiplied by a non-zero coordinate of x. For x→i , the same is true for variables t−(m−1)+i , . . . , tO(√m)+i and
√
di+1 , . . . , di+O(√m) . If i ≥ m + C m, these sets of variables are disjoint and hence T Dx and T Dx→i are
independent.
With the observations above in mind, we now define a set of vectors X as follows
X := {0, x, x→m+C √m , x→2(m+C √m) , . . . , x→⌊(n−C √m)/(m+C √m)⌋(m+C √m) }.
The 0-vector clearly maps to the 0-vector when using √1m T D as embedding. Furthermore, by the
arguments above, the embeddings of all the remaining vectors are independent and have the same
distribution. It follows that
#
"
2

|X|
√
1
Pr ∀x→i ∈ X : √ T Dx→i − 1 ≤ ε ≤ 1 − 2−O(ε m)
m
2

√ 
≤ exp −|X|2−O(ε m) .
Now since 0 ∈ X, it follows that to preserve all pairwise distances amongst vectors in X to within (1 ± ε),
we also have to preserve all norms to within ±ε. This is true since for all x of unit norm:
1
√ T Dx
m

2
2

−1 =

1
1
√ T Dx − √ T D0
m
m

2
2

2

− kx − 0k2 .

This proves the following:
Theorem 10. Let T be m×n Toeplitz and D n×n diagonal. If t−(m−1) , t−(m−2) , . . . , tn−1 and d1 , . . . , dn
are independently distributed Rademacher random variables for i = −(m − 1), . . . , n − 1 and j = 1, . . . , n,
then for all 0 < ε < C, where C is a universal constant, there exists a set of N = Ω(n/m) vectors
X ⊂ Rn such that
"
#
2


√
1
1
2
2
Pr ∀x, y ∈ X : √ T Dx − √ T Dy − kx − yk2 ≤ εkx − yk2 ≤ exp −N 2−O(ε m) .
m
m
2
It follows from Theorem 10 that if we want to have constant probability of successfully embedding
any set of N vectors, then either it must be the case that m = Ω(n/N ), or
√
m)

−N 2−O(ε

≥ −C0 ,

where C0 is a constant. This in turn implies that
√
lg N − O(ε m) ≤ lg C0
√
m = Ω(ε−1 lg N )
m = Ω(ε
This completes the proof of Theorem 3.

11

−2

2

lg N ).

=⇒
=⇒

References
[1] Dimitris Achlioptas.
Database-friendly random projections: Johnson–Lindenstrauss with
binary coins.
Journal of computer and System Sciences, 66(4):671–687, June 2003.
doi:10.1016/S0022-0000(03)00025-4.
[2] Nir Ailon and Bernard Chazelle. The fast Johnson–Lindenstrauss transform and approximate nearest
neighbors. SIAM Journal on Computing, 39(1):302–322, May 2009. doi:10.1137/060673096.
[3] Nir Ailon and Edo Liberty. Fast dimension reduction using rademacher series on dual BCH codes.
Discrete & Computational Geometry, 42(4):615–630, 2009. doi:10.1007/s00454-008-9110-x.
[4] Nir Ailon and Edo Liberty. An almost optimal unrestricted fast Johnson–Lindenstrauss transform.
ACM Trans. Algorithms, 9(3):21:1–21:12, June 2013. doi:10.1145/2483699.2483701.
[5] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson–Lindenstrauss transform itself preserves differential privacy. In Proceedings of the 2012 IEEE 53rd Annual Symposium
on Foundations of Computer Science, FOCS ’12, pages 410–419, Washington, DC, USA, 2012. IEEE
Computer Society. doi:10.1109/FOCS.2012.67.
[6] C. Boutsidis, A. Zouzias, M. W. Mahoney, and P. Drineas. Randomized dimensionality reduction
for k-means clustering. IEEE Transactions on Information Theory, 61(2):1045–1062, February 2015.
doi:10.1109/TIT.2014.2375327.
[7] E. J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory,
52(2):489–509, February 2006. doi:10.1109/TIT.2005.862083.
[8] Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proceedings of the
Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 163–172, New
York, NY, USA, 2015. ACM. doi:10.1145/2746539.2746569.
[9] Anirban Dasgupta, Ravi Kumar, and Tamá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. doi:10.1145/1806689.1806737.
[10] Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms, 22(1):60–65, 2003. doi:10.1002/rsa.10073.
[11] D. L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289–1306,
April 2006. doi:10.1109/TIT.2006.871582.
[12] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality.
Theory of Computing, 8(14):321–350, 2012.
doi:10.4086/toc.2012.v008a014.
[13] Aicke Hinrichs and Jan Vybíral. Johnson–Lindenstrauss lemma for circulant matrices. Random
Structures & Algorithms, 39(3):391–398, 2011. doi:10.1002/rsa.20360.
[14] Piotr Indyk. Algorithmic applications of low-distortion geometric embeddings. In Proceedings of the
42nd IEEE Symposium on Foundations of Computer Science, FOCS ’01, pages 10–33, Washington,
DC, USA, 2001. IEEE Computer Society. doi:10.1109/SFCS.2001.959878.
[15] William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space.
Contemporary mathematics, 26:189–206, 1984. doi:10.1090/conm/026/737400.
[16] Daniel M. Kane and Jelani Nelson. Sparser Johnson–Lindenstrauss transforms. J. ACM, 61(1):4:1–
4:23, January 2014. doi:10.1145/2559902.
[17] Felix Krahmer and Rachel Ward. New and improved Johnson–Lindenstrauss embeddings via the
Restricted Isometry Property. SIAM J. Math. Anal., 43(3):1269–1281, 2011.
12

[18] Kasper Green Larsen and Jelani Nelson. Optimality of the Johnson–Lindenstrauss lemma. In
Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science, FOCS
’17, Washington, DC, USA, October 2017. IEEE Computer Society.
[19] S. Muthukrishnan. Data Streams: Algorithms and Applications, volume 1(2) of Foundations and
TrendsTM in Theoretical Computer Science. now Publishers Inc., Hanover, MA, USA, January 2005.
doi:10.1561/0400000002.
[20] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J.
Comput., 40(6):1913–1926, December 2011. doi:10.1137/080734029.
[21] Santosh S. Vempala. The random projection method, volume 65 of DIMACS - Series in Discrete
Mathematics and Theoretical Computer Science. American Mathematical Society, Providence, RI,
USA, September 2004. doi:10.1007/978-1-4615-0013-1_16.
[22] Ky Vu, Pierre-Louis Poirion, and Leo Liberti. Using the Johnson–Lindenstrauss lemma in linear
and integer programming. ArXiv e-prints, July 2015. arXiv:1507.00990.
[23] Jan Vybíral. A variant of the Johnson–Lindenstrauss lemma for circulant matrices. Journal of
Functional Analysis, 260(4):1096–1105, 2011. doi:10.1016/j.jfa.2010.11.014.
[24] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In Proceedings of the 26th Annual International
Conference on Machine Learning, ICML ’09, pages 1113–1120, New York, NY, USA, 2009. ACM.
doi:10.1145/1553374.1553516.
[25] David P. Woodruff. Sketching as a Tool for Numerical Linear Algebra, volume 10(1–2) of Foundations
and TrendsTM in Theoretical Computer Science. now Publishers Inc., Hanover, MA, USA, 2014.
doi:10.1561/0400000060.

13

