arXiv:1801.04414v1 [cs.DS] 13 Jan 2018

Tight Bounds for ℓp Oblivious Subspace Embeddings
Ruosong Wang
Carnegie Mellon University

David P. Woodruff
Carnegie Mellon University

ruosongw@andrew.cmu.edu

dwoodruf@cs.cmu.edu

Abstract
An ℓp oblivious subspace embedding is a distribution over r × n matrices Π such that for
any fixed n × d matrix A,
Pr[for all x, kAxkp ≤ kΠAxkp ≤ κkAxkp ] ≥ 9/10,
Π

where r is the dimension of the embedding, κ is the distortion of the embedding, and for an
P
1/p
n-dimensional vector y, kykp = ( ni=1 |yi |)
is the ℓp -norm. Another important property is the
sparsity of Π, that is, the maximum number of non-zero entries per column, as this determines
the running time of computing Π · A. While for p = 2 there are nearly optimal tradeoffs in terms
of the dimension, distortion, and sparisty, for the important case of 1 ≤ p < 2, much less was
known. In this paper we obtain nearly optimal tradeoffs for ℓp oblivious subspace embeddings
for every 1 ≤ p < 2. Our main results are as follows:
1. We show for every
 1 ≤ p < 2, any oblivious
 subspace embedding with dimension r has
1
distortion κ = Ω
. When r = poly(d) ≪ n in applications, this
( d1 )1/p ·log2/p r+( nr )1/p−1/2
gives a κ = Ω(d1/p log−2/p d) lower bound, and shows the oblivious subspace embedding
of Sohler and Woodruff (STOC, 2011) for p = 1 and the oblivious subspace embedding of
Meng and Mahoney (STOC, 2013) for 1 < p < 2 are optimal up to poly(log(d)) factors.

2. We give sparse oblivious subspace embeddings for every 1 ≤ p < 2 which are optimal in
dimension and distortion, up to poly(log d) factors. Importantly for p = 1, we achieve
r = O(d log d), κ = O(d log d) and s = O(log d) non-zero entries per column. The best
previous construction with s ≤ poly(log d) √
is due to Woodruff and Zhang (COLT, 2013),
giving κ = Ω(d2 poly(log d)) or κ = Ω(d3/2 log n · poly(log d)) and r ≥ d · poly(log d); in
contrast our r = O(d log d) and κ = O(d log d) are optimal up to poly(log(d)) factors even
for dense matrices.
We also give (1) nearly-optimal ℓp -subspace embeddings with an expected 1 + ǫ number of
non-zero entries per column for arbitrarily small ǫ > 0, and (2) the first oblivious subspace
embeddings for 1 ≤ p < 2 with O(1)-distortion and dimension independent of n. Oblivious
subspace embeddings are crucial for distributed and streaming environments, as well as entrywise
ℓp low rank approximation. Our results give improved algorithms for these applications.

1

Introduction

An ℓp oblivious subspace embedding with distortion κ is a distribution over r ×n matrices Π such
that for any given A ∈ Rn×d , with constant probability, kAxkp ≤ kΠAxkp ≤ κkAxkp simultaneously
for all x ∈ Rd . The goal is to minimize r, κ and the time to calculate ΠA.
Oblivious subspace embeddings have proven to be an essential ingredient for approximately
solving numerical linear algebra problems, such as regression and low-rank approximation. Sárlos
[27] first used ℓ2 oblivious subspace embeddings to solve ℓ2 -regression and Frobenius-norm lowrank approximation. To see the connection, suppose one wish to solve the ℓ2 -regression problem
argminx kAx − bk2 in the overconstrained setting, i.e., A ∈ Rn×d and b ∈ Rn where n ≫ d.
Sárlos showed that in order to solve this problem approximately, it suffices to solve a much smaller
instance argminx kΠAx − Πbk2 , provided Π is an ℓ2 oblivious subspace embedding. Sárlos further
showed that using the Fast Johnson-Lindenstrauss Transform in [1] as the ℓ2 oblivious subspace
embedding with κ = 1 + ε, one can get a (1 + ε)-approximate solution to the ℓ2 -regression problem
in O(nd log d) + poly(d/ε) time, which is a substantial improvement over the standard SVD-based
approach which runs in O(nd2 ) time.
Subsequent to the work of Sárlos, the “sketch and solve” approach became an important way to
solve numerical linear algebra problems. We refer interested readers to the monograph of Woodruff
[30] for recent developments.
The bottleneck of Sárlos’s approach is the step to calculate ΠA, which requires Ω(nd log d)
time due to the structure of the Fast Johnson-Lindenstrauss Transform. Although this is already
nearly-optimal for dense matrices, when A is large and sparse, one may wish to solve the problem
faster than O(nd) time by exploiting the sparsity of A. Clarkson and Woodruff [12] showed that
there exist ℓ2 oblivious subspace embeddings with r = poly(d/ε) rows, s = 1 non-zero entries per
column, and κ = 1 + ε. The property that s = 1 is significant, since it implies calculating ΠA
requires only O(nnz(A)) time, where nnz(A) is the number of non-zero entries of A. In fact, the
oblivious subspace embedding they used is the CountSketch matrix from the data stream literature
[8]. By using the the CountSketch embedding in [12], one can reduce an ℓ2 -regression instance of
size n × d into a smaller instance of size poly(d/ε) × d in O(nnz(A)) time. The original proof in
[12] used a technique based on splitting coordinates by leverage scores. The number of rows can be
further reduced to r = O((d/ε)2 ) using the same construction and a finer analysis based on second
moment method, shown independently in [22] and [23].
One may wonder if it is possible to further reduce the number of rows in the CountSketch
embedding, since this affects the size of the smaller instance to solve. In [24], Nelson and Nguy˜ên
showed that any ℓ2 oblivious subspace embedding with constant distortion and s = 1 non-zero
entries per column requires Ω(d2 ) rows. Although this rules out the possibility of further reducing
the number of rows in the CountSketch embedding, this lower bound can be circumvented by
considering embeddings with s > 1 non-zero entries in each column. This idea is implemented by
the same authors in [23], obtaining a result showing that for any B > 2, for r about B · d log8 d/ε2
and s about log3B d/ε, one can achieve an ℓ2 oblivious subspace embedding with κ = 1 + ε. The
bound on r and s was further improved in [13] (see also [6]), where Cohen showed that for any
B > 2, it suffices to have r = O(B · d log d/ε2 ) and s = O(logB d/ε). Cohen’s result matches the
lower bound in [25] up to a multiplicative log d factor in the number of rows.
Another line of research focused on the case when p 6= 2, as the corresponding regression
and low rank approximation problems are often considered to be more robust, or less sensitive to
outliers. When p = 1, using Cauchy random variables, Sohler and Woodruff [28] showed there
1

exist ℓ1 oblivious subspace embeddings with O(d log d) rows and κ = O(d log d). This approach
was generalized by using p-stable random variables in work of Meng and Mahoney [22] to ℓp -norms
when 1 < p < 2, where they showed there exist ℓp oblivious subspace embeddings with O(d log d)
rows and κ = O (d log d)1/p . Unlike the case when p = 2, due to the large distortion incurred
in such upper bounds, one cannot directly get a (1 + ε)-approximate solution to the ℓp -regression
problem by solving argminx kΠAx − Πbkp . A natural question then, is whether it is possible to
obtain (1 + ε)-distortion with ℓp oblivious subspace embeddings; prior to our work there were no
lower bounds ruling out the simplest of algorithms for p 6= 2: (1) compute ΠA and Πb, and (2)
output argminx kΠAx − Πbkp .
Although it was unknown if better oblivious subspace embeddings exist for p 6= 2 prior to our
work, ℓp oblivious subspace embeddings still played a crucial role in solving ℓp -regression problems
in earlier work, since they provide a way to precondition the matrix A, which enables one to
further apply non-oblivious (sampling-based) subspace embeddings. We refer interested readers to
Chapter 3 of [30] and references therein for further details. Recent developments in entrywise ℓp lowrank approximation [29] also used ℓp oblivious subspace embeddings as an important ingredient.
Furthermore, such ℓ1 oblivious subspace embeddings are the only known way to achieve singlepass streaming algorithms for ℓ1 -regression (see, e.g., Section 5 of [28], where it is shown how to
implement the preconditioning and sampling in parallel in a single pass), a model that has received
considerable interest for linear algebra problems (see, e.g., [11]). We note that recent algorithms for
ℓp -regression based on Lewis weight sampling require at least Ω(log log n) passes in the streaming
model.
Due to these applications, speeding up the computation of ΠA for ℓp oblivious subspace embeddings is an important goal. In [10], Clarkson et al. combined the idea of Cauchy random variables
and Fast Johnson-Lindenstrauss Transforms to obtain a more structured family of subspace embeddings, which enables one to calculate ΠA in O(nd log n) time. Meng and Mahoney [22] showed
e 5 ) rows and s = 1
that when 1 ≤ p < 2, there exist ℓp oblivious subspace embeddings with r = O(d
e 3/p ). The structure of the embedding
non-zero entries per column, where the distortion κ = O(d
by Meng and Mahoney is very similar to the CountSketch embedding by Clarkson and Woodruff
[12]. In fact, to prove the distortion bound, Meng and Mahoney also used techniques of splitting
coordinates based on leverage scores.
Inspired by the technique by Andoni in [2], which used exponential random variables to estimate
the ℓp -norm of a data steam, Woodruff and Zhang [31] improved the embedding given in [22]. They
e
showed there exist ℓ1 oblivious subspace embeddings with r = O(d)
rows
√ and s = polylog(d)
2
1.5
e
e
non-zero entries per column, where the distortion κ = min{O(d ), O(d ) log n}. Note that to
e 2 ) or
achieve such
a small polylogarithmic sparsity, the distortion κ had to either increase to O(d
√
1.5
e
to O(d
) log n, the latter also depending on n.
The above works leave many gaps in our understanding on the tradeoffs between dimension,
distortion, and sparsity for ℓp oblivious subspace embeddings. For instance, it is natural to ask what
the optimal distortion bound for ℓp oblivious subspace embeddings is when 1 ≤ p < 2, provided that
the number of rows r = poly(d). Results in [28, 22] showed that κ = O (d log d)1/p is achievable.
Is this optimal? Also, it is unknown whether there exist sparse ℓp oblivious subspace embeddings

e
e d1/p . In this paper, we resolve these questions.
with dimension O(d)
and distortion κ = O

2

1.1

Our Results

Distortion Lower Bound.
embeddings, when 1 ≤ p < 2.

We first show a distortion lower bound for ℓp oblivious subspace

Theorem 1.1. For 1 ≤ p < 2, if a distribution over r × n matrices Π is an ℓp oblivious subspace
embedding, then the distortion
!
1
.
κ=Ω


2/p
1 1/p
r 1/p−1/2
·
log
r
+
d
n

When 1 ≤ p < 2 and r = poly(d), the denominator of the lower bound is dominated by the
r term, provided n is large enough. In that case, our lower bound is Ω(d1/p log−2/p d).
It is shown in [28] (for p = 1) and Theorem 6 in [22] (for 1 < p < 2) that there
 exist ℓp oblivious
1/p . Our lower bound
subspace embeddings with r = O(d 
log d) rows
and
distortion
κ
=
O
(d
log
d)


1 1/p
· log2/p
d

matches these results within an O log3/p d factor. Thus, our lower bound is nearly-optimal for
r = poly(d) (which is the main regime of interest in the above applications).
The dependence on (r/n)1/p−1/2 reflects the fact that
• When the number of rows r = n, one can get a trivial ℓp oblivious subspace embedding with
κ = 1, i.e., the identity matrix I;

• As p → 2, there exist ℓ2 oblivious subspace embeddings [27, 12, 22, 23, 6, 13] with κ = 1 + ε
and r = poly(d/ε), where ε can be an arbitrarily small constant.
It is possible that the log2/p r factor (in the (1/d)1/p ·log2/p r term) could be somewhat improved.
However, we show that some dependence on r is in fact necessary.
Theorem 1.2 (Informal version of Theorem 3.5). For 1 ≤ p < 2, there exists an ℓp oblivious
subspace embedding over exp(exp(O(d))) × n matrices Π, where the distortion κ is a constant.
Even though Theorem 1.2 has a doubly exponential dependence on d in the number of rows, it
is the first ℓp oblivious subspace embedding with constant distortion, when 1 ≤ p < 2 and r does
not depend on n. This new embedding suggests that it is impossible to get a lower bound of
!
1
κ=Ω

1/p−1/2 ,
1 1/p
+ nr
d
i.e., the


1 1/p
d

term should have some dependence on r.

New ℓp oblivious subspace embeddings. We next show there exist sparse ℓp oblivious subspace embeddings with nearly-optimal distortion.
Theorem 1.3 (Summary of Theorem 4.1, 4.2, 5.1 and 5.2.). For 1 ≤ p < 2, there exist ℓp oblivious
subspace embeddings over r × n matrices Π with s non-zero entries per column and distortion κ,
where
1. When p = 1,
3

(a) r = O(d2 ), s = 2 and κ = O(d); or
(b) For sufficiently large B, r = O(B · d log d), s = O(logB d) and κ = O(d logB d).

2. When 1 < p < 2, κ = O (d log d)1/p ,
(a) r = O(d2 ), s = 2; or

(b) For sufficiently large B, r = O(B · d log d), s = O(logB d).
Notably, the distortion of our embeddings is never worse than the dense constructions in [28, 22].
Also, when p = 1, if we set r = O(d2 ) (Case 1(a)) or r = O(d1+η ) for any constant η > 0 (Case
1(b)), then the distortion can be further improved to O(d). This is the first known ℓ1 oblivious
subspace embedding with r = poly(d) rows and distortion κ = o(d log d). We remark that by using
the dense construction in [28], it is also possible to reduce the distortion to O(d) by increasing the
number of rows.
Similar to the OSNAP embedding in [23], our results in Case 1(b) and Case 2(b) provide a
tradeoff between the number of rows and the number of non-zero entries in each column.
Sparser ℓp oblivious subspace embeddings. Finally, we show that the sparsity of Case 1(a)
and Case 2(a) in Theorem 1.3 can be further reduced by using two different approaches.
The first approach is based on random sampling, which leads to the following theorem.
Theorem 1.4 (Summary of Theorem 6.1 and 6.2). For 1 ≤ p < 2 and any constant 0 < ε < 1,
there exists an ℓp oblivious subspace embedding over O(d2 ) × n matrices Π where each column of
Π has at most two non-zero entries and 1 + ε non-zero entries in expectation, and the distortion
κ = O(d) (when p = 1) or κ = O (d log d)1/p (when 1 < p < 2).

The second approach is based on the construction in [22] and a truncation argument, which
leads to the following theorem.
Theorem 1.5 (Summary of Theorem 6.5 and 6.6). For 1 ≤ p < 2, there exists an ℓp oblivious
e 4 ) × n matrices Π where each column of Π has a single non-zero entry
subspace embedding over O(d
1/p
e
and distortion κ = O(d ).

It has been shown in [24] that for any distribution over r × n matrices Π with s = 1 nonzero entries per column, if for any fixed matrix A ∈ Rn×d , rank(ΠA) = rank(A) with constant
probability, then Π should have r = Ω(d2 ) rows. Since oblivious subspace embeddings with finite
distortion always preserve the rank, this lower bound can also be applied. We show also that this
lower bound holds even if the columns of Π have 1 + ε non-zero entries in expectation for a constant
0 < ε < 1, thereby showing Theorem 1.4 is optimal.
We leave it as an open question to obtain ℓp oblivious subspace embedding with r = O(d2 ) rows,

e d1/p ,
s = 1 non-zero entries in every column (as opposed to 1 + ε in expectation), and κ = O
or prove a stronger lower bound. If one insists on having s = 1 non-zero entries per column, then
e 4 ).
Theorem 1.5 can be applied, at the cost of increasing the number of rows to O(d

4

1.2

Comparison with Previous Work

In order to compare our results with previous work, it is crucial to realize the difference between
oblivious embeddings and non-oblivious embeddings. An oblivious subspace embedding Π is a
universal distribution over Rr×n , which does not depend the given matrix A ∈ Rn×d . A nonoblivious subspace embedding, however, is a distribution that possibly depends on the given matrix
A. Most known non-oblivious subspace embeddings involve importance sampling according to the
leverage scores or Lewis weights of the rows, and so are inherently non-oblivious. We refer the
interested reader to [20] for an excellent survey on leverage scores and [19, 14, 15] for recent
developments on non-oblivious subspace embeddings.
Previous impossibility results for dimension reduction in ℓ1 [18, 7, 9] are established by creating
a set of O(n) points in Rn and showing that any (non-oblivious) embedding on them incurs a large
distortion. In this paper, we focus on embedding a d-dimensional subspace of Rn into Rpoly(d) using
oblivious embeddings. We stress that O(n) points in a d-dimensional subspace have a very different
structure from O(n) arbitrary points in Rn . Previous results [15] showed that any d-dimensional
−2
subspace in Rn can be embedded into RO(d log dε ) with (1 + ε) distortion in ℓ1 using non-oblivious
linear embeddings, where ε > 0 is an arbitrarily small constant. Here the subspace structure is
critically used, since Charikar and Sahai [9] showed that there exist O(n) points such that any linear
embedding Rn → Rd must incur a distortion of Ω(n/d), even for non-oblivious linear embeddings.
Our hardness result in Theorem 1.1 establishes a separation between oblivious and non-oblivious
subspace embeddings in ℓp when 1 ≤ p < 2. This result suggests that in order to construct a
subspace embedding with (1+ε) distortion, it is essential to use non-oblivious subspace embeddings.
Although our main focus in this paper is to understand oblivious subspace embeddings, we
remark that our technique for proving the hardness result in Theorem 1.1 can also be applied to
embed any d points in Rn into Rpoly(d) in ℓp using oblivious linear embeddings, when 1 ≤ p < 2. In
particular, it is possible to reproduce the result by [9] using our techniques, although in a weaker
setting where the embeddings are oblivious.

1.3

Applications of Our Subspace Embeddings

Using that sparse ℓp oblivious subspace embeddings in Theorem 1.3, we obtaine improvements
to many related problems. We list a few examples in this section.
ℓp -regression in the distributed model. The ℓp -regression problem in the distributed model
is studied in [31], where there are k clients C1 , . . . , Ck and one central server. Each client has a
disjoint subset of the rows of a matrix [A, b], where A ∈ Rn×d and b ∈ Rn . There is a 2-way
communication channel between the central server and the clients, and the goal of the server is to
communicate with the k clients to solve the ℓp -regression problem argminx kAx − bkp .
In [31], when 1 ≤ p < 2, the authors devised an algorithm with total communication cost

O kd2+η + d5 log2 d + d3+p log(1/ε)/ε2 ,
where η > 0 is an arbitrarily small constant. Using our new oblivious subspace embedding in
Theorem 1.3, the total communication cost can be further reduced to


O kd2 log d + (d log d)2−p/2 d3 + d3+p log(1/ε)/ε2 ,
5

while the total running time of the whole system remains unchanged. This leads to a (d log d)p/2
improvement to the second term of the communication cost.
ℓp -regression in the streaming model. Using dense Cauchy embeddings and a sampling data
structure from [3], a single-pass streaming algorithm for ℓ1 -regression argminx kAx − bk1 was designed in [28]. In order to get a (1+ε)-approximate solution to the regression problem, the algorithm
uses poly(dε−1 log n) bits of space, where A ∈ Rn×d and b ∈ Rn . The total running time of the
algorithm, however, is O(nnz(A) · d + poly(dε−1 log n)).
By replacing the dense Cauchy embedding with our new oblivious subspace embeddings in
e
Theorem 1.3, the total running time can be further improved to O(nnz(A))
+ poly(dε−1 log n) while
the space complexity remains unchanged. We note that using earlier sparse Cauchy embeddings
[22] would also give such a running time, but with a significantly worse poly(dε−1 log n) factor. The
same approach can also be applied to design input-sparsity time algorithms for ℓp -regression in the
streaming model when 1 < p < 2.
Entrywise ℓp low rank approximation. Given a matrix A ∈ Rn×d and approximation factor
b for which
α, the goal of the ℓ1 -low rank approximation problem is to output a matrix A
b 1 ≤α·
kA − Ak

min

rank-k matrices A′

kA − A′ k1 ,

where k · k1 is the entrywise ℓ1 -norm.
In [29], the authors devised an algorithm that runs in T = O (nnz(A) + (n + d) · poly(k)) time
to solve this problem, with α = poly(k) · log d. The exact expression of the poly(k) factor in
the approximation factor α and the running time T , depends on the number of rows r and the
distortion κ of the ℓ1 oblivious subspace embedding used. Both poly(k) factors can be directly
improved by replacing the sparse Cauchy embedding [22], which is originally used in [29], with
our new oblivious subspace embeddings in Theorem 1.3. This improvement also propagates to
other problems considered in [29] such as ℓp -low rank approximation, entrywise ℓp -norm CUR
decomposition and ℓp -low rank approximation in distributed and streaming models.
Quantile Regression.
to solve
where ρτ (b − Ax) =

Pn

Given a matrix A ∈ Rn×d and b ∈ Rn , the goal of quantile regression is

i=1 ρτ ((b

argminx ρτ (b − Ax),
− Ax)i ) and for any z ∈ R,
(
τz
z≥0
.
ρτ (z) =
(τ − 1)z z < 0

Here τ is a parameter in (0, 1).
An efficient algortihm to calculate a (1 + ε)-approximate solution to quantile regression was
proposed in [32]. Using their approach, one can reduce a quantile regression instance of size n × d
to a smaller instance of size O(poly(d)ε−2 log(1/ε)) × d in O(nnz(A)) + poly(d) time. By replacing
the sparse Cauchy embedding, which is used in the conditioning step of their algorithm, with our
new oblivious subspace embeddings in Theorem 1.3, the poly(d) term in the running time can be
directly improved.
6

1.4

Our Techniques

Distortion lower bound. We use the case when p = 1 to illustrate our main idea for proving
our distortion lower bounds. We start with Yao’s minimax principle which enables us to deal only
with deterministic embeddings. Here our goal is to construct a distribution over matrices A ∈ Rn×d
such that for any Π ∈ Rr×n , if
1
kAxk1 ≤ kΠAxk1 ≤ kAxk1
κ

(1)

e
holds simultaneously for all x ∈ Rd with constant probability, then κ = Ω(d).
Roughly speaking, our proof is based on the crucial observation that, the histogram of the ℓ1 norm of columns in the deterministic embedding Π should look like that of a discretized standard
Cauchy distribution. I.e., there are at most 2i columns in Π with ℓ1 -norm larger than Θ((n/d)2−i ).
This is because if we choose a matrix A ∈ Rn×d such that each column contains (n/d)2−i non-zero
entries at random positions and all these (n/d)2−i non-zero entries are i.i.d. sampled from the
standard Gaussian distribution N (0, 1), then for each column in A, the ℓ1 -norm of that column
is Θ((n/d)2−i ) with constant probability. On the other hand, if the embedding Π contains more
than 2i columns with ℓ1 -norm larger than Θ((n/d)2−i ), then with constant probability, there exists
some i ∈ [n] and j ∈ [d] such that Ai,j ∼ N (0, 1) and the i-th column of Π has ℓ1 -norm larger than
Θ((n/d)2−i ). In that case, it can be shown that after projection by Π, the j-th column of A has
ℓ1 -norm larger than Θ((n/d)2−i ), which violates the condition in (1).
e
In order to prove κ = Ω(d),
let c ∈ Rn be a vector whose entries are all i.i.d. sampled from
N (0, 1). With constant probability kck1 = Ω(n). On the other hand, the constraint we put on the
e
e
histogram of the ℓ1 -norm of columns in Π implies that kΠck1 = O(n/d)
and hence κ = Ω(d).
A
−2
more refined analysis in Section 3.1 shows that κ = Ω(d log r) when n ≫ r.
In order to show that the dependence on r in the lower bound is necessary, we construct an ℓ1
oblivious subspace embedding with exp(exp(O(d))) rows and constant distortion. The construction
itself is the same as the dense construction in [28]. Unlike previous approaches [28, 22, 31], we do
not use the existence of Auerbach basis to prove the dilation bound. Our analysis is based on
tighter tail bounds on sum of absolute values of independent standard Cauchy (and also p-stable)
random variables in Lemma 2.10 and 2.12. Let {Xi } be R = exp(exp(O(d))) independent standard
Cauchy random variables, based on the tighter tail bounds, it can be shown that with probability
1 − exp(−Ω(d)),
R
X
|Xi | = Θ(R log R),
i=1

which enables us to use standard net argument to prove the constant distortion bound. The formal
analysis is given in Section 3.2.

New ℓp oblivious subspace embeddings. For ease of notation, here we focus on p = 1.
Before getting into our results, we first review the construction in [22] and its analysis. The
e 5 ) rows. In each column, there is a single non-zero entry
sparse Cauchy embedding in [22] has O(d
e
which is sampled from the standard Cauchy distribution. The O(d)
dilation bound follows the
standard approach [28] of using the existence of Auerbach basis and upper tail bounds for dependent
standard Cauchy random variables. The contraction bound is based on the technique of splitting
coordinates, which was first proposed in [12] to analyze the CountSketch embedding. A coordinate
7

is heavy if its ℓ1 leverage score is larger than 1/d and light otherwise. For any vector y = Ax,
if light coordinates contribute more to the ℓ1 -norm of y, then standard concentration bounds and
Cauchy lower tail bounds imply a constant distortion. If heavy coordinates contribute more to
the ℓ1 -norm, since there will be at most O(d2 ) heavy coordinates and the embedding has Ω(d4 )
rows, all the heavy coordinates will be perfectly hashed. An Ω d−2 contraction bound follows by
setting up a global event saying that the absolute values
of all the O(d2 ) standard Cauchy random

variables associated with heavy coordinates are Ω d−2 , which holds with constant probability.
Although the dilation bound seems to be tight, the contraction bound can be improved. Indeed,
the ℓ1 -norm of columns in the embedding of [22] almost follows the histogram predicted by our
lower bound argument, except for the lower tail part. As predicted by our lower bound argument,
e
for an embedding Π which has the optimal κ = O(d)
distortion, the ℓ1 -norm of each column in Π
should be larger than a constant. On the hand, the standard Cauchy distribution is heavy-tailed
in both directions1 . This leads to the idea of truncation, which is formalized in Section 6.2. The
rough idea is that we make sure the absolute values of the standard Cauchy random variables are
never smaller than a constant and thus the contraction bound can be improved to be a constant. It
is shown in Corollary 6.4 that standard Cauchy random variables are still “approximately 1-stable”
after truncation, which enables one to use Cauchy tail inequalities to analyze the dilation bound.
However, even though the distortion bound of this new embedding is nearly optimal, the number
e 4 ), which is quite large and seems difficult to improve.
of rows is O(d
Our alternate approach is still based on the technique of splitting coordinates. Unlike the
approach in [22] which is based on splitting coordinates according to ℓ1 leverage scores, in this new
approach, for any vector y = Ax, a coordinate i is heavy if |yi | ≥ d12 kyk1 and light otherwise. When
light coordinates contribute more to the ℓ1 -norm of y, we show that the sparse Cauchy embedding
in [22] with only O(d log d) rows is already sufficient to deal with such vectors. This is due to a
tighter analysis based on negative association theory [17] which also greatly simplifies the proof.
When heavy coordinates contribute more to the ℓ1 -norm of y, the idea is to use known ℓ2 oblivious
subspace embeddings. The key observation is that when heavy coordinates contribute more to the
ℓ1 -norm, we have kyk2 ≥ Ω d1 kyk1 and thus any ℓ2 oblivious subspace embedding with constant
distortion will also be an ℓ1 oblivious subspace embedding with O(d) distortion. See Section 4 for
a formal analysis and Section 5 for how to generalize this idea to ℓp -norms when 1 < p < 2.
Our final embedding consists of two parts. The ℓ2 oblivious subspace embedding part could
be the CountSketch embedding or the OSNAP embedding, which also provides a tradeoff between
number of non-zero entries per column and number of rows. For the sparse Cauchy part, although it
would be sufficient to prove the O(d log d) distortion bound as long as this part has O(d log d) rows,
an analysis based on a tighter Cauchy lower tail bound in Lemma 2.12 shows that it is possible to
further reduce the dilation to O(d) by increasing the number of rows in this part.
Using this approach, the sparsest embedding we can construct has O(d2 ) rows and two nonzero entries per column. We further show how to construct even sparser embeddings using random
sampling. Since we only use the sparse Cauchy part to deal with vectors in which light coordinates
contribute more to the ℓ1 -norm, thus even if we zero out each coordinate with probability 1 − ε
for a small constant ε, the resulting vector will still have sufficient ℓ1 -norm, with large enough
probability. Thus, if we zero out each standard Cauchy random variable in the sparse Cauchy part
with probability 1 − ε, the resulting embedding will still have the same distortion bound, up to a
constant factor. By doing so, there will be 1 + ε non-zero entries in expectation in each column of
1

This is also observed in [31], where the authors used exponential random variables to remedy this issue.

8

the new embedding. This idea is formalized in Section 6.1.

2

Preliminaries

We use k · kp to denote the ℓp -norm of a vector or the entry-wise ℓp -norm of a matrix. The
following lemma is a direct application of Hölder’s inequality.
Lemma 2.1. For any x ∈ Rn and 1 ≤ p ≤ q ≤ 2, we have
kxkq ≤ kxkp ≤ n1/p−1/q kxkq .
For u ∈ Rn and 1 ≤ a ≤ b ≤ n, let ua:b denote the vector with i-th coordinate equal to ui when
i ∈ [a, b], and zero otherwise. For a matrix S ∈ Rn×m , we use Si,∗ to denote the i-th row of S, S∗,j
to denote the j-th column of S.
Definition 2.1. For p ∈ [1, 2], a distribution over r × n matrices Π is an ℓp oblivious subspace
embedding, if for any fixed A ∈ Rn×d ,
i
h
Pr kAxkp ≤ kΠAxkp ≤ κkAxkp , ∀x ∈ Rd ≥ 0.99.
Π

Here κ is the distortion of Π.

Throughout the whole paper, we use X ≃ Y to denote that X and Y have the same distribution.
We use X  Y to denote stochastic dominance, i.e., X  Y iff for any t ∈ R, Pr[X ≥ t] ≥ Pr[Y ≥ t].

2.1

Stable Distribution

Definition 2.2 (p-stable distribution). A distribution D is p-stable if for any n real numbers
a1 , a2 , . . . , an , we have
!1/p
n
n
X
X
p
ai Xi ≃
|ai |
X.
i=1

i=1

Here Xi are i.i.d. drawn from D and X ∼ D.

p-stable distribution exists for any 0 < p ≤ 2 (see, e.g., [26]). We let Dp denote the p-stable
distribution. It is also well known that the standard Cauchy distribution is 1-stable and the
standard Gaussian distribution N (0, 1) is 2-stable.
We use the following lemma due to Nolan [26]
Lemma 2.2 (Theorem 1.12 in [26]). For 1 ≤ p < 2, let Xp ∼ Dp . As t → ∞,
Pr[Xp > t] ∼ cp x−p ,
where cp > 0 is a constant which depends only on p.
The following lemma is established in [22] by using Lemma 2.2
Lemma 2.3 (Lemma 8 in [22]). For 1 ≤ p < 2, let Xp ∼ Dp . There exists a constant αp such that
αp |C|  |Xp |p ,
where C is a standard Cauchy random variable and αp is a constant which depends only on p.
9

2.2

Tail Inequalities

We use the following standard form of the Chernoff bound and Bernstein’s inequality.
Lemma 2.4 (Chernoff Bound).
Suppose X1 , X2 , . . . , Xn are independent random variables taking
P
values in [0, 1]. Let X = ni=1 Xi .
For any δ > 0 we have
Pr [X > (1 + δ) E[X]] ≤ exp(−δ2 E[X]/3),
Pr [X < (1 − δ) E[X]] ≤ exp(−δ2 E[X]/2).
For t > 2e E[X] we have
Pr [X > t] ≤ 2−t .
Lemma 2.5 (Bernstein’s inequality).
Suppose X1 , X2 , . .P
. , Xn are independent random variables
P
taking values in [0, b]. Let X = ni=1 Xi and Var[X] = ni=1 Var[Xi ] be the variance of X. For
any t > 0 we have


t2
.
Pr[X > E[X] + t] ≤ exp −
2 Var[X] + 2bt/3
The following Bernstein-type lower tail inequality is due to Maurer [21].
Lemma 2.6 ([21]). Suppose
X1 , X2 , . . . , Xn are independent positive random variables that satisfy
P
E[Xi2 ] < ∞. Let X = ni=1 Xi . For any t > 0 we have


t2
Pr[X ≤ E[X] − t] ≤ exp − Pn
.
2 i=1 E[Xi2 ]
We use the following tail inequality of a Gaussian random vector.

Lemma 2.7. Let (a1 , a2 , . . . , an ) be a fixed vector. For i ∈ [n], let {Xi } be n possibly dependent
standard Gaussian random variables. For any 1 ≤ p ≤ 2, we have


!1/p
n
X


∈ Cp−1 kakp , Cp kakp  ≥ 0.99.
Pr 
|ai Xi |p
i=1

Here Cp > 1 is an absolute constant depends only on p.
Proof.
E
|p ]

"

n
X
i=1

p

|ai Xi |

#

=

n
X
i=1

p

p

|ai | E [|Xi | ] = Ap

where Ap = E [|Xi is a constant which depends only on p.
Thus, by Markov’s inequality, with probability at least 0.995
n
X
i=1

|ai Xi |p

!1/p

n
X
i=1

≤ (200Ap )1/p kakp .

10

|ai |p ,

There exists a constant Bp , which depends only p, such that
Pr[|Xi |p < Bp ] ≤

1
.
400

We let Yi be an indicator variable such that
(
1 if |Xi |p < Bp
.
Yi =
0 otherwise
P
1
, which also implies E [ ni=1 |ai |p · Yi |] ≤
We know that E[Yi ] ≤ 400
inequality, with probability at least 0.995 we have
n
X
i=1

Notice that

n
X

Thus, with probability at least 0.995,
n
X
i=1

Thus by Markov’s

1
|ai |p · Yi ≤ kakpp .
2

|ai Xi |p ≥ Bp

i=1

p
1
400 kakp .

p

|ai Xi |

!1/p

n
X
i=1

≥

|ai |p (1 − Yi )



Bp
2

1/p

kakp .


 1/p 
1/p
and using a union bound.
Thus, the lemma holds by taking Cp = max (200Ap ) , B2p

The following upper tail inequality for dependent standard Cauchy random variables is established in [22].
Lemma 2.8 (Lemma 3 in [22]). For P
i ∈ [n], let {Xi } be n possibly dependent standard Cauchy
random variables and γi > 0 with γ = i∈[n] γi . For any t ≥ 1 and n ≥ 3,


Pr 

X

i∈[n]



γi |Xi | > γt ≤

2 log(nt)
.
t

The following corollary is a direct implication of Lemma 2.8 and Lemma 2.3.
Corollary
P2.9. For i ∈ [n], let {Xi } be n possibly dependent p-stable random variables and γi > 0
with γ = i∈[n] γi . For any t ≥ 1 and n ≥ 3,


Pr 

X

i∈[n]



γi |Xi |p > αp γt ≤

where αp is the constant in Lemma 2.3.

11

2 log(nt)
,
t

For the sum of absolute values of independent standard Cauchy random variables, it is possible
prove an upper tail inequality better than Lemma 2.8.
Lemma 2.10. For i ∈ [n], let {Xi } be n independent standard Cauchy random variables. There
exists a constant U1 , such that for any n ≥ 3,
" n
#
X
log log n
.
Pr
|Xi | ≤ U1 n log n ≥ 1 −
log n
i=1

n log n
Proof. Let Ei be the event that |Xi | ≤ log
log n . According to the cumulative density function of the
standard Cauchy distribution, we have

Pr[Ei ] = 1 −

2 log log n
2
arctan (n log n/ log log n) ≥ 1 −
.
π
πn log n

T
log n
Let E = n1≤i Ei . By a union bound, E holds with probability at least 1 − 2 log
π log n . Next we
calculate E[|Xi | | E]. Since the Xi are independent, by using the probability density function of the
standard Cauchy distribution,


1 1
E[|Xi | | E] = E[|Xi | | Ei ] =
log 1 + (n log n/ log log n)2 = O(log n).
Pr[Ei ] π

Notice that conditioned on E, |Xi | are still independent. Furthermore, conditioned on E, for any
i ∈ [n], |Xi | ∈ [0, n log n/ log log n]. Thus for sufficiently large U1 , by applying the Chernoff bound
in Lemma 2.4 on |Xi | log log n(n log n)−1 ,
#
" n
X
U1 n log n
−
|Xi | > U1 n log n | E ≤ 2 n log n/ log log n = 2−U1 log log n .
Pr
i=1

Thus for sufficiently large U1 ,
#
#
" n
" n
X
X
|Xi | ≤ U1 n log n | E · Pr[E]
|Xi | ≤ U1 n log n ≥ Pr
Pr
i=1

i=1


 

2 log log n
log log n
−U1 log log n
· 1−
≥ 1−2
.
≥1−
π log n
log n

The following corollary is a direct implication of Lemma 2.10 and Lemma 2.3.
Corollary 2.11. Suppose 1 ≤ p < 2. For i ∈ [n], let {Xi } be n independent p-stable random
variables. There exists a constant Up which depends only on p, such that for any n ≥ 3,
#
" n
X
log log n
.
|Xi |p ≤ Up n log n ≥ 1 −
Pr
log n
i=1

Lemma 2.12. Suppose 1 ≤ p < 2. For i ∈ [n], let {Xi } be n independent p-stable random variables.
There exists a constant Lp which depends only on p, such that for sufficiently large n and T ,
" n

#
X
n
1
|Xi |p ≥ Lp n log
Pr
≥1− .
log T
T
i=1

12

Proof. According to Lemma 2.2, there exists a constant tp ≥ 1 which depends only on p, such that
for any t ≥ tp ,
cp
Pr[Xi > t] ≥ t−p .
2
p
Thus for t ≥ tp
Pr[|Xi |p > t] = Pr[|Xi | > t1/p ] = 2 Pr[Xi > t1/p ] ≥ cp t−1 .
For i ≥ 0 and j ∈ [n], we let Nji denote the indicator variable such that
(
1
Nji =
0

if |Xj |p > 2i tpp
otherwise

Pn

We have that E[Nji ] ≥ 2−i cp t−p
and thus E[N i ] ≥ n · 2−i cp t−p
. According to

i
p
h p
−p
i
−i−1
.
≥ 1 − exp −n · 2−i−3 cp t−p
the Chernoff bound in Lemma 2.4 we have Pr N ≥ n2
cp tp
p
Let lmax be the largest i such that
and N i =

i
j=1 Nj .


1
exp −n2−i−3 cp t−p
≤
.
p
2T

(2)

By a union bound, with probability at least
1−

lX
max
i=0



−p
exp −n2−i−3cp tp ≥ 1 − 1/T,

simultaneously for all 0 ≤ i ≤ lmax , N i ≥ n2−i−1 cp t−p
p , which implies
n
X
i=1

p

|Xi | ≥

lX
max
i=0

2i tpp · N i /2 ≥ cp /4 · lmax · n.

Solving (2) and substituting the value of lmax , for sufficiently large T and n, with probability at
least 1 − 1/T ,


n
X
n
p
|Xi | ≥ Lp n log
,
log T
i=1

where Lp is a constant which depends only on p.

2.3

ε-nets

We use the standard ε-net construction of a subspace in [5].
Definition 2.3. For any 1 ≤ p ≤ 2, for a given A ∈ Rn×d , denote B = {Ax | x ∈ Rd , kAxkp = 1}.
We say N ⊆ B is a ε-net of B if for any y ∈ B, there exists ŷ ∈ N such that ky − ŷkp ≤ ε.
Lemma 2.13 ([5]). For a given A ∈ Rn×d , there exists an ε-net N ⊆ B = {Ax | x ∈ Rd , kAxkp =
1} with size |N | ≤ (3/ε)d .

13

2.4

Known ℓ2 Oblivious Subspace Embeddings

In [12, 22, 23, 6, 13], a series of results on sparse ℓ2 oblivious subspace embedding are obtained.
Lemma 2.14 (CountSketch [12, 22, 23]). There exists an ℓ2 oblivious subspace embedding over
O(d2 ) × n matrices Π, where each column of Π has a single non-zero entry and the distortion
κ = 2.
Lemma 2.15 (OSNAP [23, 13]). For any B > 2, there exists an ℓ2 oblivious subspace embedding
over O (B · d log d) × n matrices Π, where each column of Π has at most O (logB d) non-zero entries
and the distortion κ = 2.
For completeness we include the construction for CountSketch and OSNAP here. In the CountSketch embedding, each column is chosen to have s = 1 non-zero entries chosen in a uniformly
random location and the non-zero value is uniformly chosen in {−1, 1}. In the OSNAP embedding,
each column is chosen to have s = O(logB d) non-zero entries in random locations, each equal to
±s−1/2 uniformly at random. All other entries in both embeddings are set to zero.
We need a few additional properties of the CountSketch embedding and the OSNAP embedding.
The following lemma is a direct calculation of the operator ℓ1 -norm of the matrices stated above.
Lemma 2.16. For any y ∈ Rn ,
• kΠyk1 ≤ kyk1 if Π is sampled from the CountSketch embedding;
1/2

• kΠyk1 ≤ O(logB d)kyk1 if Π is sampled from the OSNAP embedding.
The following lemma deals with the ℓp -norm of a vector and its ℓp -norm after projection using
CountSketch or OSNAP.
Lemma 2.17. For any y ∈ Rn and sufficiently large ω, with probability 1 − exp(Ω(ωd log d)),
• kΠ (y1:d2 ) kp ≤ (ωd log d)1−1/p kykp if Π is sampled from the CountSketch embedding;
• kΠ (y1:d2 ) kp ≤ (O(logB d))1/p−1/2 (ωd log d)1−1/p kykp if Π is sampled from the OSNAP embedding.
Proof. Suppose Π has R rows and s non-zero entries per column. For the CountSketch embedding
we have R = O(d2 ) and s = 1, while for the OSNAP embedding we have R = O(B · d log d) and
s = O(logB d). In either case we have R ≤ O(d2 ).
For i ∈ [R], define Bi = {j | j ≤ d2 and Πi,j 6= 0}. According to the Chernoff bound in Lemma
2.4, with probability at least 1 − exp(−Ω(ωd log d)), |Bi | ≤ ωd log d. It follows by a union bound
that with probability at least 1 − exp(−Ω(ωd log d)) · R = 1 − exp(−Ω(ωd log d)), simultaneously
for all i ∈ [R] we have |Bi | ≤ ωd log d. We condition on this event in the rest of the proof.
Notice that
p

X
|yj |
|(Π (y1:d2 ))i |p ≤ s−1/2


j∈Bi




≤ s−1/2 (ωd log d)1−1/p 

X

j∈Bi

1/p p


X

|yj |p   = s−p/2 (ωd log d)p−1 
|yj |p  .
j∈Bi

14

Here the second inequality follows from Lemma 2.1 and |Bi | ≤ ωd log d. For each j ∈ [d2 ], the
number of i ∈ [R] for which j ∈ Bi is exactly s, which implies
R
X
i=1

p

|(Π (y1:d2 ))i | ≤ s

−p/2

p−1

(ωd log d)

R X
X

i=1 j∈Bi

2

p

|yj | = s

1−p/2

p−1

(ωd log d)

d
X
j=1

|yj |p .

Thus,
kΠ (y1:d2 ) kp ≤ s1/p−1/2 (ωd log d)1−1/p ky1:d2 kp ≤ s1/p−1/2 (ωd log d)1−1/p kykp .

2.5

Well-conditioned Bases

We recall the definition and some existential results on well-coditioned matrices with respect to
ℓp -norms.
Definition 2.4 ((α, β, p)-well-conditioning [16]). For a given matrix U ∈ Rn×d and p ∈ [1, 2], let
q be the dual norm of p, i.e., 1/p + 1/q = 1. We say U is (α, β, p)-well-conditioned if (i) kU kp ≤ α
and (ii) kxkq ≤ βkU xkp for any x ∈ Rd .
Lemma 2.18 (Auerbach basis [4]). For any matrix A, there exists a basis matrix U of A such that
U is (d1/p , 1, p)-well-conditioned.

3

Hardness Result

3.1

The Lower Bound

The goal of this section is to prove Theorem 1.1. We restate it here for convenience.
Theorem 1.1. (restated) For 1 ≤ p < 2, if a distribution over r × n matrices Π is an ℓp oblivious
subspace embedding, then the distortion
!
1
κ=Ω
.


2/p
1 1/p
r 1/p−1/2
·
log
r
+
d
n

By Yao’s minimax principle [33], it suffices to show that there exists a hard distribution A over
such that for any Π ∈ Rr×n , if
i
h
(3)
Pr kAxkp ≤ kΠAxkp ≤ κkAxkp , ∀x ∈ Rd ≥ 0.99,

Rn×d

A∼A

then

κ=Ω


1 1/p
d

1
· log2/p r +


r 1/p−1/2
n

!

.

The columns in our construction of A consist of three parts:

• The first column is a vector where all the n entries are i.i.d. standard Gaussian random
variables. We call this column the D-column.
15

• For the next d/4 columns, each column has 4n/d non-zero entries, where all these non-zero
entries are i.i.d. standard Gaussian random variables. The indices of the 4n/d non-zero
entries of the i-th column are (4n/d) · (i − 1) + 1, (4n/d) · (i − 1) + 2, . . . , (4n/d) · i. We call
these columns M-column.
d
• We divide the next d/2 columns into log(n/d) blocks, where each block contains 2 log(n/d)
columns. For 0 ≤ i < log(n/d), columns in the i-th block contain 2i+1 non-zero entries and
all of these non-zero entries are i.i.d. standard Gaussian random variables. For two different
d
columns in the same block, the sets of indices of non-zero entries are disjoint. For the 2 log(n/d)
d
d
· 2i+1 = log(n/d)
2i non-zero entries are
columns in the i-th block, the indices of the 2 log(n/d)
sampled from {1, 2, . . . , n} without replacement. We call these columns S-column.

All entries in other columns are zero. This finishes our construction of A.
The following lemma is a direct implication of Lemma 2.7 and our construction.
Lemma 3.1. For each column c in A, with probability at least 0.99, the following holds:
1. If c is an S-column in the i-th block, then kckp ≤ Cp 2(i+1)/p .
2. If c is an M-column, then kckp ≤ Cp (4n/d)1/p .
3. If c is a D-column, then kckp ≥ Cp−1 n1/p .
Here Cp is the constant in Lemma 2.7.
Lemma 3.2. For any matrix Π ∈ Rr×n which satisfies the condition in (3), the ℓp -norm of each
column of Π is at most Cp2 κ(4n/d)1/p , where Cp is the constant in Lemma 2.7.
Proof. Suppose for contradiction that there exists some i ∈ [n] such that the i-th column of Π has
ℓp -norm larger than Cp2 κ(4n/d)1/p . Consider the vector Mj , which is the j-th M-column, whose i-th
entry is a standard Gaussian random variable, i.e., (4n/d) · (j − 1) + 1 ≤ i ≤ (4n/d) · j. We first
show that with probability at least 0.99, kΠMj kp > Cp κ(4n/d)1/p . According to the 2-stability of
the standard Gaussian distribution, for any k ∈ [r],
1/2

(4n/d)·j
X
Π2k,l  N (0, 1).
(ΠMj )k ∼ 
l=(4n/d)·(j−1)+1

Since




(4n/d)·j

X

l=(4n/d)·(j−1)+1

1/2

Π2k,l 

≥ Πk,i ,

according to Lemma 2.7, with probability at least 0.99,
kΠMj kp ≥ Cp−1 kΠ∗,i kp > Cp κ(4n/d)1/p .
According to Lemma 3.1, with probability at least 0.99,
kMj kp ≤ Cp (4n/d)1/p ,
which implies the condition in (3) is violated.
16

Lemma 3.3. For any matrix Π ∈ Rr×n which satisfies the condition in (3), for any 0 ≤ i <
2−i ,
log(n/d), the number of columns in Π with ℓp -norm larger than Cp2 κ2(i+1)/p is at most n log(n/d)
d
where Cp is the constant in Lemma 2.7.
Proof. Suppose for contradiction that for some 0 ≤ i < log(n/d), the number of columns in Π with
−1
ℓp -norm larger than Cp2 κ2(i+1)/p is larger than n log(n/d)
2−i . Let Π1 , Π2 , . . . , Πd log (n/d)/2 be the
d
 d 2i

−i log(n/d)
2
d log−1 (n/d)/2 S-column in the i-th block. With probability at least 1− 1 − log(n/d)
≥
d

1 − 1/e, there exists some j ∈ [d log−1 (n/d)/2] and l ∈ [n] such that (i) kΠ∗,l kp ≥ Cp2 κ2(i+1)/p and
(ii) Πjl is a standard Gaussian random variable. According to Lemma 3.1, with probability at least
0.99, kΠj kp ≤ Cp 2(i+1)/p . Now we show that with probability at least 0.99, kΠΠj kp ≥ Cp−1 kΠ∗,l kp >
Cp κ2(i+1)/p . Suppose P ⊆ [n] is the set of indices at which Πj contains a standard Gaussian random
variable. We know that l ∈ P . Thus, due to the 2-stability of the standard Gaussian distribution,
for any k ∈ [r],
!1/2
X
Π2k,m
N (0, 1).
(ΠΠj )k ∼
m∈P

Since

X

Π2k,m

m∈P

!1/2

≥ Πk,l ,

according to Lemma 2.7, with probability at least 0.99, kΠΠj kp ≥ Cp−1 kΠ∗,l kp > Cp κ2(i+1)/p ≥
κkΠj kp , which implies the condition in (3) is violated.
Lemma 3.4. For any matrix Π ∈ Rr×n which satisfies the condition in (3), we have
r
X
i=1

kΠi,∗ kp2

!1/p



1
1√
= O κ(n/d)1/p log2/p (n/d) + κr p − 2 n .

Proof. We partition the columns of Π into two parts. We let ΠL be the submatrix of Π formed by
columns with ℓp -norm at most 21/p Cp2 κ and ΠH be the submatrix formed by columns with ℓp -norm
larger than 21/p Cp2 κ. For ΠH , by Lemma 3.2 and Lemma 3.3 we have
r
X
i=1

≤

r
X



i=1

p
kΠH
i,∗ k2
p
kΠH
i,∗ kp

!1/p

!1/p

= kΠH kp =

X
i

p
kΠH
∗,i kp

!1/p

1/p
n
log(n/d)
(Cp2 κ)p · 2i+2 ·
≤
+ (Cp2 κ)p · (4n/d) · 2 log(n/d)
2i d
i=0


=O κ(n/d)1/p log2/p (n/d) .
log(n/d)−1

X

17

For ΠL , since all the columns have ℓp -norm at most 21/p Cp2 κ, we have
r
X
i=1

≤r

p
kΠL
i,∗ k2

1
− 12
p

r
X
i=1

1

≤r p

− 12

X
i

!1/p

2
kΠL
i,∗ k2
2
kΠL
∗,i kp

!1/2

=r

!1/2

1
− 21
p

kΠL k2 = r

1
− 12
p

 1 1√ 
−
= O κr p 2 n ,

X
i

2
kΠL
∗,i k2

!1/2

where the first inequality follows from Lemma 2.1 and the last equality follows from the fact that
ΠL has at most n columns.
L
Notice that for any 1 ≤ i ≤ r, kΠi,∗ k2 ≤ kΠH
i,∗ k2 + kΠi,∗ k2 , which implies
r
X
i=1

kΠi,∗ kp2

!1/p

≤

r
X
i=1

p
kΠH
i,∗ k2

!1/p

+

r
X
i=1

p
kΠL
i,∗ k2

!1/p



1
−1 √
= O κ(n/d)1/p log2/p (n/d) + κr p 2 n .

Now consider the vector D, which is the D-column in A. According to Lemma 3.1, with probability at least 0.99, kDkp = Ω(n1/p ). Due to the 2-stability of the standard Gaussian distribution,
(ΠD)i ∼ kΠi,∗ k2 N (0, 1).
According to Lemma 2.7, with probability at least 0.99,
kΠDkp = O

r
X
i=1

kΠi,∗ kp2

!1/p



1√
1
= O κ(n/d)1/p log2/p (n/d) + κr p − 2 n .

According to the condition in (3), we have

which implies



1
1√
Ω(n1/p ) = kDkp ≤ kΠDkp = O κ(n/d)1/p log2/p (n/d) + κr p − 2 n .
κ=Ω


1 1/p
d

1
· log2/p (n/d) +


r 1/p−1/2
n

!

.

Now we show that the lower bound can be further improved to
κ=Ω


1 1/p
d

1
· log2/p r +


r 1/p−1/2
n

!

.

(4)

We first note that r should be at least d, otherwise if we take a full-rank matrix A ∈ Rn×d ,
rank(ΠA) < d = rank(A), which means we can find a non-zero vector y = Ax in the column space
of A and Πy = 0, which implies the distortion κ is not finite.
18

When n ≤ rd2/(2−p) , log2/p (n/d) = O(log2/p r), which means the lower bound in (4) holds.
When n > rd2/(2−p) , we repeat the argument above but only consider the first rd2/(2−p) columns
of Π. By doing so we get a lower bound of



κ = Ω

1


1 1/p

d

· log2/p (rd2/(2−p)−1 ) +



1
d2/(2−p)

which is always stronger than the lower bound of
κ=Ω

3.2


1 1/p
d


1/p
2/p
1/p−1/2  = Ω(d / log (r)),

1
· log2/p r +


r 1/p−1/2
n

!

.

Necessity of Dependence on r

The goal of this section is to prove Theorem 3.5.



1/p 2d
4
−1
Theorem 3.5. Let r = exp 4 · 10 · 24 Up Lp
, where Up and Lp are the constants in

Corollary 2.11 and Lemma 2.12, respectively. For 1 ≤ p < 2, there exists an ℓp oblivious subspace
embedding over r × n matrices Π, where the distortion κ is a constant which depends only on p.

Our construction for the embedding in Theorem 3.5 is actually the same the dense p-stable
embedding in [28] (for p = 1) and Theorem 6 in [22] (for 1 < p < 2), whose entries are i.i.d.
sampled from the scaled p-stable distribution (r log r)−1/p Dp .
For any given matrix A ∈ Rn×d and any x ∈ Rd , we show that

i
h
1/p −d
.
Pr (Lp /2)1/p kAxkp ≤ kΠAxkp ≤ Up1/p kAxkp ≥ 1 − 10−2 24 Up L−1
p
Π

According to the definition of the p-stable distribution in Definition 2.2, for any i ∈ [r],
(ΠAx)i ∼ (r log r)−1/p kAxkp Dp .

Since the entries in Π are independent, entries in the vector ΠAx are also independent. Thus

1/p −d
,
according to Corollary 2.11, with probability at least 1 − logloglogr r ≥ 1 − 200−1 24 Up L−1
p
we have
kΠAxkpp ≤ Up (r log r)−1 kAxkpp · r log r = Up kAxkpp ,
which implies
kΠAxkp ≤ Up1/p kAxkp .


1/p d
On the other hand, according to Lemma 2.12, by setting T = 200 24 Up L−1
, with probap
−d


1/p
, we have
bility at least 1 − 1/T = 1 − 200−1 24 Up L−1
p
kΠAxkpp ≥ Lp (r log r)−1 kAxkpp · r log
19

r
≥ Lp /2kAxkpp ,
log T

which implies


1/p
kΠAxkp ≥ L1/p
/2
kAxkp .
p

It follows by a union bound that for any x ∈ Rd ,

i
h
1/p −d
Pr (Lp /2)1/p kAxkp ≤ kΠAxkp ≤ Up1/p kAxkp ≥ 1 − 10−2 24 Up L−1
.
p
Π

1/p
We build an ε-net N ⊆ B = {Ax | x ∈ Rd , kAxkp = 1} by setting 1/ε = 8 Up L−1
.
p

d

1/p
According to Lemma 2.13, |N | ≤ (3/ε)d = 24 Up L−1
. Again by a union bound, with
p
probability at least 0.99, we have for any y ∈ N ,
(Lp /2)1/p kykp ≤ kΠykp ≤ Up1/p kykp .
Condition on the event stated above. Now we show that for any x ∈ Rd ,
(Lp /4)1/p kAxkp ≤ kΠAxkp ≤ 2Up1/p kAxkp .
For any x ∈ Rd , let y = Ax. By homogeneity we can assume kykp = 1. We claim y can be written
as
y = y0 + y1 + y2 + . . . ,
i

where for any i ≥ 0 we have (i) kyyi kp ∈ N and (ii) ky i kp ≤ εi .
According to the definition of ε-net, there exists some vector y 0 ∈ N such that ky − y 0 kp ≤ ε
y−y 0
and ky 0 kp = 1. If y = y0 then we stop. Otherwise we consider the vector ky−y
0 k . Again can find
p
y−y 0
ky−y 0 kp

a vector ŷ 1 ∈ N such that

− ŷ 1

p

≤ ε and kŷ 1 kp = 1. Here we set y 1 = ky − y 0 kp · ŷ 1 and

continue this process inductively.
It follows that
X
X
kΠykp ≥ kΠy 0 k −
kΠy i k ≥ (Lp /2)1/p −
Up1/p εi ≥ (Lp /2)1/p − 2Up1/p ε ≥ (Lp /4)1/p
i>0

i>0

and
kΠykp ≤

X
i≥0

kΠy i k ≤

X
i≥0

Up1/p εi ≤ 2Up1/p .

Thus, Π is a valid ℓp oblivious subspace embedding with κ ≤ 2 4Up L−1
p
that depends only on p.

4

1/p

, which is a constant

New Subspace Embeddings for ℓ1

In this section, we present new sparse ℓ1 oblivious subspace embeddings with nearly-optimal
distortion.
Theorem 4.1. For any given A ∈ Rn×d , let U be a (d, 1, 1)-well-conditioned basis of A. There
exists an ℓ1 oblivious subspace embedding over O(d2 ) × n matrices Π where each column of Π has
two non-zero entries and with probability 0.99, for any x ∈ Rd ,
Ω(log d)kU xk1 ≤ kΠU xk1 ≤ O(d log d)kU xk1 .
20

Theorem 4.2. For any given A ∈ Rn×d and sufficiently large B, let U be a (d, 1, 1)-well-conditioned
basis of A. There exists an ℓ1 oblivious subspace embedding over O(B · d log d) × n matrices Π where
each column of Π has O(logB d) non-zero entries and with probability 0.99, for any x ∈ Rd ,
Ω(log B)kU xk1 ≤ kΠU xk1 ≤ O(d log d)kU xk1 .
Our embedding for Theorem 4.1 and Theorem 4.2 can be written as Π = (Π1 , Π2 )T . For
Theorem 4.1, Π1 is sampled from the CountSketch embedding in Lemma 2.14, scaled by a d log d
factor. For Theorem 4.2, Π1 is sampled from the OSNAP embedding in Lemma 2.15 with O(B ·
d log d) rows, O(logB d) non-zero entries per column, and scaled by a d log B factor. Suppose Π1
has R1 rows. Let R2 = min{R1 , d1.1 }. Π2 can be written as ΦD : Rn → RR2 as follows:
• h : [n] → [R2 ] is a random map so that for each i ∈ [n] and t ∈ [R2 ], h(i) = t with probability
1/R2 .
• Φ is an R2 × n binary matrix with Φh(i),i = 1 and all remaining entries 0.
• D is an n × n random diagonal matrix where the diagonal entries are i.i.d. sampled from the
standard Cauchy distribution.
It is immediate to see that the number of rows in Π2 is at most that in Π1 . Furthermore, Π2
has a single non-zero entry per column.
In the remainder of this section, we prove the dilation bound in Section 4.1, and the contraction
bound in Section 4.2. In the analysis we will define three events E1 , E2 and E3 , which we will
condition on later in the analysis. We will prove that each of these events holds with probability
at least 0.999. By a union bound, all of these events hold with probability at least 0.997. Thus,
these conditions will not affect our overall failure probability by more than 0.003.

4.1

No Overestimation

Let E1 be the event that kΠ2 U k ≤ O (d log d). We first prove that E1 holds with probability at
least 0.999.
Lemma 4.3. E1 holds with probability at least 0.999.
Proof.
kΠ2 U k1 =

R2 X
d
X
i=1 j=1

|(Π2 U )i,j | =

R2 X
d
X

X

i=1 j=1 k|h(k)=i

Dk,k Uk,j ≃

R2 X
d
X
i=1 j=1




X

k|h(k)=i



|Uk,j | X̂i,j .

n
o
Here X̂i,j are dependent standard Cauchy random variables. Since U is a (d, 1, 1)-well-conditioned
basis of A, we have


R2 X
d
X
X

|Uk,j | ≤ d.
i=1 j=1

k|h(k)=i

By Lemma 2.8 we have

Pr [kΠ2 U k1 > td] ≤
21

2 log(R2 td)
.
t

Taking t = ω log d where ω is a sufficiently large constant, we have
Pr [kΠ2 U k1 ≤ td] ≥ 0.999.
Lemma 4.4. Conditioned on E1 , for any x ∈ Rd , we have
kΠ2 U xk1 ≤ O(d log d)kU xk1 .
Proof.
kΠ2 U xk1 ≤ kΠ2 U k1 kxk∞ ≤ kΠ2 U k1 kU xk1 ≤ O(d log d)kU xk1 .
The first inequality follows from Hölder’s inequality, and the second inequality follows from the
definition of (d, 1, 1)-well-conditioned basis.
Since Π1 is sampled from the CountSketch embedding and scaled by a d log d factor, or the
OSNAP embedding and scaled by a d log B factor, the following lemma is a direct implication of
Lemma 2.16.
Lemma 4.5. For any x ∈ Rd , we have
kΠ1 U xk1 ≤ O(d log d)kU xk1 .
Combining Lemma 4.4 and Lemma 4.5, we can bound the overall dilation of our embedding.
Lemma 4.6. Conditioned on E1 , for any x ∈ Rd , we have
kΠU xk1 ≤ O(d log d)kU xk1 .
Proof.
kΠU xk1 = kΠ1 U xk1 + kΠ2 U xk1 = O(d log d)kU xk1 .

4.2

No Underestimation

We let E2 be the event that for any x ∈ Rd ,
d log dkU xk2 ≤ kΠ1 U xk2 ≤ 2d log d · kU xk2

(for Theorem 4.1)

d log BkU xk2 ≤ kΠ1 U xk2 ≤ 2d log B · kU xk2

(for Theorem 4.2).

or
Since Π1 is sampled from an ℓ2 oblivious subspace embedding with κ = 2 and scaled by a factor
of d log d (for Theorem 4.1) or d log B (for Theorem 4.2), E2 holds with probability at least 0.999.
Without loss of generality we assume |x1 | ≥ |x2 | ≥ |x3 | ≥ . . . ≥ |xn |. Of course, this order is
unknown and is not used by our embedding.
We first show that for any y = U x, if we can find a “heavy” part inside y, then the scaled ℓ2
oblivious subspace embedding Π1 also works well for ℓ1 . Formally, we have the following lemma.

22

Lemma 4.7. Conditioned on E2 , for any x ∈ Rd , if k(U x)1:d2 k1 2 ≥ 0.5kU xk1 , then
• kΠ1 U xk1 ≥ Ω(log d)kU xk1 for Theorem 4.1;
• kΠ1 U xk1 ≥ Ω(log B)kU xk1 for Theorem 4.2.
Proof. Notice that

1
1
k(U x)1:d2 k1 ≥
kU xk1 ,
d
2d
where the second inequality follows from Lemma 2.1. Thus for Theorem 4.1, kΠ1 U xk1 ≥ kΠ1 U xk2 ≥
Ω(log d)kU xk1 since Π1 is sampled from an ℓ2 oblivious subspace embedding and scaled by a factor
of d log d. For Theorem 4.2, kΠ1 U xk1 ≥ kΠ1 U xk2 ≥ Ω(log B)kU xk1 since Π1 is sampled from an
ℓ2 oblivious subspace embedding and scaled by a factor of d log B.
kU xk2 ≥ k(U x)1:d2 k2 ≥

Now we analyze those vectors U x that do not contain a “heavy” part. We show that they can
be handled by the Π2 part of our embedding.
Lemma 4.8. For any x ∈ Rd , if k(U x)d2 +1:n k1 ≥ 0.5kU xk1 , then with probability at least 1 −
exp(−32d log d), we have
• kΠ2 U xk1 ≥ Ω(log d)kU xk1 for Theorem 4.1;
• kΠ2 U xk1 ≥ Ω(log B)kU xk1 for Theorem 4.2.
Proof. Let y = U x. By homogeneity we assume kyk1 = 1. According to the given condition we
2
2
2
have kyd2 +1:n k1 ≥ 0.5. Notice
P that kyd2 +1:n k∞ ≤ 1/d since otherwise ky1:d2 k1 > d · 1/d = 1.
For i ∈ [R2 ], let Bi = d2 <j≤n Bi,j where
(
|yj | if h(j) = i
.
Bi,j =
0
otherwise
P 2
It follows that R
i=1 Bi = kyd2 +1:n k1 ≥ 0.5.
Since kyd2 +1:n k∞ ≤ 1/d2 and 1/2 ≤ kyd2 +1:n k1 ≤ 1, for any i ∈ [R2 ] and j > d2 we have
Bi,j ≤

1
d2

and

1
1
≤ E[Bi ] ≤
.
2R2
R2
Furthermore, by Hölder’s inequality we have
Var[Bi ] =

n
X
j=1

n
1 X 2
1
1
Var[Bi,j ] ≤
yj ≤
kyd2 +1:n k∞ · kyd2 +1:n k1 ≤
.
2
R2
R
R
2
2d
2
j=d +1

Thus by Bernstein’s inequality in Lemma 2.5, we have
t2
Pr[Bi ≥ 1/R2 + t] ≤ exp − 2
R2 d2 +
2

2t
3d2

!

.

(5)

Recall that for u ∈ Rn and 1 ≤ a ≤ b ≤ n, let ua:b denote the vector with i-th coordinate equal to ui when
i ∈ [a, b], and zero otherwise.

23

Let t = d0.2 /R2 . Since R2 ≤ d1.1 , by (5) we have



Pr[Bi > (d0.2 + 1)/R2 ] ≤ exp −3d2.2 /4R2 ≤ exp −3d1.1 /4 .

By a union bound, with probability at least

1 − exp −3d1.1 /4 · R2 ≥ 1 − exp(−32d log d)/4,

simultaneously for all i ∈ [R2 ] we have Bi ≤ (d0.2 + 1)/R2 .
Let t = 1/R2 . Since R2 ≤ d1.1 , by (5) we have


Pr[Bi > 2/R2 ] ≤ exp −3d2 /8R2 ≤ exp −3d0.9 /8 .

According to [17], Bi are negatively associated, which implies for any I ⊆ [R2 ] we have
Y
Pr[Bi ≥ ti , i ∈ I] ≤
Pr[Bi ≥ ti ].
i∈I

Thus, the probability that the number of Bi which satisfy Bi > 2/R2 is larger than d0.2 , is at most


R2
exp(−3d0.9 /8 · d0.2 ) < exp(−32d log d)/4.
d0.2
It follows that with probability at least 1 − exp(−32d log d)/2, for any i ∈ [R2 ] we have Bi ≤
+ 1)/R2 , and the number of Bi which satisfy Bi > 2/R2 is at most d0.2 . In the rest of the
proof we condition on this event.
Since R2 ≥ d log d,
X
Bi ≥ 0.5 − d0.2 · (d0.2 + 1)/R2 ≥ 1/4.

(d0.2

i∈[R2 ]|Bi ≤2/R2

Thus, the number of Bi which satisfy Bi ≥
X

i∈[R2 ]|Bi ≤2/R2

1
8R2

is at least R2 /16, since otherwise

< R2 /16 · 2/R2 + R2 ·

1
= 1/4.
8R2

Now consider Π2 y. According to the 1-stability of the standard Cauchy distribution,


X
|yj | · |Xi |
|(Π2 y)i | ≃ 
j∈[n]|h(j)=i

where {Xi } are independent standard Cauchy random variables. Notice that conditioned on the
event stated above,
the number P
of Bi which satisfy Bi ≥ 8R1 2 is at least R2 /16. Furthermore, for
P
any i ∈ [R2 ], j∈[n]|h(j)=i |yj | ≥ d2 <j≤n|h(j)=i |yj | = Bi . Thus,
R2
X
i=1

R2 /16

|(Π2 y)i | 

X
i=1

24

1
|X i |,
8R2


where X i are independent standard Cauchy random variables.
According to Lemma 2.12, by setting T = 2 exp(32d log d), with probability at least 1 − 1/T we
have
R2
X
1
|(Π2 y)i | ≥ L1 · R2 /16 · log(R2 /(16 log T )) ·
= Ω(log(R2 / log T )).
8R2
i=1

Thus, for Theorem 4.1, we have kΠ2 yk1 ≥ Ω(log d) since R2 = d1.1 and log T = O(d log d). For
Theorem 4.2, when R1 ≤ d1.1 , we have kΠ2 yk1 ≥ Ω(log B) since R2 = R1 = O(B · d log d) and
log T = O(d log d). When R1 > d1.1 , we have kΠ2 yk1 ≥ Ω(log d) = Ω(log B) since R2 = d1.1 and
log T = O(d log d).
Set ε = 1/d2 and create an ε-net N ⊆ B = {U x | x ∈ Rd and kU xk1 = 1}. According to
Lemma 2.13, |N | ≤ (3d2 )d . Let E3 be the event that for all y ∈ N , if kyd2 +1:n k1 ≥ 0.5, then
kΠ2 yk1 ≥ Ω(log d)kyk1 (for Theorem 4.1) or kΠ2 yk1 ≥ Ω(log B)kyk1 (for Theorem 4.2).
Now we show that E3 holds with constant probability.
Lemma 4.9. E3 holds with probability at least 0.999.
Proof. According to Lemma 4.8, by using a union bound, we have
Pr[E3 holds] ≥ 1 − |N | exp(−32d log d) > 0.999

We are now ready to prove the contraction bound.
Lemma 4.10. Conditioned on E1 , E2 and E3 , for all x ∈ Rd , we have
• kΠ2 U xk1 ≥ Ω(log d)kU xk1 for Theorem 4.1;
• kΠ2 U xk1 ≥ Ω(log B)kU xk1 for Theorem 4.2.
Proof. By homogeneity we can assume kU xk1 = 1. According to Lemma 4.7, conditioned on
E2 and E3 , for all y ∈ N , we have kΠ2 U xk1 ≥ Ω(log d)kU xk1 (for Theorem 4.1) or kΠ2 U xk1 ≥
Ω(log B)kU xk1 (for Theorem 4.2). For any given y = U x where kyk1 = 1, there exists some ŷ ∈ N
for which ky − ŷk1 ≤ ε = 1/d2 . Thus, conditioned on E1 , notice that both ŷ and y − ŷ are in the
column space of U , so according to Lemma 4.6, we have
kΠyk1 ≥ kΠŷk1 − kΠ(y − ŷ)k1 ≥ Ω(log d) − 1/d2 · O(d log d) = Ω(log d)

(for Theorem 4.1)

kΠyk1 ≥ kΠŷk1 − kΠ(y − ŷ)k1 ≥ Ω(log B) − 1/d2 · O(d log d) = Ω(log B)

(for Theorem 4.2).

or

25

5

New Subspace Embeddings for ℓp

In this section, we show how to generalize the constructions in Section 4 to ℓp -norms, for
1 < p < 2.
Theorem 5.1. Suppose 1 ≤ p < 2. For any given A ∈ Rn×d , let U be a (d1/p , 1, p)-well-conditioned
basis of A. There exists an ℓp oblivious subspace embedding over O(d2 ) × n matrices Π where each
column of a matrix drawn from Π has two non-zero entries and with probability 0.99, for any x ∈ Rd ,


Ω(1)kU xkp ≤ kΠU xkp ≤ O (d log d)1/p kU xkp .

Theorem 5.2. Suppose 1 ≤ p < 2. For any given A ∈ Rn×d and sufficiently large B, let U
be a (d1/p , 1, p)-well-conditioned basis of A. There exists an ℓp oblivious subspace embedding over
O(B · d log d) × n matrices Π where each column of a matrix drawn from Π has O(logB d) non-zero
entries and with probability 0.99, for any x ∈ Rd ,


Ω(1)kU xkp ≤ kΠU xkp ≤ O (d log d)1/p kU xkp .

Our embeddings for Theorem 5.1 and Theorem 5.2 can be written as Π = (Π1 , Π2 )T . Similar
to the constructions in Section 4, for Theorem 5.1, Π1 is sampled from the CountSketch embedding
in Lemma 2.14, scaled by a d2/p−1 factor. For Theorem 5.2, Π1 is sampled from the OSNAP
embedding in Lemma 2.15 with O(B · d log d) rows and O(logB d) non-zero entries per column and
also scaled by a d2/p−1 factor. The construction for Π2 is almost the same as that for Theorem 4.1
and 4.2, except for replacing the standard Cauchy random variables in the diagonal entries of D
with p-stable random variables. Most parts of the proof for the distortion bound resemble that for
Theorem 4.1 and 4.2. We will omit similar proofs.
The following lemma can be proved in the same way as Lemma 4.3 and Lemma 4.4, except
for replacing the upper tail inequality for standard Cauchy random variables in Lemma 2.8 with
that for p-stable random variables in Corollary 2.9, and replacing the properties of a (d, 1, 1)-wellconditioned basis with those of a (d1/p , 1, p)-well-conditioned basis.

Lemma 5.3. Let E1 be the event that kΠ2 U kp ≤ O (d log d)1/p . E1 holds with probability at least
0.999. Furthermore, conditioned on E1 , for any x ∈ Rd , we have


kΠ2 U xkp ≤ O (d log d)1/p kU xkp .
Let E2 be the event that for any x ∈ Rd ,

d2/p−1 kU xk2 ≤ kΠ1 U xk2 ≤ 2d2/p−1 kU xk2 .
Since Π1 is sampled from an ℓ2 oblivious subspace embedding with κ = 2, and scaled by a factor
of d2/p−1 , E2 holds with probability at least 0.999.
Without loss of generality we assume |x1 | ≥ |x2 | ≥ |x3 | ≥ . . . ≥ |xn |. Of course, this order is
unknown and is not used by our embeddings.
Lemma 5.4. Conditioned on E2 , for any x ∈ Rd , we have


kΠ1 (U x)d2 +1:n kp ≤ O (d log d)1/p kU xkp .
26

Proof. By homogeneity we can assume kU xkp = 1. Notice that k(U x)d2 +1:n k∞ ≤ d−2/p since
otherwise kU xkp ≥ k(U x)1:d2 kp > 1. By Hölder’s inequality,


k(U x)d2 +1:n k2 = 

n
X

(U x)2i 

i=d2 +1

Thus,

1/2



≤

1/p−1/2

kΠ1 (U x)d2 +1:n kp ≤ R1

n
X

i=d2 +1

|(U x)i |p ·

max

d2 +1≤i≤n

1/2

|U xi |2−p 

≤ d1−2/p .

kΠ1 (U x)d2 +1:n k2



≤O(d2/p−1 ) · 2d2/p−1 k(U x)d2 +1:n k2 = O(d2/p−1 ) = O (d log d)1/p .

Here the first inequality follows from Lemma 2.1 and the fact that Π1 U x has R1 rows, the second
inequality holds since R1 ≤ O(d2 ) and E2 holds.
Lemma 5.5. Conditioned on E2 , for any x ∈ Rd , if k(U x)1:d2 kp ≥ 0.5kU xkp , then kΠ1 U xkp ≥
Ω(1)kU xkp .
Proof. Notice that
kU xk2 ≥ k(U x)1:d2 k2 ≥ d1−2/p k(U x)1:d2 kp ≥ d1−2/p /2kU xkp ,
where the second inequality follows from Lemma 2.1 and the third inequality follows from the
condition that k(U x)1:d2 kp ≥ 0.5kU xkp . Thus, kΠ1 U xkp ≥ kΠ1 U xk2 ≥ Ω(1)kU xkp since Π1 is
sampled from an ℓ2 oblivious subspace embedding and scaled by a factor of d2/p−1 .
The proof of the following lemma is almost identical to that of Lemma 4.8. We omit the proof
here.
Lemma 5.6. For any x ∈ Rd , if k(U x)d2 +1:n kp ≥ 0.5kU xkp , then with probability at least 1 −
exp(−32d log d), we have kΠ2 U xkp ≥ Ω(1)kU xkp .
Set ε = 1/d2 and create an ε-net N ⊆ B = {U x | x ∈ Rd and kU xkp = 1}. According to
Lemma 2.13, |N | ≤ (3d2 )d .
Let E3 be the event that for all y ∈ N ,
1. if kyd2 +1:n kp ≥ 0.5kykp , then kΠ2 ykp ≥ Ω(1)kykp ;

2. kΠ1 (y1:d2 ) kp ≤ O (d log d)1/p kykp .

Lemma 5.7. E3 holds with probability at least 0.999.

Proof. Notice that Π1 is sampled from the CountSketch embedding or the OSNAP embedding and
scaled by a d2/p−1 factor. According to Lemma 2.17, by setting ω sufficiently large, with probability 1 − exp(−32d
log d) we have kΠ1 (y1:d2 ) kp ≤ d2/p−1 (O(logB d))1/p−1/2 (ωd log d)1−1/p kykp =

O (d log d)1/p kykp . Combining this with Lemma 5.6 and a union bound, we have
Pr[E3 holds] ≥ 1 − 2|N | exp(−32d log d) > 0.999

27

Lemma 5.8. Conditioned on E1 , E2 and E3 , for all x ∈ Rd , we have


Ω(1)kU xkp ≤ kΠU xkp ≤ O (d log d)1/p kU xkp .

Proof. For any x ∈ Rd , let y = U x. By homogeneity we can assume kykp = 1. As in the proof of
Theorem 3.5, y can be written as
y = y0 + y1 + y2 + . . . ,
i

where for any i ≥ 0 we have (i) kyyi kp ∈ N and (ii) ky i kp ≤ εi .
It follows by Lemma 5.3, Lemma 5.4 and Lemma 5.5 that



X
X 
kΠykp ≥ kΠy 0 kp −
kΠy i kp ≥ Ω(1) −
O (d log d)1/p εi ≥ Ω(1) − O (d log d)1/p 2ε ≥ Ω(1)
i>0

and
kΠykp ≤

6

i>0

X
i≥0

kΠy i kp ≤

X
i≥0





O (d log d)1/p εi ≤ O (d log d)1/p .

Subspace Embeddings with Improved Sparsity

In this section, we present two approaches to constructing sparser ℓp oblivious subspace embeddings for 1 ≤ p < 2. In Section 6.1 we present our first approach based on random sampling, which
yields an ℓp oblivious subspace embedding where each column of the embedding has at most two
non-zero entries and 1 + ε non-zero entries in expectation, where the number of rows r = O(d2 ).
In Section 6.2, we present another approach based on the construction in [22] and a truncation
argument, which yields an ℓp oblivious subspace embedding where each column of the embedding
e 4 ).
has a single non-zero entry, at the cost of increasing the number of rows r to O(d

6.1

Improved Sparsity Based on Random Sampling

In this section, we show how to further improve the sparsity in the constructions of Theorem
4.1 and Theorem 5.1.
Theorem 6.1. For any given A ∈ Rn×d , let U be a (d, 1, 1)-well-conditioned basis of A. For any
constant 0 < ε < 1, there exists an ℓ1 oblivious subspace embedding over O(d2 ) × n matrices Π
where each column of Π has at most two non-zero entries and 1 + ε non-zero entries in expectation,
such that with probability 0.99, for any x ∈ Rd ,
Ω(log d)kU xk1 ≤ kΠU xk1 ≤ O(d log d)kU xk1 .
Our embedding for Theorem 6.1 is almost identical to that for Theorem 4.1 except for the Π2
part. Recall that the Π2 part of the construction for Theorem 4.1 can be written as ΦD, where
Φh(i),i = 1 and all remaining entries are 0. In the new construction for Π2 , Φh(i),i are i.i.d. samples
from the Bernoulli distribution Ber(ε). I.e., Φh(i),i = 1 with probability ε and 0 otherwise. All
other parts of the construction are the same as in Theorem 4.1.
28

We note that the proof for Theorem 4.1 can still go through for the new construction. The
only difference occurs when proving Lemma 4.8. In fact, the Π2 part of the new construction for
Theorem 6.1 can be viewed as the following equivalent two-step procedure. For any given vector
y = U x, we first zero out each coordinate of y with probability 1 − ε, which results in a new vector
y, and then apply the Π2 part of the embedding in Theorem 4.1 on
 the new vector y.
Now we show that with probability at least 1 − exp −Ω(d2 ε) , we have
ky d2 +1:n k1 ≥ Ω(ǫ)kyd2 +1:n k1 .

Notice that E[|y i |] = ε|yi | and E[y 2i ] = εyi2 , which implies
E[ky d2 +1:n k1 ] = ε · kyd2 +1:n k1
and

X

i>d2

E[y 2i ] =

X

i>d2

εyi2 ≤ εkyd2 +1:n k1 · kyd2 +1:n k∞ = εd−2 kyd2 +1:n k21 .


Thus, by Maurer’s inequality in Lemma 2.6, with probability at least 1 − exp −Ω(d2 ε) , we have
ky d2 +1:n k1 ≥ Ω(ǫ)kyd2 +1:n k1 .

The rest part of the proof is identical to the original proof for Lemma 4.8. Similarly, the same
argument can also be applied to Theorem 5.1.
Theorem 6.2. Suppose 1 ≤ p < 2. For any given A ∈ Rn×d , let U be a (d1/p , 1, p)-well-conditioned
basis for A. For any constant 0 < ε < 1, there exists an ℓp oblivious subspace embedding over
O(d2 ) × n matrices Π where each column of Π has at most two non-zero entries and 1 + ε non-zero
entries in expectation, such that with probability 0.99, for any x ∈ Rd ,


Ω(1)kU xkp ≤ kΠU xkp ≤ O (d log d)1/p kU xkp .

The number of rows in Theorem 6.1 and Theorem 6.2 can not be further reduced. It is proved
in [24] (Theorem 16) that for any distribution over r × n matrices Π such that any matrix in its
support has at most one non-zero entry per column, if rank(ΠA) = rank(A) holds with constant
probability, then r = Ω(d2 ). Now we sketch how to generalize this lower bound to distribution over
r × n matrices for which each column has at most 1 + ε non-zero entries in expectation, for any
constant 0 < ε < 1. Notice that such a lower bound already implies the number of rows of Theorem
6.1 and Theorem 6.2 is optimal up to constant factors, since any oblivious subspace embedding
preserves the rank with constant probability.
For each column in the matrix Π, by Markov’s inequality, with probability at least 1 − 1+ε
2 ,
there will be at most one non-zero entry in that column. By the Chernoff bound in Lemma 2.4,
with probability 1 − exp(−Ω(n)), the number of columns in Π with at most one non-zero entry is
Ω(n). Furthermore, the balls and bins analysis in the proof of Theorem 16 in [24] can be applied
to distributions over r × n matrices such that for any matrix in the support of the distribution, the
number of columns with at most one non-zero entry is Ω(n). Indeed, with constant probability the
rank will drop if the embedding matrix has o(d2 ) rows. This establishes the desired lower bound
of r = Ω(d2 ).

29

6.2

Improving Sparsity Based on Truncation

In this section, we show how to use a truncation argument to improve the construction in [22].
Before formally stating the construction, we first define the truncation operation. For a given
parameter α > 0, for any x ∈ R, define

if x ∈ [0, α]

α
truncα (x) = −α if x ∈ [−α, 0) .


x
otherwise

Here we note some elementary properties of the truncation operation.
Lemma 6.3. For a given parameter α > 0, for any x ∈ R, we have
• |truncα (x)| ≥ α.
• truncα (x) − α ≤ x ≤ truncα (x) + α.

When applying the truncation operation to standard Cauchy random variables, the following
properties are direct implications of Lemma 6.3 and the 1-stability of standard Cauchy random
variables.
Corollary 6.4. For i ∈ [n], let Xi be n independent standard Cauchy random variables. The
following holds.
• |truncα (Xi )| ≥ α.
• For any a = (a1 , a2 , . . . , an ) ∈ Rn ,
kak1 · X̂ − kak1 · α 

n
X
i=1

ai · truncα (Xi )  kak1 · X̂ + kak1 · α,

where X̂ is a standard Cauchy random variable.
Now we are ready to state the main result of this section.
e 4 ) × n matrices Π where
Theorem 6.5. There exists an ℓ1 oblivious subspace embedding over O(d
e
each column of Π has a single non-zero entry. The distortion κ = O(d).

Our embedding for Theorem 6.5 is almost identical to the embedding for Theorem 2 in [22]
and the Π2 part of the embedding for Theorem 4.1 and Theorem 4.2, except for replacing standard
e 4 ) be
Cauchy random variables with truncated standard Cauchy random variables. Let R = O(d
the number of rows of Π. Here Π can be written as ΦD : Rn → RR , defined as follows:
• h : [n] → [R] is a random map so that for each i ∈ [n] and t ∈ [R], h(i) = t with probability
1/R.
• Φ is an R × n binary matrix with Φh(i),i = 1 and all remaining entries 0.
• D is an n × n random diagonal matrix where Di,i = truncα (Xi ). Here {Xi } are i.i.d. samples
from the standard Cauchy distribution and α < 1/4 is a positive constant.
30

Now we sketch how to modify the proof of Theorem 2 in [22] to prove the the distortion bound
of our new embedding.
In the proof of Theorem 2 in [22], the authors defined five events: EU , EL , EH , EC and EL̂ .
Notice that for our new embedding, the event EC is no longer needed, since by Corollary 6.4, the
absolute values of standard Cauchy random variables are never smaller than α after truncation,
where α is a small constant. We also change the number of rows of Π to O(d4 log5 d), and the
definition of the event EL̂ is changed to kΠU L̂ k1 ≤ O(1/d log 2 d) correspondingly.
Lemma 16 and Lemma 22 in the proof for Theorem 2 in [22] show that EU and EL̂ hold with
constant probability. The proofs for these two lemmas almost remain unchanged, except for replacing the 1-stability of standard Cauchy random variables with the upper bound part of the
“approximately 1-stability” of truncated standard Cauchy random variables in Corollary 6.4.
Lemma 13 is changed to the following: Given EL , for any fixed y ∈ Y L , we have




1
− α kyk1 ≤ exp(−Ω(d log d)).
Pr kΠyk1 ≤
4
The proof of the new version of Lemma 13 is also similar to the original proof, except for replacing
the 1-stability of standard Cauchy random variables with the lower bound part of the “approximate
1-stability” of truncated standard Cauchy random variables in Corollary 6.4. This also explains
why we need α to be a constant smaller than 1/4. Similarly, the constant 1/8 in Lemma 14 also
need to be modified to reflect the changes in Lemma 13.
Finally, since the absolute values of standard Cauchy random variables are never smaller than
α after truncation, Lemma 15 is changed to the following: Given EH and EL̂ , for any y ∈ Y H we
have kΠyk1 ≥ Ω(α)kyk1 . This finishes our modification to the proof of Theorem 2 in [22].
By applying the truncation argument to p-stable random variables, a similar result can be
obtained for ℓp oblivious subspace embeddings.
e 4) × n
Theorem 6.6. For 1 ≤ p < 2, there exists an ℓp oblivious subspace embedding over O(d
e 1/p ).
matrices Π where each column of Π has a single non-zero entry. The distortion κ = O(d

References

[1] Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast johnsonlindenstrauss transform. In Proceedings of the thirty-eighth annual ACM symposium on Theory
of computing, pages 557–563. ACM, 2006.
[2] Alexandr Andoni. High frequency moments via max-stability. In Acoustics, Speech and Signal
Processing (ICASSP), 2017 IEEE International Conference on, pages 6364–6368. IEEE, 2017.
[3] Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David Woodruff. Efficient sketches for earthmover distance, with applications. In Foundations of Computer Science, 2009. FOCS’09. 50th
Annual IEEE Symposium on, pages 324–330. IEEE, 2009.
[4] Herman Auerbach. On the area of convex curves with conjugate diameters. PhD thesis, PhD
thesis, University of Lwów, 1930.
[5] J. Bourgain, J. Lindenstrauss, and V. Milman. Approximation of zonoids by zonotopes. Acta
mathematica, 162(1):73–141, 1989.
31

[6] Jean Bourgain, Sjoerd Dirksen, and Jelani Nelson. Toward a unified theory of sparse dimensionality reduction in euclidean space. Geometric and Functional Analysis, 25(4):1009–1088,
2015.
[7] Bo Brinkman and Moses Charikar. On the impossibility of dimension reduction in ℓ1 . Journal
of the ACM (JACM), 52(5):766–788, 2005.
[8] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data
streams. Automata, languages and programming, pages 784–784, 2002.
[9] Moses Charikar and Amit Sahai. Dimension reduction in the ℓ1 norm. In Foundations of
Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 551–560.
IEEE, 2002.
[10] Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui
Meng, and David P. Woodruff. The fast cauchy transform and faster robust linear regression.
SIAM Journal on Computing, 45(3):763–810, 2016.
[11] Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model.
In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009,
Bethesda, MD, USA, May 31 - June 2, 2009, pages 205–214, 2009.
[12] Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in
input sparsity time. In Proceedings of the forty-fifth annual ACM symposium on Theory of
computing, pages 81–90. ACM, 2013.
[13] Michael B. Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 278–287. Society for Industrial and Applied Mathematics, 2016.
[14] Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron
Sidford. Uniform sampling for matrix approximation. In Proceedings of the 2015 Conference
on Innovations in Theoretical Computer Science, pages 181–190. ACM, 2015.
[15] Michael B. Cohen and Richard Peng. ℓp row sampling by lewis weights. In Proceedings of the
forty-seventh annual ACM symposium on Theory of computing, pages 183–192. ACM, 2015.
[16] Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney.
Sampling algorithms and coresets for ℓp regression. SIAM Journal on Computing, 38(5):2060–
2078, 2009.
[17] Devdatt Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. BRICS
Report Series, 3(25), 1996.
[18] James R. Lee and Assaf Naor. Embedding the diamond graph in Lp and dimension reduction
in L1 . Geometric and Functional Analysis, 14(4):745–747, 2004.
[19] Mu Li, Gary L. Miller, and Richard Peng. Iterative row sampling. In Foundations of Computer
Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 127–136. IEEE, 2013.

32

[20] Michael W. Mahoney. Randomized algorithms for matrices and data.
Trends R in Machine Learning, 3(2):123–224, 2011.

Foundations and

[21] Andreas Maurer. A bound on the deviation probability for sums of non-negative random
variables. J. Inequalities in Pure and Applied Mathematics, 4(1):15, 2003.
[22] Xiangrui Meng and Michael W. Mahoney. Low-distortion subspace embeddings in inputsparsity time and applications to robust linear regression. In Proceedings of the forty-fifth
annual ACM symposium on Theory of computing, pages 91–100. ACM, 2013.
[23] Jelani Nelson and Huy L. Nguy˜ên. OSNAP: Faster numerical linear algebra algorithms via
sparser subspace embeddings. In Foundations of Computer Science (FOCS), 2013 IEEE 54th
Annual Symposium on, pages 117–126. IEEE, 2013.
[24] Jelani Nelson and Huy L. Nguy˜ên. Sparsity lower bounds for dimensionality reducing maps. In
Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 101–110.
ACM, 2013.
[25] Jelani Nelson and Huy L. Nguy˜ên. Lower bounds for oblivious subspace embeddings. In International Colloquium on Automata, Languages, and Programming, pages 883–894. Springer,
2014.
[26] J. P. Nolan. Stable Distributions - Models for Heavy Tailed Data. Birkhauser, Boston, 2018.
In progress, Chapter 1 online at http://fs2.american.edu/jpnolan/www/stable/stable.html.
[27] Tamas Sarlos. Improved approximation algorithms for large matrices via random projections.
In Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on, pages
143–152. IEEE, 2006.
[28] Christian Sohler and David P. Woodruff. Subspace embeddings for the l1-norm with applications. In Proceedings of the forty-third annual ACM symposium on Theory of computing,
pages 755–764. ACM, 2011.
[29] Zhao Song, David P. Woodruff, and Peilin Zhong. Low rank approximation with entrywise
ℓ1 -norm error. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of
Computing, pages 688–701. ACM, 2017.
[30] David P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends R
in Theoretical Computer Science, 10(1–2):1–157, 2014.
[31] David P. Woodruff and Qin Zhang. Subspace embeddings and ℓp -regression using exponential
random variables. In Conference on Learning Theory, pages 546–567, 2013.
[32] Jiyan Yang, Xiangrui Meng, and Michael Mahoney. Quantile regression for large-scale applications. In International Conference on Machine Learning, pages 881–887, 2013.
[33] Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity.
In Foundations of Computer Science, 1977., 18th Annual Symposium on, pages 222–227. IEEE,
1977.

33

