Near-Optimal Sample Complexity Bounds for
Circulant Binary Embedding

arXiv:1603.03178v2 [] 14 Mar 2016

Samet Oymak∗
March 15, 2016

Abstract
Binary embedding is the problem of mapping points from a high-dimensional space to a Hamming
cube in lower dimension while preserving pairwise distances. An efficient way to accomplish this is
to make use of fast embedding techniques involving Fourier transform e.g. circulant matrices. While
binary embedding has been studied extensively, theoretical results on fast binary embedding are rather
limited. In this work, we build upon the recent literature to obtain significantly better dependencies on
the problem parameters. A set of N points in R n can be properly embedded into the Hamming cube
{±1}k with δ distortion, by using k ∼ δ −3 log N samples which is optimal in the number of points N and
compares well with the optimal distortion dependency δ −2 . Our optimal embedding result applies in the
√
regime log N ≲ n1/3 . Furthermore, if the looser condition log N ≲ n holds, we show that all but an
arbitrarily small fraction of the points can be optimally embedded. We believe our techniques can be
useful to obtain improved guarantees for other nonlinear embedding problems.

1

Introduction

Binary embedding problem aims to map a set of points in a high-dimensional space to the Hamming cube
in a lower dimension. The task is preserving the distances between the points while keeping embedding
dimension as small as possible. A common approach to accomplish this task is applying a random map to
the data. In particular, given a point x ∈ Rn , we first apply a linear transformation x → Ax ∈ Rk and then
apply the discretization Ax → sgn(Ax) where sgn(⋅) returns the sign. Given a set S and distortion level
δ > 0, we are interested in ensuring that for all x, y ∈ S, A satisfies
∣k −1 ∥sgn(Ax), sgn(Ay)∥H − ang(x, y)∣ ≤ δ.

Here, ∥⋅, ⋅∥H is the Hamming distance between two {0, 1}k vectors and ang(⋅) is the angular distance which
returns the smaller angle between two points normalized by π. Often we are interested in embedding a large
set of points S = {vi }N
i=1 or a continuous set such as a subspace. An important aspect of the embedding
problems is the tradeoff between the number of points N and the embedding dimension m. For linear
embedding, classical Johnson-Lindenstrauss (JL) Lemma guarantees that by using k ≈ δ −2 log N samples, N
points can be embedded with δ distortion. More recently, this tradeoff attracted significant attention for the
binary embedding problem. Specifically, by choosing A to be a Gaussian matrix, it can be trivially shown that
one can achieve a good binary embedding under the same assumption of k ≈ δ −2 log N . This arguments have
also been extended to arbitrary (e.g. continuous) sets which are of interest for sparse estimation problems.
While the results on dense Gaussian matrices are valuable, for most applications we are interested in
faster projections where embedding can be done in near-linear time. Such projections make use of fast
matrix multiplications such as the Fourier Transform followed by random diagonal modulations and are
broadly called Fast Johnson-Lindenstrauss Transform (FJLT). In this work, we focus on circulant embedding
matrices where projection matrix A is given by A = RCh diag(r). Here,
∗

Google Inc. 1600 Amphitheatre Parkway, Mountain View, CA 94043.

1

• R ∈ Rk×n is the restriction operator that selects k rows out of n uniformly at random.
• h, r ∈ Rn are independent vectors with independent standard normal entries.
• Ch is a circulant matrix whose first row is equal to h∗ .
• diag(r) is a diagonal matrix obtained from the vector r.
The theoretical results for fast binary embedding techniques are rather limited [13, 22, 23]. Related to us,
very recently Yu et al. provided an analysis of circulant projections. Loosely speaking, the authors show
that by using k ∼ log2 N samples, binary embedding with small distortion is possible as long as log N ≲ n1/6 .
Another related work connected to nonlinear embedding is due to Le et al. [11]. Here, the authors speed
up Kernel approximation [17] by making use of FJLT however the number of required Fourier features scale
quadratically due to suboptimal concentration bounds. A natural question is whether circulant projections
can achieve the optimal binary embedding guarantees. In this work, we answer this question positively. We
show that using k ∼ log N samples, binary embedding via circulant matrices will be successful as long as
log N ≲ n1/2 . This shows that Fast JL Transform not only works well for linear embedding but also for highly
nonlinear problems and the embedding behavior is essentially same.
Contributions: Specifically, we have two sets of results. Our first set of results consider embedding with
circulant projections and the associated theorem has a dependency on the coherence of the set {vi }N
i=1 . When
the points are not spiky, (i.e. small infinity norm), the optimal embedding works for a larger regime of N .
For maximally incoherent sets we can allow log N ≲ n1/2 . Our second result is a corollary of the first one and
attempts to remove the dependence on incoherence. This is done by applying an additional layer of randomness x → Hdiag(b)v where H is the Hadamard transform and diag(b) is a diagonal matrix with independent
Rademacher diagonal entries. The overall embedding takes the form v → sgn(RCh diag(r)Hdiag(b)v). Observe that all matrix multiplications are still near-linear time. This model makes no assumption
√ on the set
1/3
{vi }N
. Furthermore, if log N ≲ n, fast and
i=1 and optimal embedding is possible as soon as log N ≲ n
optimal binary embedding still succeeds for all but arbitrarily small fraction of the points.

1.1

Related Literature

Binary embedding with dense Gaussian matrices is a rather well studied problem. Guarantees for finite set
of points can be obtained by applying a standard Chernoff bound. Embedding continuous sets is a more
challenging problem and it is studied in a series of papers [2, 8, 13, 15, 16] with results mostly restricted
to Gaussian ensemble. Much less is known for the fast embedding techniques that make use of Fourier or
Hadamard transforms. We can split the existing results in this direction into two groups.
● Fast JL embedding followed by dense (two-layer) map: This map is given by x → sgn(GF diag(b)x)
′
′
where G ∈ Rk×k is a dense Gaussian matrix, F ∈ Rk ×n is the subsampled Discrete Fourier Transform matrix,
h has independent Rademacher entries, and k ≈ k ′ ≈ O(log N ). This first applies a fast linear dimensionality
′
reduction to linearly embed points to the lower dimensionality space Rk . Next, we use a dense Gaussian
matrix √
to obtain a binary embedding guarantee. This approach is not computationally efficient as soon as
k ≳ O( n) as dense Gaussian multiplication becomes more expensive than the Fourier transform. In [22],
Yi et al. propose a related but more efficient algorithm by replacing G with a more involved procedure
involving Toeplitz matrices.
√
The optimal embedding bound of the present paper applies in the regime k ≤ n which shows that
circulant projections
perform as good as two-layer maps computationally (both require O(n log n) in the
√
regime√k ≤ O( n)). However, the proposed approach is much simpler and easily extends to the regime
k ≥ O( n) in an efficient manner (albeit without proof).
● Simply use Fast JL embedding: We simply apply a Fast JL Transform by using a circulant matrix. The
map we consider has the form x → sgn(RCh diag(r)) where R ∈ Rk×n is the subsampling operator, Ch is a
circulant matrix and r, h are vectors with iid N (0, 1) entries. Since circulant matrices are diagonalized by the
Discrete Fourier Transform, the computational complexity of embedding is always O(n log n) independent
of the sample size k ≤ n. Yu et al. [23] very recently provided an analysis of this map with rigorous
2

sample complexity bounds. While their result has significant dependency on the set geometry, under best
circumstances, they show that k ≳ log2 N samples are sufficient for successful embedding as long as log N ≲
n1/6 . As an example of geometric dependence, the results of [23] depends on the maximal correlation of the
point set supi≠j ∣vi∗ vj ∣ and becomes arbitrarily suboptimal as this number approaches 1. In particular, they
cannot allow points that are close to each other. There are also several works on the applications of fast
binary projections in large scale image retrieval and hashing algorithms [6, 21, 24].

2

Main results

Suppose we are given N unit vectors in Rn namely {vi }N
i=1 . Our task is mapping this points to a lowdimensional Hamming cube in Rk while preserving the distances. We are interested in ensuring that for all
1 ≤ i, j ≤ N , A satisfies
∣k −1 ∥sgn(Avi ), sgn(Avj )∥H − ang(vi , vj )∣ ≤ δ.
As a geometric feature, we shall make use of the coherence of the set which is defined as
ρcross = max{ sup ∥vi ∥ℓ∞ ,
1≤i≤N

sup
1≤i≠j≤N

∥vi − vj ∥ℓ∞
∥vi − vj ∥ℓ2

}.

For our results to work, we make the following assumptions on N, k, n and the coherence parameter.
Condition 2.1 There exists sufficiently large nonnegative constants c1 , c2 , c3 1 , such that
1. k > c1 δ −3 log N .
2. c2 δkρcross log n < 1.
3. δ ≥ c3 kρcross .

Observe that in the maximally incoherent case (ρcross = O(n−1/2 )), we can pick√δ = o(1), k = O((log n)−1 n1/2 )
and log N = O(δ −3 k). Hence, our optimal embedding result applies up to O( n) as the embedding dimension. Our main result is on fast binary embedding of finite set of points with near-optimal embedding
dimensions and is stated in the next theorem.
Theorem 2.2 Let A = RCh diag(r) ∈ Rk be a circulant projection as described above. Under the assumptions
of Condition 2.1, with probability 1 − exp(−c4 δ 3 k), for all x, y ∈ {vi }N
i=1 , we have that
∣k −1 ∥sgn(Ax), sgn(Ay)∥H − ang(x, y)∣ ≤ δ.

This result applies to arbitrary set of points; however, it depends on the incoherence of the set ρcross .
One can get rid of this dependency by applying an additional layer of randomization. In particular, let H
be a Hadamard matrix of size n and let b ∈ Rn be a vector with independent Rademacher entries. If n is not
a power of 2, we can simply zero-pad the vectors. Consider the map
AH = AHdiag(b) = RCh diag(r)Hdiag(b).
For this map, we have the following result that is incoherence-free.
Theorem 2.3 Consider the binary embedding via the operator x → sgn(AH x). There exists universal
constants c, C > 0 such that following holds. Suppose
log N ≤ cδ 2 (log n)−1 n1/3 .

Then, with probability 1 − exp(−c log N ), the point set wi = Hdiag(b)vi obeys the incoherence condition with
ρcross = Cδ(log n)−1/2 n−1/3 . Consequently, as soon as k ≥ c1 δ −3 log N , with probability 1 − exp(−c4 δ 3 k),

1

∣k −1 ∥sgn(AH x), sgn(AH y)∥H − ang(x, y)∣ ≤ δ.

c, C, {ci , Ci }i≥0 , c′ , C ′ will be used to denote absolute constants that may vary from line to line.

3

Proof This result follows from the fact that the set of points obtained by the map vi → Hbvi has desirable
geometric features (small ρcross ) with high probability. In particular, combine Theorem 2.2 with Lemma
B.2.
√
Finally, the next result shows that one can optimally embed most of the points as long as log N ≲ O( n).

Theorem 2.4 Consider the binary embedding via the operator x → sgn(AH x). There exists universal
constants c, C > 0 such that following holds. Suppose
log N ≤ cδ 3 (log n)−2 n1/2 .

Then, with probability 1 − n−2 (over H), there exists Sgood ⊆ {vi }N
i=1 such that
∣Sgood ∣ ≥ (1 − c5 n−2 )N,

and

for all v ∈ Sgood : ∥Hdiag(b)v∥ℓ∞ ≤ ρcross

√
where ρcross = C log n/n. Consequently, as soon as k ≥ c1 δ −3 log N , with probability 1 − n−2 − exp(−c4 δ 3 k),
all x, y chosen from Sgood obeys
∣k −1 ∥sgn(AH x), sgn(AH y)∥H − ang(x, y)∣ ≤ δ.
Proof This result follows from the fact that all but a small fraction of the set of points obtained by the
map vi → Hbvi has desirable geometric features (small ρcross ) with high probability. In particular, combine
Theorem 2.2 with Lemma B.3. Pick p = n−2 in Lemma B.3.

3

Conclusions and Open Problems

In this work, we showed that fast binary embedding with near optimal dimensions are possible. In particular,
our embedding bounds are consistent with the state of the art results for linear embedding, indicating that
fast binary embedding is feasible under identical conditions to fast linear embedding such as [1,10,14]. This is
the first such result for fast binary embedding and significantly improves over related literature (e.g. [11,23]).
We believe the tools developed in this paper broadly applies to nonlinear embedding tasks. For instance, our
argument may be used to improve the concentration estimates of Fastfood features [11] which is a popular
fast kernel approximation technique. Our embedding result holds for finite set of points and it is of interest
to extend this work
√ that the embedding dimension
√ to continuous sets. A weakness of our result is the fact
scales up to O( n) which limits the number of points to log N ≲ O( n). This work opens up several
research directions.
• Fast embedding in linear regime: Does fast binary embedding work with embedding dimension n?
In other words, can we
√ pick k ∼ O(n) to embed N ∼ exp(O(k)) points? If not, is there a fundamental
bottleneck at k ∼ O( n)?
• Practical considerations: Our result on circulant embedding Ch diag(r) requires h and r to have
Gaussian entries. We believe r can have Rademacher entries without impacting the performance. It
would possibly improve the performance as the operator v → diag(r)v preserves the inner products
when r is Rademacher. Furthermore, it is not clear whether the incoherence assumption in Theorem
2.2 is necessary. Numerical results of prior work [23, 24] indicates that the map v → sign(Ch diag(r)v)
works well which suggests that we may not need additional randomization via Hadamard transform.
This would allow us to discard one layer of the embedding, namely, v → Hdiag(b)v.
• General nonlinear embedding: With a minor modification of our analysis, it is possible to obtain
fast embedding bounds for a more general model f (Ax) where f is a function that apply pointwise. The
important use cases would be to replace sgn(⋅) function with a general function such as quantization,
ReLU, sigmoid etc [5, 7]. It would also be of interest to investigate quadratic samples arising in phase
retrieval [4, 9].
4

• Embedding of continuous sets: Our current results apply to finite set of points however it is of
interest to embed continuous sets such as subspaces or sparse and low-rank manifolds. While this
problem is studied for dense Gaussian embedding matrices, we believe similar results can be obtained
for fast embedding matrices by building on this work and [23].
The rest of the paper is dedicated to the proof of our main result Theorem 2.2. Before going into technical
details, we introduce the necessary notation. Given a vector x ∈ Rn , let si (x) be the vector obtained by
shifting entries of x by i position, i.e. si (x). In particular, jth entry of si (x) is same as (i + j)th entry of
x modulo n. σmin (⋅) and σmax (⋅) returns minimum and maximum singular values of a matrix respectively.
∥ ⋅ ∥ denotes the spectral norm of a matrix and is same as σmax (⋅). diag(⋅) returns a diagonal matrix from
a vector input or returns the vector of diagonal entries of a matrix. c, C, {ci , Ci }i≥0 , c′ , C ′ will be used to
denote absolute constants. For nonzero x, x̄ = x/ ∥x∥ℓ2 and 0̄ = 0. Throughout this work, Hadamard and
Discrete Fourier Transform matrices are normalized to be unitary. A standard Gaussian vector obeys the
distribution N (0, I). S denotes a subset of {1, 2, . . . , n} obtained by picking k-elements uniformly at random
without replacement. Define direct coherence to be ρdirect = sup1≤i≤N ∥vi ∥ℓ∞ . Let θ > 0 be the smallest angle
between these points namely mini≠j ang(vi , vj ). It is trivial to show that the cross coherence can be bounded
as ρcross ≤ 2 sin(θ)−1 ρdirect . ℓth entry of a vector of size n is same as “ℓ (mod n)”th entry of the vector.

4

Controlling the Conditioning of the Projection Matrix

To simplify our notation, we shall assume that N ≥ n. n > N case can be recovered by setting n = N in our
main result. Let {ri }ki=1 be distinct numbers selected from the set {1, 2, . . . , n} uniformly at random.

Definition 4.1 (Random shift vectors) Let x ∈ S n−1 and let r ∈ Rn be a standard Gaussian vector.
Random shift vectors of x are a set of random vectors {Xi }ni=1 such that Xi = si (diag(r)x) for 0 ≤ i ≤ n − 1.
Define Yi in the identical manner given vector y for the same choice of r.
The following theorem summarizes the main result of this section by providing a spectral norm bound
on subsampled random shift vectors.
Theorem 4.2 Pick unit vectors x, y ∈ Rn satisfying x∗ y = 0 and ∥x∥ℓ∞ , ∥y∥ℓ∞ ≤ ρ. Form a matrix M ∈
Rn×2k by picking the same k vectors {Xri }ki=1 , {Yri }ki=1 from each of {Xi }ni=1 and {Yi }ni=1 without replacement
uniformly at random and then stacking next to each other. With probability 1 − 2 exp(−δ 2 k) (over r and
selection of {Xri }ki=1 ’s), we have that
σmax (M ∗ M − I) ≤ Cδkρ log n.

(4.1)

σmax (M ∗ M − Iθ ) ≤ Cδkρ log n.

(4.2)

Corollary 4.3 Let x, y be unit vectors obeying ang(x, y) = θ and ∥x∥ℓ∞ , ∥y∥ℓ∞ ≤ ρ. Form a matrix M ∈
Rn×2k by picking the same k vectors {Xri }ki=1 , {Yri }ki=1 from each of {Xi }ni=1 and {Yi }ni=1 without replacement
uniformly at random and then stacking next to each other. With probability 1 − 6 exp(−δ 2 k) (over r and
selection of {Xri }ki=1 ’s), we have that
Ik
where Iθ ∈ R2k×2k is given by the matrix [
cos(θ)Ik

cos(θ)Ik
].
Ik

Proof Proof is based on Theorem 4.2. Consider the decomposition y = cos(θ)x + sin(θ)y ′ where x∗ y ′ = 0.
Denote the k chosen columns {Xri }ki=1 by the matrix X ∈ Rn×k and the corresponding matrix to {Yri }ki=1
by Y ∈ Rn×k and set Y ′ = sin(θ)−1 (Y − cos(θ)X). Now observe that
X ∗ Y = cos(θ)X ∗ X + sin(θ)X ∗ Y ′ .

5

Using Theorem 4.2 on X ∗ X, we know that for an absolute constant c1 > 0, with probability 1 − 2 exp(−δ 2 k)
∥X ∗ X − I∥ ≤ c1 kρ log n.

Next we apply Theorem 4.2 to the matrix [X Y ′ ]. From Lemma A.4, y ′ obeys ∥y ′ ∥ℓ∞ ≤
we have the spectral norm estimate

2ρ
.
sin(θ)

Consequently,

∥X ∗ Y ′ ∥ ≤ ∥[X Y ′ ]∗ [X Y ′ ]∥ ≤ sin(θ)−1 c1 δkρ log n.

Combining these, and using triangle inequality, we obtain

∥X ∗ Y − cos(θ)I∥ ≤ sin(θ)∥X ∗ Y ′ ∥ + cos(θ)∥X ∗ X − I∥ ≤ 2c1 δkρ log n + cos(θ)c1 δkρ log n ≤ 3c1 δkρ log n.

Finally, we need to estimate the remaining submatrices. In particular, direct applications of Theorem 4.2
yields
max{∥X ∗ X − I∥, ∥Y ∗ Y − I∥} ≤ c1 δkρ log n.

Combining these estimates and representing M as 4 k × k submatrix involving X ∗ X, Y ∗ Y , X ∗ Y , Y ∗ X, we
find
∥M ∗ M − Iθ ∥ ≤ ∥Y ∗ Y − I∥ + ∥X ∗ X − I∥ + 2∥X ∗ Y − cos(θ)I∥ ≤ 8c1 δkρ log n.

Using a union bound, this final event happens with probability 1 − 6 exp(−δ 2 k).

4.1

Proof of Theorem 4.2

Theorem 4.4 (Hanson-Wright Theorem [18]) Let A ∈ Rn×n and g ∈ Rn be a standard Gaussian vector.
There exists a constant c > 0 such that
P(∣g ∗ Ag − E[g ∗ Ag]∣ ≥ t) ≤ 2 exp (−c {

t
t2
,
}) .
∥A∥2F ∥A∥

The following lemma follows as a corollary of Hanson-Wright Theorem.

Lemma 4.5 Let x, y be two unit vectors where ∥x∥ℓ∞ , ∥y∥ℓ∞ ≤ ρ and x∗ y = 0. Let g be a standard Gaussian
vector and G = diag(g). Then, the followings hold
For all 1 ≤ i ≠ j ≤ n
max{P(∣si (Gx)∗ sj (Gy)∣ > t), P(∣si (Gx)∗ sj (Gx)∣ > t), P(∣ ∥Gx∥ℓ2 − 1∣ > t)} ≤ 2 exp(−c min{
2

If ∥x∥ℓ∞ ≤ ρ, ∥y∥ℓ∞ ≤ ρ′ we additionally have P(∣si (Gx)∗ sj (Gy)∣ > t) ≤ 2 exp(−c min{ ρρt ′ , ρt 2 }).

t t2
, }).
ρ2 ρ2

2

Proof The proofs are based on Hanson-Wright Theorem. si (Gx)∗ sj (Gy) can be viewed as g ∗ M g where
M is a weighted permutation matrix whose (ℓ + i, ℓ + j)th entry is of the form xℓ+i yℓ+j for 1 ≤ ℓ ≤ n and
whose remaining entries are 0. Consequently, this matrix has maximum spectral norm ρ2 and maximum
Frobenius norm of ρ. E[si (Gx)∗ sj (Gy)] is clearly 0 when i ≠ j and for i = j it is equal to x∗ y = 0. Hence,
Hanson-Wright yields the desired bound.
For the second and third relations, identical argument applies. We additionally use the fact that
2
E[∥Gx∥ℓ2 ] = 1. The last statement follows by modifying the spectral norm estimate from ρ2 to ρρ′ .

Theorem 4.6 Pick unit vectors satisfying x∗ y = 0, ∥x∥ℓ∞ , ∥y∥ℓ∞ ≤ ρ, and ρ < c0 max{δ, (log n)−1/2 } for
a sufficiently small constant c0 > 0. Define the matrix A = [X1 . . . Xn Y1 . . . Yn ]. Form the matrix
M ∈ Rn×2k by picking the same k columns from {Xi }ni=1 and {Yi }ni=1 uniformly at random. Denote the
indices of these columns (i.e. support set) by S which is a subset of {1, 2, . . . , n}. Let Φ ∈ Rn×2n be the matrix
obtained by normalizing the columns of A. Let P be the matrix obtained by normalizing the columns of M
2
which is a submatrix of Φ. With probability 1 − 3e−δ k over the generation of S, we have that
E[σmax (M ∗ M − I)] ≤ ckρ log n.
6

(4.3)

Proof We first calculate the coherence of the matrix Φ which is defined as µ(Φ) = supi≠j ∣φ∗i φj ∣ where φi is
the ith column of Φ for 1 ≤ i ≤ 2n.
√
Lemma 4.7 P(µ(Φ) ≤ c1 log nρ) ≥ 1 − 4n−3 where the probability is over r and c1 > 0 is an absolute
constant.
−1/2

Proof For some absolute constant c1 = 8c2 , c2 > 0 we have the followings. Applying Lemma 4.5, for all
2
terms, we have that ∣ ∥Xi ∥ℓ2 −1∣, ∣Xi∗ Xj ∣, ∣Xi∗ Yj ∣, ∣Xi∗ Yi ∣ ≤ γ with probability 1−4n2 exp(−c2 min{γρ−2 , γ 2 ρ−2 }).
√
Hence, picking γ = c1 log nρ/2, we can guarantee that supi≠j ∣φ∗i φj ∣ is small for all i, j pairs with probability
1 − 4n−3 after normalizing the columns by their lengths ∥Xi ∥ℓ2 , ∥Yi ∥ℓ2 .
√
Next, Lemma 4.9 shows that the spectral norm of Φ can be bounded as ∥Φ∥ ≤ c3 ρ n log n with probability
−3
1 − n as well. Assume c3 > c1 without losing
generality.
√
√
√
2
Let us call the event that “µ(Φ) ≤ c3 log nρ and ∣ ∥Xi ∥ℓ2 − 1∣ ≤ c3 log nρ and ∥Φ∥ ≤ c3 ρ n log n” as E
which is an event over r with probability at least 1 − 5n−3. Split P into X and Y parts
√ namely P = [PX PY ]
where PX , PY ∈ Rn×k . Conditioned on E, applying Theorem C.4 with u = 2δ k log k, with probability
2
1 − e−δ k over the choice of support S, we have that
E

r ∣E

∗
[σmax (PX
PX − I)] ≤ c4 kρ log n

r ∣E

E

since we can bound (C.4) as follows

[σmax (PY∗ PY − I)] ≤ c4 kρ log n

√
√ √ √
√
k
k
µ(Φ) ku + ∥Φ∥2 ≤ c3 (ρ log n k k log kδ + (ρ2 n log n))
n
n
≤ c3 (kδρ log n + kρ2 log n) ≤ 2c3 kδρ log n.

where we used the fact that δ ≥ ρ. Similarly, applying Theorem C.7, we estimate the cross term as
r ∣E

E
This yields

r ∣E

E
2

∗
[σmax (PX
PY )] ≤ c4 kρ log n

[σmax (P ∗ P − I)] ≤ 4c4 kρ log n

with probability 1 − 3e−δ k . Next, observe that

P = M diag(α)
√
√
where α ∈ R2k is a vector whose entries lie between 1 ± c3 log nρ. Let c5 = max{2c3 , 8c4 }. Consequently,
applying Lemma B.4
σmax (M ∗ M − I) ≤ c5 kρ log n.
(4.4)
For the complementary event Ē, independent of the support S we will use a simpler estimate namely
σmax (M ∗ M − I) ≤ σmax (M ∗ M ) ≤ ∥M ∥2F = k(∥X1 ∥ℓ2 + ∥Y1 ∥ℓ2 ) ≤ 2kρ2 ∥r∥ℓ2 .
2

2

2

For this case, applying Lemma B.1 with p = 5n−3 yields that

E[∥r∥ℓ2 ∣Ē]P(Ē) ≤ c6 n−2
2

(4.5)
2

Combining the estimates over E (4.4) and Ē (4.5), we find that with the desired probability over S (1−e−δ k ),
Er [σmax (M ∗ M − I)] = Er [σmax (M ∗ M − I)∣E]P(E)
+ Er [σmax (M ∗ M − I)∣Ē]P(Ē)

≤ c5 kρ log n + c6 n−2 ≈ c5 kρ log n

where we used the fact that kρ log n ≥ n−2 .

7

4.2

Probabilistic bounds on the singular values

Lemma 4.8 Let R ∈ Rn×k be a matrix obtained by picking k elements from√{Xi }ni=1 ⊂ Rn and stacking them
next to each other. The maximum and minimum singular values of R are k ∥x∥ℓ∞ Lipschitz function of r.

Proof We view R as a random matrix obtained from the vector r. Given an alternative vector r̂, construct
R̂ from circular shifts of the vector diag(r̂)x in an identical manner to R (i.e. form {X̂i }ni=1 and pick the
same k elements). Applying Lemma A.1, we have that
√
√
∥R̂ − R∥F = k ∥diag(r̂)x − diag(r)x∥ℓ2 ≤ k ∥x∥ℓ∞ ∥r − r̂∥ℓ2
which is the desired conclusion.

Lemma 4.9 Let X = [X1 . . . Xn ] where Xi are obtained by circular shifts of diag(r)x. There exists an
absolute constant c > 0 such that
√
P(∥X∥ ≥ cρ n log n) ≤ c1 n−3 .
(4.6)

Next, consider the matrix Φ of Theorem 4.6. Assuming ρ < c′ (log n)−1/2 , Φ obeys the following similar bound
√
P(∥Φ∥ ≥ 4cρ n log n) ≤ (2c1 + 4)n−3 .

Proof Let g ∼ N (0, 1). From Stirling’s approximation, we have that
E[g 2d ] = (2d)!! =

(2d)! e(2d)2d+1/2 exp(−2d)
≤ c1 (2/e)ddd .
≤ √
2d d! 2d 2πdd+1/2 exp(−d)

Pick a complex standard normal g ′ = g1 + ig2 where g1 , g2 ∼ N (0, 1). Comparing the moments of g ′ to g
E[∣g ′ ∣2d ] = E[(g12 + g22 )d ] ≤ E[(g12 + g12 )d ] ≤ c1 (4/e)ddd .

Suppose h is a real random variable obeying E[h2d ] ≤ n E[∣g ′ ∣2d ] ≤ c1 n(4/e)ddd for all d ≥ 1. Then, using
Markov inequality
P(∣h∣ ≥ t) ≤ t−2d c1 n(4/e)d dd .
√
Pick t = 2d and d = (C log n)/2 to find that
P(∣h∣ ≥ t) ≤ t−2d c1 n(2/e)ddd ≤ c1 n(2/e)(C log n)/2 ≤ c1 n−3

by picking C > 0 to be a large enough constant. This gives
√
P(∣h∣ ≥ C log n) ≤ c1 n−3 .

(4.7)

The remaining discussion will analyze the spectral norm of X to make use of (4.7). Observe that the
random variable tr((X ∗ X)d ) ≥ ∥X∥2d . Now form the complex circulant matrix X ′ by stacking circular shifts
{si (diag(g)x′ )}ni=1 next to each other where are entries of the vector x′ are equal to ρ i.e. x′ = [ρ . . . ρ]∗
and g is a vector of independent random variables where each entry is distributed as g ′ .
Singular values of ρ−1 X ′ are trivial. In particular, singular values are absolute values of the eigenvalues
and eigenvalues
are independent complex Gaussian random variables whose imaginary and real parts have
√
′
denote the real part of the matrix X ′ . First observe that,
variance n. Next, we relate X ′ to X. Let Xreal
the following deterministic relation holds for all d ≥ 1
′
′
trace(X ′ X ′ )d ≥ trace((Xreal
)∗ Xreal
)d .
∗

′
′
On the other hand, E trace((Xreal
)∗ Xreal
)d ≥ E trace(X ∗ X)d . This follows form the fact that when the
traces are expanded term by term, each individual nonzero term of the left-hand side dominates that of the

8

right-hand side as entries of x′ are at least as large as that of x (in absolute value). Finally observe that
∗
trace(X ′ X ′ )d ∼ ∑ni=1 gi2d where gi are independent standard complex with variance 2ρ2 n. Consequently,
setting h = ∥X∥, we find that
n

E[h2d ] = E[∥X∥2d ] ≤ E trace(X ∗ X)d ≤ E trace(X ′ X)d = E[∑ gi2d ].
∗

i=1

√
To conclude with the proof of the first statement, apply the estimate (4.7) by normalizing both sides by ρ n
and obtain the advertised result (4.6).
To obtain the result on Φ, recalling
Theorem 4.6, we write Φdiag(α) = [X Y ] where X, Y = [Y1 . . . Yn ]
√
have spectral norm at most cρ n log n and α is a diagonal (length) normalization matrix whose entries are
at least 1/2 with probability 1 − 4n−3 as soon as ρ < c′ (log n)−1/2 for sufficiently small constant c′ > 0.
4.2.1

Finalizing the Proof of Theorem 4.2

Lemma 4.10 Consider the setup in Theorem 4.2 and set M = [Xr1 . . . Xrk Yr1 . . . Yrk ]. There exists a
constant c1 > 0 such that with probability 1 − 4 exp(−δ 2 k) over the generation of {ri }ki=1 and modulation r,
we have that
∥M ∗ M − I∥ ≤ c1 ρδk log n.
Proof From Theorem 4.6, we know that with probability 1 − 3e−δ

2

k

over support S

E[∥M ∗ M − I∥] ≤ cδkρ log n.
√
On the other hand, σmin (M ) and σmax (M ) are k ∥x∥ℓ∞ Lipschitz functions of r. Consequently, conditioned
on S, applying Lemma A.2, we have that
√
P(∣∥M ∥ − E[∥M ∥]∣ ≤ δ 2k ∥x∥ℓ∞ ) ≤ 2 exp(−δ 2 k).
Combining the expectation and deviation estimates, with probability 1 − 2 exp(−δ 2 k), we obtain that
√
√
√
∥M ∥ ≤ 1 + cδkρ log n + 2δkρ ≤ 1 + (c + 2)δkρ log n.
The exact same argument applies to the minimum singular value σmin (M ) which gives
√
√
√
σmin (M ) ≥ 1 − cδkρ log n − 2δkρ ≥ 1 − (c + 2)δkρ log n

allowing us to conclude with the desired result.

5

On orthogonal decomposition of Gaussian circulant pairs

k
Let x, y be two unit vectors chosen from {vi }N
i=1 . Form {Xri , Yri }i=1 via uniform sampling of Gaussian
n
′
′
circular rotations {Xi , Yi }i=1 . Decompose Xri = Xri + pi , Yri = Yri + p′i where pi , p′i are the projections of
Xri , Yri onto the span of {Xr′ j , Yr′j }i−1
j=1 . Observe that this has a similar flavor to QR decomposition.

2
Lemma 5.1 Let Si be the subspace spanned by {Xrj , Yrj }i−1
j=1 . With probability 1 −4 exp(−δ k), we have that
for all 1 ≤ i ≤ k
(5.1)
max{∥PSi (Xri )∥ℓ2 = ∥pi ∥ℓ2 , ∥PSi (Yri )∥ℓ2 = ∥p′i ∥ℓ2 } ≤ c1 δkρdirect .

9

Proof Our proof is in similar spirit to Lemma 12 of [23]. The main difference is that we apply an additional
orthogonalization procedure that reduces dependency on the correlation ∣x∗ y∣ and improves our estimates.
To start analysis, let us focus on Xri only. First observe that

Next observe that

span([Xr1 . . . Xri Yr1 . . . Yri ]) = span([Xr′ 1 . . . Xr′ i Yr′1 . . . Yr′i ]).
span([Xr1 . . . Xri Yr1 . . . Yri ]) = span([Xr1 . . . Xri Yr⊥1 . . . Yr⊥i ])

where Y ⊥ r1 is obtained by the Gaussian circular rotations of y ⊥ =

y−cos(θ)x
∥y−cos(θ)x∥ℓ

where θ is the angle between
2

x and y. Consequently, we can focus on understanding the projection of Xri onto the column span of
Mi = [Xr1 . . . Xri−1 Y ⊥ r1 . . . Y ⊥ ri−1 ]. Let Mi have singular value decomposition UL ΣUR∗ where Σ ∈
R2(i−1)×2(i−1) . Consider the vector
qi = Mi∗ Xri ∈ R2(i−1)
√
√
From Lemma 4.5, we know that each entry of qi is less than c2 max{ρdirect ρcross δ 2 k, ρdirect δ k} ≤ c2 δρdirect k
for all 1 ≤ i ≤ k with probability 1 − exp(−δ 2 k) where we used the fact that δ 2 k ≥ c′ log N ≥ c′ log n. On the
other hand, using Theorem 4.2, with the same probability all matrices {Mi }ki=1 satisfy
∥Mi∗ Mi − I∥ ≤ c3 ρcross k log n Ô⇒ σmin (Mi ) = σmin (Σ) ≥ 1 − c3 ρcross δk log n ≥ 1/2.

Consequently, the projection can be bounded as

−1
−1
(Σ) ∥Mi∗ Xri ∥ℓ2 .
(Σ) ∥ΣUL∗ Xri ∥ℓ2 = σmin
∥PSi (Xri )∥ℓ2 = ∥UL∗ Xri ∥ℓ2 ≤ σmin

This implies that, with 1 − 2 exp(−δ 2 k) probability, ∥PSi (Xri )∥ℓ2 ≤ c2
The identical argument applies to Yri .

√

√
2k × (δρdirect k)2 = 2c2 δkρdirect .

Lemma 5.2 Consider the matrix P ∈ Rn×2k obtained by concatenating pi , p′i for 1 ≤ i ≤ k. Under initial
assumptions, we have that ∥P ∥ ≤ 7 with probability 1 − 8 exp(−δ 2 k).

Proof Consider the matrix M = [Xr1 . . . Xrk Yr1 . . . Yrk ]. From Corollary 4.3, we know that ∥M ∥ ≤ 3
with probability 1 −6 exp(−δ 2 k). On the other hand, using Gaussian concentration, each column of M obeys
P(∥Xri ∥ℓ2 ≤ 2) ≤ 1 − exp(−0.5ρ−2 ).

Using our initial assumption δ ≥ c′ kρ (see Condition 2.1), this holds for all columns with probability 1 −
k exp(−0.5ρ−2 ) ≥ 1 − exp(−δ 2 k). Given this, observe that Xr′ i is perpendicular to {Xr′ j }j≠i and ∥Xr′ i ∥ℓ ≤
2
∥Xri ∥ℓ2 ≤ 2. This ensures that
∥[Xr′ 1 . . . Xr′ k ]∥ ≤ max ∥Xrk ∥ℓ2 ≤ 2.
1≤i≤k

Yr′i
′

′

[Xr′ 1

ensuring M =
The same argument applies to
4. Consequently ∥P ∥ = ∥M − M ∥ ≤ ∥M ∥ + ∥M ′ ∥ ≤ 7.

. . . Xr′ k Yr′1 . . . Yr′k ] has spectral norm of at most

Lemma 5.3 The matrix P = [p1 . . . pk p′1 . . . p′k ] obeys the following bounds with probability 1−12 exp(−cδ 2 k).
• Each column pi , p′i of P satisfies ∥pi ∥ℓ2 , ∥p′i ∥ℓ2 ≤ Cδρk for all 1 ≤ i ≤ k.
• Spectral norm of P satisfies ∥P ∥ ≤ 7.

Proof The proof follows directly by making use of Lemmas 5.2 and 5.1.

10

6

Final perturbation analysis

We are in a position to prove our main result Theorem 2.2.
Proof The proof is based on perturbation analysis, namely to what extent structured samples deviate from
Gaussian-like behavior. We break the analysis in two parts, namely over r and over h.
● Upper bounds on the perturbation due to r:
Recall that C = Ch is the circulant part of the embedding operator where h ∼ N (0, I) is its first row and
ith row is equal to si (h) for 1 ≤ i ≤ n. Given any two points x, y, chosen from {vi }N
i=1 consider the vectors
x′ = diag(r)x = X1 and y ′ = diag(r)y = Y1 . Now, observe that the ith entry of Cx′ is equal to
si (h)∗ x′ = h∗ sn−i (x′ ) = h∗ Xn−i .

Similarly the ith entry of Cy ′ is equal to h∗ Yn−i . Consequently, for a random subsampling RC ∈ Rk×n of
C, we have that
RCx′ = Mx h, RCy ′ = My h,
where Mx = [Xr1 . . . Xrk ]∗ and My = [Yr1 . . . Yrk ]∗ and {ri }ki=1 are randomly selected coordinates. Next,
for each 1 ≤ i ≤ k, we decompose Xri , Yri as described in Section 5.
Xri = Xr′ i + pi , Yri = Yr′i + p′i .
Since h is a standard Gaussian vector, by construction, h∗ Xr′ i and h∗ Yr′i is independent of {h∗ Xr′ j , h∗ Yr′j }j≠i .
To proceed, let us estimate the angle between Xr′ i , Yr′i probabilistically.
√
2
2
Firstly, ∥Xri ∥ℓ2 , ∥Yri ∥ℓ2 lies between 1 ± c1 δρ k with probability 1 − exp(−δ 2 k). Next, with the same
√
√
probability ∣Xr∗i Yri −x∗ y∣ ≤ c1 δρ k. Together these imply that ∣X̄r∗i Ȳri −x∗ y∣ ≤ 4c1 δρ k where ā = a/ ∥a∥ℓ2 .
Making use of Lemma A.5, we can conclude that
√ √
(6.1)
∣ang(Xri , Yri ) − ang(x, y)∣ ≤ c2 ρδ k ∶= ∆r .
In particular, since Xri , Yri are circulant rotations of Xr1 , Yr1 the angle between is exactly same i.e.
ang(Xri , Yri ) = ang(Xrj , Yrj ) for 1 ≤ i, j ≤ k.
With these, we can state the following result that summarizes the properties of the perturbation. Below
we additionally used the fact that log N ≤ δ 2 k/4.

Lemma 6.1 {Xri , Yri } satisfies the following with probability 1 − 12 exp(−δ 2 k/2) for all x, y pairs chosen
from {vi }N
i=1 where the probability is over r and support S.
• ∣ang(Xri , Yri ) − ang(x, y)∣ ≤ ∆r .

• {Xr′ i , Yr′i }ki=1 are orthogonal pairs and for all i, Xri − Xr′ i = pi , Yri − Yr′i = p′i where pi , p′i obey
∥pi ∥ℓ2 ≤ Cρδk, ∥[p1 . . . pk ]∥ ≤ 7.

What remains is to characterize the effect of perturbation error on the binary embedding distortion. Let
θi = ang(Xr′ i , Yr′i ). Applying Lemma A.5 again, we know for a fact that (by picking c2 > 0 to be a large
enough constant)
ang(Xr′ i , Xri ) ≤ c2 δρk/2, ang(Yr′i , Yri ) ≤ c2 ρδk/2.
Together, these ensure that

∣θi − ang(x, y)∣ = ∣ang(Xr′ i , Yr′i ) − ang(x, y)∣ ≤ c2 δρk + ∣ang(Xri , Yri ) − ang(x, y)∣ ≤ c2 δρk + ∆r ∶= ∆′r .

∆′r will be the source of embedding distortion due to r and our initial assumptions will guarantee that it is
small. Next section develops estimates for the remaining source of the perturbation which is connected to
h.
11

● Probabilistic analysis of the perturbation due to h:
Pick δbuf f > 0. For the rest of the discussion probabilities will be over h. Let us define the events
Ei = (h∗ Xr′ i > δbuf f and h∗ Yr′i < −δbuf f ) or (h∗ Xr′ i < −δbuf f and h∗ Yr′i > δbuf f ),
Ēi = (h∗ Xr′ i > δbuf f and h∗ Yr′i > δbuf f ) or (h∗ Xr′ i < −δbuf f and h∗ Yr′i < −δbuf f ).

Ei and Ēi are the robust versions of the events sgn(h∗ Xr′ i ) ≠ sgn(h∗ Yr′i ) and sgn(h∗ Xr′ i ) = sgn(h∗ Yr′i )
respectively.
Without losing generality, let us consider the event Ei . Recall that with probability 1 − exp(−δ 2 k),
2
2
for all 1 ≤ i ≤ k, we can guarantee that 0.75 ≤ ∥Xri ∥ℓ2 ≤ 2 and ∥pi ∥ℓ2 ≤ 0.25. Hence, conditioned on r,
∗
′
∗
′
h Xri (and h Xri ) is a Gaussian random variable with variance between 0.5 to 2. Also, observe that
P(sgn(h∗ Xr′ i ) ≠ sgn(h∗ Yr′i )) = θi . Consequently, letting θ = ang(x, y), from small ball probability of
Gaussians, we have that
P(Ei ) ≥ ang(θi ) − c3 δbuf f ≥ ang(θ) − c3 (δbuf f + ∆′r ).

Let E = ∑ki=1 1Ei . Consequently, applying a standard Chernoff bound, we find that

2
P(E ≥ k(ang(θ) − c3 (δbuf f + ∆′r ) − δbuf f )) ∶= P(E ≥ k(ang(θ) − c4 (δbuf f + ∆′r ))) ≥ exp(−2δbuf
f k)

(6.2)

where the probability is over h.
Next, we consider the impact of perturbations {pi , p′i }ki=1 . Using the facts that ∥P ∥2F ≤ C 2 ρ2 δ 2 k 3 , ∥P ∥ ≤ 7
and applying Lemma A.3, we have that
P(∥[p1 p2 . . . pk ]∗ h∥ℓ2 ≤ ρ2 δ 2 k 3 + t) ≥ 1 − exp(−c5 min{
2

t2
t
, }).
2
2
2
3
50C ρ δ k 50

2
To proceed, pick t = εbuf f δbuf
f k to obtain that with probability 1 − exp(−c6 min{
perturbation obeys
2
2
∥P ∗ h∥ℓ2 ≤ ρ2 δ 2 k 3 + εbuf f δbuf
f k.
′

The same bound applies to the perturbation over y namely P =
that sgn(Xri ) ≠ sgn(Yri ) whenever
i) Ei holds

[p′1

...

p′k ].

4
ε2buf f δbuf
f
2
2
ρ δ k

2
, εbuf f δbuf
f k}),

(6.3)

Now for any 1 ≤ i ≤ k, observe

and ii) max{∣h∗ (Xri − Xr′ i )∣, ∣h∗ (Yri − Yr′i )∣} < δbuf f .

(6.4)

We know that Ei holds on at least k(ang(θ) − c4 (δbuf f + ∆′r )) coordinates. Next, we can upper bound the
number of coordinates for which (6.4) does not hold. Using the estimate (6.3), this number is given by
∥P ∗ h∥ℓ2 + ∥P ′∗ h∥ℓ2
2

2

2
δbuf
f

−2
2 2 3
≤ kεbuf f + δbuf
fρ δ k .

(6.5)

With the estimates (6.5) and (6.2), we find that for all pairs x, y with probability
1 − N 2 exp(−c6 min{
we have that

4
ε2buf f δbuf
f

ρ2 δ 2 k

2
2
, εbuf f δbuf
f k}) − exp(−δ k/2)

−2
2 2 2
′
k −1 ∥RAx, RAy∥H ≥ ang(x, y) − [εbuf f + δbuf
f δ ρ k + c3 (δbuf f + ∆r )].

The identical (symmetric) argument allows us to obtain the upper bound on the Hamming distance to
conclude that
−2
2 2 2
′
∣k −1 ∥RAx, RAy∥H − ang(x, y)∣ ≤ εbuf f + δbuf
f δ ρ k + c3 (δbuf f + ∆r ).

With these bounds, we find that binary embedding with cf inal δ distortion succeeds with probability 1 −
2 exp(−c6 δ 3 k/2) under the following conditions:
12

• εbuf f ≤ δ,
• δbuf f ≤ δ,
2
−1
• ρ2 k 2 ≤ δbuf
fδ ,
√
√
• Via ∆′r : ρδ k ≤ δ 2 i.e. ρ k ≤ δ,

• Via ∆′r : ρδk ≤ δ.
To satisfy these, pick δbuf f = ε√
buf f = δ. Furthermore, our initial assumptions (Condition 2.1) guarantee
that δ ≥ C0 ρk ≥ C0 max{ρ2 k 2 , ρ k} for a sufficiently large constant C0 > 0 which yields a total distortion
proportional to δ. Finally, the probability of success is
1 − N 2 exp(−c6 min{

δ4 3
, δ k}) − exp(−δ 2 k/2).
ρ2 k

Observing ρ2 k ≤ δ 2 /C02 (C0 > 1 is sufficient) and using the initial assumption C1 log N ≤ δ 3 k for a sufficiently
large constant C1 > 0 we can conclude. In particular pick C1 > 4/c6 . With these, we ensured that the
total distortion is cf inal δ for an absolute constant cf inal > 0 with the desired probability. Rescaling δ as
δ → c−1
f inal δ, we conclude with the advertised result in Theorem 2.2.

References
[1] Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast johnson-lindenstrauss transform.
In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 557–563. ACM, 2006.
[2] Petros T Boufounos and Richard G Baraniuk. 1-bit compressive sensing. In Information Sciences and Systems,
2008. CISS 2008. 42nd Annual Conference on, pages 16–21. IEEE, 2008.
[3] Jean Bourgain and Lior Tzafriri. Invertibility of ?large?submatrices with applications to the geometry of banach
spaces and harmonic analysis. Israel journal of mathematics, 57(2):137–224, 1987.
[4] Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and
algorithms. Information Theory, IEEE Transactions on, 61(4):1985–2007, 2015.
[5] Raja Giryes, Guillermo Sapiro, and Alex M Bronstein. Deep neural networks with random gaussian weights: A
universal classification strategy? arXiv preprint arXiv:1504.08291, 2015.
[6] Yunchao Gong and Svetlana Lazebnik. Iterative quantization: A procrustean approach to learning binary codes.
In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, pages 817–824. IEEE, 2011.
[7] Laurent Jacques. A quantized johnson–lindenstrauss lemma: The finding of buffon?s needle. Information Theory,
IEEE Transactions on, 61(9):5012–5027, 2015.
[8] Laurent Jacques, Jason N Laska, Petros T Boufounos, and Richard G Baraniuk. Robust 1-bit compressive sensing
via binary stable embeddings of sparse vectors. Information Theory, IEEE Transactions on, 59(4):2082–2102,
2013.
[9] Kishore Jaganathan, Samet Oymak, and Babak Hassibi. Sparse phase retrieval: Convex algorithms and limitations. In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pages 1022–1026.
IEEE, 2013.
[10] Felix Krahmer and Rachel Ward. New and improved johnson-lindenstrauss embeddings via the restricted isometry property. SIAM Journal on Mathematical Analysis, 43(3):1269–1281, 2011.
[11] Quoc Le, Tamás Sarlós, and Alex Smola. Fastfood-approximating kernel expansions in loglinear time. ICML,
2013.
[12] Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes. Springer
Science & Business Media, 2013.

13

[13] Samet Oymak and Ben Recht. Near-optimal bounds for binary embeddings of arbitrary sets. arXiv preprint
arXiv:1512.04433, 2015.
[14] Samet Oymak, Benjamin Recht, and Mahdi Soltanolkotabi. Isometric sketching of any set via the restricted
isometry property. arXiv preprint arXiv:1506.03521, 2015.
[15] Yaniv Plan and Roman Vershynin. Robust 1-bit compressed sensing and sparse logistic regression: A convex
programming approach. Information Theory, IEEE Transactions on, 59(1):482–494, 2013.
[16] Yaniv Plan and Roman Vershynin. Dimension reduction by random hyperplane tessellations. Discrete & Computational Geometry, 51(2):438–461, 2014.
[17] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural
information processing systems, pages 1177–1184, 2007.
[18] Mark Rudelson and Roman Vershynin. Hanson-wright inequality and sub-gaussian concentration. Electron.
Commun. Probab, 18(0), 2013.
[19] Joel A Tropp. On the conditioning of random subdictionaries. Applied and Computational Harmonic Analysis,
25(1):1–24, 2008.
[20] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices.
arXiv:1011.3027, 2010.

arXiv preprint

[21] Qifan Wang, Bin Shen, Shumiao Wang, Liang Li, and Luo Si. Binary codes embedding for fast image tagging
with incomplete labels. In Computer Vision–ECCV 2014, pages 425–439. Springer, 2014.
[22] Xinyang Yi, Constantine Caramanis, and Eric Price. Binary embedding: Fundamental limits and fast algorithm.
arXiv preprint arXiv:1502.05746, 2015.
[23] Felix X Yu, Aditya Bhaskara, Sanjiv Kumar, Yunchao Gong, and Shih-Fu Chang. On binary embedding using
circulant matrices. arXiv preprint arXiv:1511.06480, 2015.
[24] Felix X Yu, Sanjiv Kumar, Yunchao Gong, and Shih-Fu Chang. Circulant binary embedding. arXiv preprint
arXiv:1405.3162, 2014.

A

Standard results

Lemma A.1 Given vectors v, u, f (v) = ∥diag(u)v∥ℓ2 is ∥u∥ℓ∞ Lipschitz function.

Lemma A.2 (Lipschitz concentration of Gaussians) If f ∶ R n → R is an L-Lipschitz function, for a standard
Gaussian vector g P(∣f (g) − E[f (g)]∣ > t) ≤ 2 exp(−t2 /(2L2 )).

Lemma A.3 Let v1 , . . . , vk ∈ R n be vectors satisfying ∥vi ∥ℓ2 ≤ ℓ. Let V = [v1 . . . vk ]∗ and g ∼ N (0, In ). Then, we
have that
t2
t
2
2
P(∥V g∥ℓ2 ≥ ∥V ∥F + t) ≤ exp(−c min{
}).
,
2
∥V ∥F ∥V ∥2 ∥V ∥2

Proof Let V have singular value decomposition UL ΣUR∗ where Σ ∈ R k×k . UR∗ g ∼ g and UL does not affect the ℓ2
2
norm. Hence ∥UL ΣUR∗ ∥ℓ2 ∼ ∥Σg∥2ℓ2 which is a weighted sum of subexponentials where weights are at most ∥V ∥2 .
Denoting the ith weight by wi = σi (V )2 we have that
k

2
∑ wi = ∥V ∥F ,

i=1

sup ≤ ∥V ∥2 .

1≤i≤wi

Subject to these constraints, we are interested in finding ∑ki=1 wi2 . Observe that if a > b > c we have that (a + c)2 +
(b − c)2 > a2 + b2 . Consequently, without losing generality, we can assume that nonzero singular values are as large as
possible, namely ∥V ∥ so that there are

∥V ∥2
F
∥V ∥2
k

nonzero values equal to ∥V ∥.

2
∑ wi ≤

i=1

∥V ∥2F
∥V ∥4 = ∥V ∥2F ∥V ∥2 .
∥V ∥2

With this bound, Proposition 5.16 of [20] yields the desired result.

14

Lemma A.4 Let a, b be two unit vectors obeying max{∥a∥ℓ∞ , ∥b∥ℓ∞ } ≤ ρ. Let θ be the angle in between. Let
2ρ
b′ = b − aa∗ b. We have that ∥b̄′ ∥ℓ ≤ sin(θ)
.
∞

Proof Clearly ∥b′ ∥ℓ∞ ≤ ∥b∥ℓ∞ + ∥a∗ ba∥ℓ∞ ≤ 2ρ. On the other hand since the angle between is θ, ∥b′ ∥ℓ2 = sin(θ).

Lemma
A.5 Let x, x′ , y, y ′ be unit length vectors satisfying ∣x∗ y−x′∗ y ′ ∣ ≤ α. We have that ∣ang(x, y)−ang(x′ , y ′ )∣ ≤
√
5 α. We also have that for a unit vector x and a perturbation v, ang(x, x + v) ≤ 5 ∥v∥ℓ2 .
Proof Without losing generality, let θ = ang(x, y) and θ′ = ang(x′ , y) where 0 ≤ θ ≤ θ′ < π. We are given that
cos(θ) − cos(θ′ ) = ∫

θ

θ′

sin(x)dx ≤ α.

Using the fact that sin(x) is increasing over [0, π/2] and decreasing over [π/2, π], we have that
2∫

(θ ′ −θ)/2
0

sin(x)dx ≤ ∫

θ′

sin(x)dx.

θ

If θ′ − θ < π/2, using the fact that sin(x)/x is decreasing over [0, π/2]
2∫

(θ ′ −θ)/2
0

√
sin(x)dx ≥ (2 2π −1 )2 (θ′ − θ)2 ≥ 0.92 (θ′ − θ)2 .

√
(θ ′ −θ)/2
π/4
This implies 0.92 (θ′ − θ)2 ≤ α. Otherwise, α ≥ 2 ∫√
sin(x)dx ≥ 2 ∫0 sin(x)dx ≥ 0.5 Ô⇒
α ≥ 0.7. On the
0
√
other hand θ′ − θ < π which implies θ′ − θ < (π/0.7) α. Consequently θ′ − θ ≤ max{π/0.7, 1.2} α.
Suppose x is a unit length vector and x′′ be the projection of x on x′ . Clearly ∥x′ − x∥ℓ2 ≥ ∥x′′ − x∥ℓ2 and
√
ang(x′′ , x) = ang(x′ , x). ∥x′′ − x∥ℓ2 has a simple form namely it is equal to sin(θ). Now if θ < π/4, sin(θ) > 2 2π −1 θ
√
√
√
so that ang(x′ , x) ≤ 2 2π −1 ∥x′ − x∥ℓ2 . If θ > π/4, ∥x′ − x∥ℓ2 ≥ 1/2 and θ ≤ π which implies θ ≤ 2π ∥x − x′ ∥ℓ2 .

B

Results on random matrices

Lemma B.1 Let g ∈ R n be a standard Gaussian vector and E be an event over g that holds with probability p. We
have that
−1
2
E[∥g∥ℓ2 ∣E]P(E) ≤ (9n + 2 log p )p.
Setting p = n−3 yields right hand side is at most 15n−2 .

Proof Let r > 0 be the number for which P(∥g∥ℓ2 ≥ r) = p and L be the associated event. Then P(E ∩ L̄) = P(Ē ∩ L)
and
E[∥g∥2ℓ2 ∣E ∩ L̄] ≤ E[∥g∥2ℓ2 ∣Ē ∩ L].
This implies that

E[∥g∥2ℓ2 ∣E]p ≤ E[∥g∥2ℓ2 ∣L]p = ∫

∥g∥ℓ >r
2

∥g∥2ℓ2 dg.

Let a = ∥g∥ℓ2 and p(t) be the density function of a and Q(t) = P(a > t). Using Lipschitzness of ℓ2 norm, we have that
√
√
for t > n, Q(t) ≤ exp(−(t − n)2 ).
E[∥g∥2ℓ2 ∣L]p = ∫

a>r

a2 p(a)da = − ∫

We also have that

a>r

a2 dQ(a) = ∫

a>r

Q(a)da2 − [Q(a)a2 ]∞
r

=∫

a>r

Q(a)da2 + Q(r)r 2 .

√ 2
p(a)da = Q(r) ≤ exp(−(r − n) ).
√
√
√
which implies p ≤ exp(−(r − n)2 ) Ô⇒ r ≤ log p−1 + n. Construct an alternative distribution where p′ (a) = p(a)
√
√
√
√
√
for a ≤ r, p′ (a) = 0 for r < a ≤ log p−1 + n and Q′ (a) = exp(−(a − n)2 ) for a > log p−1 + n. This choice ensures
′
that Q (a) > Q(a) for all a ≥ 0 hence
∫

a>r

∫

a>r

a2 p′ (a)da = ∫

a>r

Q′ (a)da2 + Q′ (r)r 2 ≥ ∫

a>r

15

Q(a)da2 + Q(r)r 2 .

Consequently, we will use Q′ to upper bound the Gaussial tail. We have that
∫

a>r

a2 p′ (a)da = ∫

a>

Finally, we need to estimate the right hand side. For r ′ =
∫

a>r ′

2aQ′ (a)da = ∫

u>c

√
√
log p−1 + n

a2 p′ (a)da.

√
n + c and c ≥ 1, we have that

√
√
2( n + u) exp(−u2 /2)du = 7 n exp(−c2 /2).

We also have the estimate Q(r ′ )r ′2 ≤ 2(n + c2 ) exp(−c2 /2). Setting c =

√

log p−1 and p = n−3 we find that

E[∥g∥2ℓ2 ∣L]p ≤ (9n + 2 log p−1 )p ≤ 15n−2 .

n
Lemma B.2 (Infinity norm of random modulation) Let {vi }N
i=1 be a finite set of points. Let b ∈ R be
√ a vector
n
with independent Rademacher entries and let U ∈ R be the unitary Hadamard matrix where entries are ± 1/n. Let
wi = U diag(b)vi . With probability 1 − exp(−c0 log N ), for all 1 ≤ i ≤ N , we have that
√
√
log n + log N
.
sup ∥wi ∥ℓ∞ ≤
√
n
1≤i≤N

Proof Observe that wi = U diag(v
√ i )b hence each entry of wi is 2a weighted linear combination
√ of subgaussians where
the weights are Ujk vki = ±vki / n. In particular ∑n
n) subgaussian norm.
∣U
v
∣
=
1/n
hence
w
has
O(1/
ij
jk
ki
k=1
Consequently for any 1 ≤ j ≤ n
2
P(∣wij ∣ ≥ t) ≤ exp(−cnt /2).

N 1/2
Pick t = c′ ( log n+log
)
and apply a union bound over all 1 ≤ j ≤ n and all 1 ≤ i ≤ N to conclude.
n

n
be a vector
Lemma B.3 (Embedding most vectors) Let {vi }N
i=1 be a finite set of points. Let b ∈ R
√ with inn
dependent Rademacher entries and let U ∈ R be the unitary Hadamard matrix where entries are ± 1/n. Let
wi = U diag(b)vi . With probability 1 − p, for at least (1 − cp−1 n−3 )N points wi (1 ≤ i ≤ N ), we have that
√
log n
sup ∥wi ∥ℓ∞ ≤ C √ .
n
1≤i≤N

Proof Observe that wi = U diag(vi )b hence each entry of wi is a weighted linear combination of subgaussians where
√
√
2
the weights are Ujk vki = ±vki / n. In particular ∑n
k=1 ∣Ujk vki ∣ = 1/n hence wij has O(1/ n) subgaussian norm.
Consequently for any 1 ≤ j ≤ n
P(∣wij ∣ ≥ t) ≤ exp(−cnt2 ).

Pick t = c′ ( log(n)
)1/2 to ensure that P(∣wij ∣ ≥ t) ≤ c′′ n−4 . Applying a union bound over the entries, this ensures
n
′′ −3
P(∥wi ∥ℓ∞ ≥ t) ≤ c n . Let Ns be the number of wi obeying the bound ∥wi ∥ℓ∞ ≤ t. We have that
E[Ns ] ≥ 1 − c′′ n−3 .

Hence N − Ns is a nonnegative random variable obeying E[N − Ns ] ≤ c′′ n−3 . Applying Markov’s inequality P(N − Ns >
p−1 c′′ n−3 ) ≤ p.
∗
Lemma B.4 Let A be a random matrix with unit length
√ columns. Suppose E ∥A A − I∥ ≤ α. Let B = Adiag(α)
where α is a diagonal matrix whose entries lie between 1 ± ε and α is allowed to depend on A. We have that

E ∥B ∗ B − I∥ ≤ 2α + ε.

Proof Let φ = ∥A∗ A − I∥. We have that ∥B∥2 ≤ (1 + φ)(1 + ε) and σmin (B)2 ≥ (1 − φ)(1 − ε). Consequently
E[∥B∥ − 1] ≤ E[φ] + ε + E[φε], 1 − σmin (B) ≤ E[φ] + ε − E[φε].
2

2

16

C

Generalizations of Tropp’s “Incoherent Subdictionary Theorem”

Definition C.1 Φ ∈ R m×n is called a dictionary with coherence µ if columns of Φ have unit length and coherence is
defined as µ = supi≠j ∣φ∗i φj ∣ where φi is the ith column of Φ.
Definition C.2 (Restriction) R ∈ R m×m1 is called a restriction operator if AR ∈ R n×m1 is a matrix obtained by
selecting m1 columns of A for any A ∈ R n×m and any n ≥ 1. If R select m1 columns uniformly at random, we shall
call it random restriction. A random subdictionary of A is obtained by applying the restriction R to get AR.
Define ∥ ⋅ ∥1,2 norm of a matrix to be the largest ℓ2 norm of its columns. The next result will be beneficial for the
derivation.
Theorem C.3 (Theorem 8 of [19]) Let A be a matrix with N columns and let R be a restriction to m coordinates
chosen uniformly at random. Fix q ≥ 1. For any p ≥ max{2, 2 log(rankAR∗ ), q/2} we have that
√
√
∗ q 1/q
(E ∥AR ∥ ) ≤ 3 p∥A∥1,2 + m/N ∥A∥.
Observe that (a + b)q ≤ (2 max(a + b))q ≤ (2a)q + (2b)q hence

√
√
E ∥AR∗ ∥q ≤ (6 p∥A∥1,2 )q + (2 m/N ∥A∥)q .

The following is our variation of Tropp’s spectral norm bounds on incoherent subdictionaries.
Theorem C.4 Suppose Φ ∈ R n×2n is a random matrix such that all of its realizations are incoherent dictionaries
with√coherence µ. Pick a random subdictionary X ∈ R n×2k of Φ. Define the function f (R) = EΦ ∥X ∗ X − I∥. For
u ≥ 2 log n + 1, we have that
√
m
P R (f (R) ≥ c′ (u m(log m + 1)µ + ∥Φ∥2 )) ≤ exp(−u2 /4).
(C.1)
n
Proof The proof exactly follows the work by Tropp, namely Section 6 of [19]. We will only point out the main
differences as almost all of the argument overlaps. Let R be the random restriction for which X = ΦR. We first
establish the following result.
Theorem C.5 For q ≥ 2 log n + 1, we have that
∗

q 1/q

(ER (EΦ ∥X X − I∥) )

∗

q 1/q

≤ (ER,Φ ∥X X − I∥ )

√
m
2
≤ c( qm(log m + 1)µ + ∥Φ∥ ).
n

Proof For the sake of completeness, we repeat most of the arguments in [19]. First note that X ∗ X − I = RHR∗
where H = Φ∗ Φ − I. A standard symmetrization argument (Theorem 9 of [19]) ensures that there exists a submatrix
Ĥ ∈ R n/2×n/2 (where columns and rows correspond to disjoint subsets) and restrictions R1 , R2 such that
∗

q 1/q

(ER ∥X X − I∥ )

≤ 2(

q 1/q

max

ER1 ,R2 ∥R1 ĤR2 ∥ )

max

ER1 ,R2 ∥R1 ĤR2 ∥ .

m1 +m2 =m

.

(C.2)

Exponentiating both sides, this implies
∗

q

q

ER ∥X X − I∥ ≤ 2

m1 +m2 =m

q

Hence, we shall upper bound the right-hand side. This will be done in two steps by first taking expectation over R2
and then R1 .
ER1 ,R2 ∥R1 ĤR2 ∥q = ER1 ER2 ∥R1 ĤR2 ∥q .
Applying Theorem C.3 with p = max{2, 2 log(m/2) + 1, q/2} we have that
√
√
q
q
q
ER2 ∥R1 ĤR2 ∥ ≤ (6 p∥R1 Ĥ∥1,2 ) + ( 8m2 /n∥R1 Ĥ∥) .

√
Similar to Tropp, the coherence assumption ensures that ∥R1 Ĥ∥1,2 ≤ µ m to obtain
√
√ √
ER2 ∥R1 ĤR2 ∥q ≤ (6 pµ m)q + ( 8m2 /n∥R1 Ĥ∥)q .

17

The remaining task is to upper bound E ∥R1 Ĥ∥q . Reapplying Theorem C.3, we have that
√
√ √ q
q
q
∗ ∗ q
E ∥R1 Ĥ∥ = E ∥Ĥ R1 ∥ ≤ (6 pµ n) + ( 8m1 /n∥Ĥ∥) .
The combination of the last two inequalities, yields that, for any Φ obeying the coherence and spectral norm bounds,
we have
√
√
√
√ √ q
√ √ q
q
q
ER1 ,R2 ∥R1 ĤR2 ∥ ≤ (6 pµ m) + ( 8m2 /n6 pµ n) + ( 8m2 /n 8m1 /n∥Ĥ∥)
√
m
q
q
≤ (c1 pmµ) + (c2 ∥Ĥ∥) .
n
Since this holds for all realizations of Φ, we can take an additional expectation over Φ to conclude
√
√
m
m
ER,Φ ∥X ∗ X − I∥q ≤ (c1 pmµ)q + (c2 ∥Ĥ∥)q Ô⇒ (ER,Φ ∥X ∗ X − I∥q )1/q ≤ c( pmµ + ∥Ĥ∥).
n
n
For q ≥ 1, this also implies that

√
m
(ER (EΦ ∥X ∗ X − I∥)q )1/q ≤ (ER,Φ ∥X ∗ X − I∥q )1/q ≤ c( pmµ + ∥Ĥ∥).
n

Picking p = q(log m/2 + 1), and using the estimate ∥Ĥ∥ ≤ ∥H∥ ≤ ∥Φ∗ Φ∥ + 1 ≤ 2∥Φ∥2 we obtain that
√
m
(ER (EΦ ∥X ∗ X − I∥)q )1/q ≤ (ER,Φ ∥X ∗ X − I∥q )1/q ≤ c( qm(log m + 1)µ + ∥Φ∥2 ).
n
Now letting f (R) = EΦ ∥X ∗ X − I∥ and applying Proposition 10 of [19], for u ≥ 1, we obtain that
√
m
P(f (R) ≥ c′ (u m(log m + 1)µ + ∥Φ∥2 )) ≤ exp(−u2 /4)
n
which is the desired concentration bound.

C.1

Asymmetric version of Tropp’s incoherent subdictionary result

We first prove the following variation of Theorem 25 of [19]. This result assumes the matrix to have even dimensions
but the odd case can be shown with minimal modification of the proof strategy. The proof exactly follows the
argument of Tropp however we will provide it here for the sake of completeness. We remark that Tropp’s result was
based on more classical results due to Bourgain and Tzafriri [3, 12].
Theorem C.6 Let A be a 2n × 2n matrix with a 0 diagonal. Let R be a restriction to m random coordinates. Fix
q ≥ 1. There exists a partition of the coordinates {1, 2, . . . , 2n} into two blocks T1 and T2 with N elements each so
that
E ∥RAR∗ ∥q ≤ 2q max E ∥R1 AT1 ×T2 R2 ∥q .
m1 +m2 =m

Proof We prove the result for q = 1. Identical argument applies to q > 1 case. Let aij denote the ijth coordinate of
the matrix A and ei denote the ith vector of the standard basis. Define the matrices Bjk = ajk ej e∗k . δ ∈ {0, 1}2n , be
a vector which has exactly m components equal to 1. Then, we have
RAR∗ = ∑ δj δk Bjk
j≠k

We wish to bound the expectation

M = Eδ ∥ ∑ δj δk Bjk ∥
j≠k

Let η ∈ R

2n

be a random vector with exactly n coordinates equal to 1. For j ≠ k, we have that
Eη [ηj (1 − ηk ) + ηk (1 − ηj )] =

18

n
.
2n − 1

(C.3)

Now, based on these, applying Jensen’s inequality, we have the following list of inequalities
M=

2n − 1
Eδ ∥ ∑ Eη [ηj (1 − ηk ) + ηk (1 − ηj )]δj δk Bjk ∥
n
j≠k

< 2 E δ Eη ∥ ∑ [ηj (1 − ηk ) + ηk (1 − ηj )]δj δk Bjk ∥
j≠k

< 2[Eδ Eη ∥ ∑ ηj (1 − ηk )δj δk Bjk ∥ + Eδ Eη ∥ ∑ ηk (1 − ηj )δj δk Bjk ∥]
j≠k

j≠k

< 4 E δ Eη ∥ ∑ ηj (1 − ηk )δj δk Bjk ∥
j≠k

It follows that there exists a 0 − 1 vector η ∗ containing exactly n 1s such that
M < 4 Eδ ∥ ∑ ηj (1 − ηk )δj δk Bjk ∥
∗

∗

j≠k

Note that this vector η ∗ partitions the set {1, 2, . . . , 2n} into two parts T1 , T2 each containing N elements. T1
corresponds to the coordinates ηi = 1 and T2 corresponds to the coordinates ηi = 0. Calling these parts T1 , T2 , we can
rewrite the inequality as
M < 4 E δ ∥ ∑ δj δk Bjk ∥
j∈T1 ,k∈T2

Next, let number of active coordinates of δ over T1 be m1 . Observe that conditioned on the choice of T1 and m1 , the
m1 and m − m1 active coordinates of δ are distributed uniformly at random over T1 and T2 . This is due to the fact
that δ is independent of η ∗ . With this, the inequality takes the advertised form
M < 4 E m1 ,m2 ∥R∗1 AT1 ×T2 R2 ∥ ≤

max

m1 +m2 =m

4 E ∥R∗1 AT1 ×T2 R2 ∥

Using Theorem C.6 and repeating the proof of Theorem C.4 line by line we can conclude with the following result.
Theorem C.7 Suppose Φ ∈ R n×2n is a random matrix such that all of its realizations are incoherent dictionaries
with coherence µ. Pick a random subdictionary X1 ∈ R n×k from first n columns of Φ. Pick the same
√ k coordinates
from the second n columns of Φ and form X2 . Define the function f (R) = EΦ ∥X1∗ X2 ∥. For u ≥ 2 log n + 1, we
have that
√
m
(C.4)
P R (f (R) ≥ c′ (u m(log m + 1)µ + ∥Φ∥2 )) ≤ exp(−u2 /4).
n
Proof Denote the first and second n columns of Φ by Φ1 and Φ2 respectively and set Θ = Φ∗1 Φ2 . Let R ∈ R n×k be a
random restriction. Observe that
EΦ ∥X1∗ X2 ∥ = EΦ,R ∥R∗ Φ∗1 Φ2 R∥ = EΦ,R ∥R∗ ΘR∥
Next, split the diagonal and off-diagonal entries of Θ and apply the argument in Theorem C.4 where we replace the
inequality (C.2) with the estimate of Theorem C.6.

19

