INTRODUCTION

An ℓ p oblivious subspace embedding with distortion κ is a distribution over r ×n matrices Π such that for any given A ∈ R n×d , with constant probability, Ax p ≤ ΠAx p ≤ κ Ax p simultaneously for all x ∈ R d . 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. Sárlos [29]firstusedℓ 2 oblivious subspace embeddings to solve ℓ 2 -regression and Frobenius-norm lowrank approximation. To see the connection, suppose one wishes to solve the ℓ 2 -regression problem argmin x Axb 2 in the overconstrained setting, i.e., A ∈ R n×d and b ∈ R n where n ≫ d. Sárlos showed that to solve this problem approximately, it suffices to solve a much smaller instance argmin x ΠAx -Πb 2 , provided Π is an ℓ 2 oblivious subspace embedding for the matrix formed by concatenating columns of A ∈ R n×d and b ∈ R n . Sárlos further showed that using the Fast Johnson-Lindenstrauss Transform in Reference [1]astheℓ 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 approach based on the normal equation, which runs in O (nd 2 ) time. The advatange of the Fast Johnson-Lindenstrauss Transform is that for any A ∈ R n×d , for any matrix Π in the support of the distribution, ΠA can be computed in O (nd log n) time.

Subsequent to the work of Sá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 [34] for recent developments.

The bottleneck of Sárlos's approach is the step to calculate ΠA, which requires Ω(nd ) 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 [10] 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 [6]. By using the CountSketch embedding in Reference [10], 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 Reference [10] 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 References [24,25].

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 Reference [26], Nelson and Nguy ẽn showed that any ℓ 2 oblivious subspace embedding with constant distortion and s = 1 non-zero entries per column requires Ω(d 2 ) 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 Reference [25], obtaining a result showing that for any Tight Bounds for ℓ 1 Oblivious Subspace Embeddings 8:3 B > 2, for r about B • d log 8 d/εfoot_2 and s about log 3 B d/ε, one can achieve an ℓ 2 oblivious subspace embedding with κ = 1 + ε.Theboundonr and s was further improved in Reference [11](seealso Reference [4]), where Cohen showed that for any B > 2, it suffices to have r = O (B •d log d/ε 2 ) and s = O (log B d/ε). Cohen's result matches the lower bound in Reference [27] up to a multiplicative log d factor in the number of rows.

Another line of research focused on the case when p 2, as the corresponding regression and low-rank approximation problems are often considered to be more robust, or less sensitive to outliers. Moreover, the p = 1 error measure for regression yields the maximum likelihood estimator under Laplacian noise models. When p = 1, using Cauchy random variables, Sohler and Woodruff [30] showed there exist ℓ 1 oblivious subspace embeddings with r = 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 [24]t oℓ p -norms when 1 < p < 2, where they showed there exist ℓ p oblivious subspace embeddings with r = O (d log d ) rows and κ = O (d log d ). 1 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 argmin x ΠAx -Πb p . 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 existence of ℓ p oblivious subspace embeddings with r = poly(d/ε) and κ = 1 + ε.

Although it was unknown if better oblivious subspace embeddings exist for p 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 Reference [34] and references therein for further details. Recent developments in entrywise ℓ p low-rank approximation [31]alsousedℓ p oblivious subspace embeddings as an important ingredient. Furthermore, such ℓ 1 oblivious subspace embeddings are the only known way to achieve single-pass streaming algorithms for ℓ 1 -regression (see, e.g., Section 5 of Reference [30], 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., Reference [9]). We note that recent algorithms for ℓ p -regression based on Lewis weights 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 Reference [8], 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 [24] showed that when 1 ≤ p < 2, there exist ℓ p oblivious subspace embeddings with r = O (d 5 ) rows and s = 1 non-zero entries per column, where the distortion κ = O (d 3 ). 2 The structure of the embedding by Meng and Mahoney is very similar to the CountSketch embedding by Clarkson and Woodruff [10]. 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 [2], which used exponential random variables to estimate the ℓ p -norm of a data steam, Woodruff and Zhang [35] improved the embedding given in Reference [24]. They showed there exist ℓ 1 oblivious subspace embeddings with r = O (d ) rows and s = polylog(d ) non-zero entries per column, where the distortion κ = min{ O (d 2 ), O (d 1.5 ) log n}. Note that to achieve such a small polylogarithmic sparsity, the distortion κ given by the analysis

Here, η > 0 is an arbitrarily small constant. B > 0 is required to be sufficiently large and provides a tradeoff between r , κ,ands.

in Reference [35] had to either increase to O (d 2 ) or to O (d 1.5 ) log n, the latter also depending on n.SeeTable1 for a summary of previous and new upper bounds when p = 1.

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 References [24,30] showed that κ = O (d log d ) is achievable. Is this optimal? Also, it is unknown whether there exist sparse ℓ 1 oblivious subspace embeddings with dimension O (d ) and distortion κ = O (d ). In this article, we resolve these questions.

Our Results

Distortion Lower Bound. We first show a distortion lower bound for ℓ p oblivious subspace embeddings, when 1 ≤ p < 2. Theorem 1.1. For 1 ≤ p < 2, if a distribution over r × n matrices Π is an ℓ p oblivious subspace embedding, then the distortion

When 1 ≤ p < 2a n dr = 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 Ω(d 1/p log -2/p d ). It was shown in Reference [30] that there exist ℓ 1 oblivious subspace embeddings with r = O (d log d ) rows and distortion κ = O (d log d ). Our lower bound matches this result up to an O (log 3 d ) factor. Thus, our lower bound is nearly optimal for r = poly(d ) when p = 1 (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 [4,10,11,24,25,29] with κ = 1 + ε and r = poly(d/ε),whereε can be an arbitrarily small constant.

It is possible that the log 2/p r factor (in the (1/d ) 1/p • log 2/p r term) could be somewhat improved. However, we show that some dependence on r is, in fact, necessary.

Tight Bounds for ℓ 1 Oblivious Subspace Embeddings 8:5 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 < 2andr does not depend on n. This new embedding suggests that it is impossible to get a lower bound of

i.e., the ( 1 d ) 1/p term should have some dependence on r . New ℓ p oblivious subspace embeddings. We next show there exist sparse ℓ 1 oblivious subspace embeddings with nearly optimal distortion, and sparse ℓ p oblivious subspace embeddings with O (d log d ) distortion when 1 < p < 2. Theorem 1.3 (Summary of Theorem 4.1, 4.2, 5.1,and5.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

Notably, the distortion of our embeddings is never worse than the dense constructions in References [24,30]. Also, when p = 1, if we set r = O (d 2 ) (Case 1(a)) or r = O (d 1+η ) 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 ).W er e m a r k that by using the dense construction in Reference [30], it is also possible to reduce the distortion to O (d ) by increasing the number of rows.

Similar to the OSNAP embedding in Reference [25], 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 (d 2 ) × 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 )

The second approach is based on the construction in Reference [24] 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 subspace embedding over O (d 4 ) × n matrices Π where each column of Π has a single non-zero entry and distortion κ = O (d ).

It has been shown in Reference [26] that for any distribution over r × n matrices Π with s = 1 non-zero entries per column, if for any fixed matrix A ∈ R n×d ,rank(ΠA) = rank(A) with constant probability, then Π should have r = Ω(d 2 ) 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.

Comparison with Previous Work

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 R r ×n , which does not depend the given matrix A ∈ R n×d . A non-oblivious 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 Reference [20] for an excellent survey on leverage scores and References [12,13,17] for recent developments on non-oblivious subspace embeddings.

Previous impossibility results for dimension reduction in ℓ 1 [5,7,16] are established by creating asetofO (n) points in R n and showing that any (non-oblivious) embedding on them incurs a large distortion. In this article, we focus on embedding a d-dimensional subspace of R n into R poly(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 R n . Previous results [13] showed that any d-dimensional subspace in R n can be embedded into R O (d (log d )ε -2 ) 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 [7] showed that there exist O (n) points such that any linear embedding R n → R d 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 nonoblivious subspace embeddings in ℓ p when 1 ≤ p < 2. This result suggests that to construct a subspace embedding with (1 + ε) distortion, it is essential to use non-oblivious subspace embeddings.

Although our main focus in this article is to understand oblivious subspace embeddings, we remark that our technique for proving the hardness result in Theorem 1.1 canalsobeappliedto embed any d points in R n into R poly(d ) in ℓ p using oblivious linear embeddings, when 1 ≤ p < 2. In particular, it is possible to reproduce the result of Reference [7] using our techniques, although in a weaker setting where the embeddings are oblivious.

Errors in Prior Work and the Conference Version

In the conference version of this article [32], we incorrectly claimed that the distortion of the embeddings in Theorems 1.3 and 1.4 is κ = O ((d log d ) 1/p ),andκ = O (d 1/p ) for the embedding in Theorem 1.5. The source of the error is Lemma 2.22 (Lemma 2.16 in the conference version), in which it was claimed that by the existence of an Auerbach basis, the existence of a certain well-conditioned basis follows. However, it is unclear whether the existence of an Auerbach basis implies the existence of such a well-conditioned basis. The claim that we made was actually already made in previous work. It first appeared in the technical report version [23] of Reference [24]. In the proof of Theorem 6 in Section A.7 of Reference [23], the authors claimed that the existence of an Auerbach basis implied the existence of a (d 1/p , 1, p)-conditioned basis. The authors of Reference [24] confirmed that this is an error in their work in Reference [22]. Besides propagating to our work, that error also propagates to Reference [35], in which a similar claim was made.

Tight Bounds for ℓ 1 Oblivious Subspace Embeddings 8:7

After fixing this, the best existing ℓ p oblivious subspace embeddings with r = poly(d ) rows have distortion κ = O (d log d ) when 1 < p < 2. Thus, while we obtain tight bounds up to polylog(d ) factors for the important case of p = 1, when 1 < p < 2, our distortion lower bound in Theorem 1.1 is not necessarily tight. We leave it as an open problem to resolve the case 1 < p < 2.

Applications of Our Subspace Embeddings

Using the sparse ℓ p oblivious subspace embeddings in Theorem 1.3, we obtain improvements to many related problems. We list a few examples in this section.

ℓ p -regression in the streaming model. Using dense Cauchy embeddings and a sampling data structure from Reference [3], a single-pass streaming algorithm for ℓ 1 -regression argmin x Ax -b 1 was designed in Reference [30]. To get a (1 + ε)-approximate solution to the regression problem, the algorithm uses poly(dε -1 log n) bits of space, where A ∈ R n×d and b ∈ R n . The total running time of the algorithm, however, is

By replacing the dense Cauchy embedding with our new oblivious subspace embeddings in 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 [24] 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 ∈ R n×d and approximation factor α,the goal of the ℓ 1 -low-rank approximation problem is to output a matrix A for which

where • 1 is the entrywise ℓ 1 -norm.

In Reference [31], 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 timeT , 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 [24], which is originally used in Reference [31], with our new oblivious subspace embeddings in Theorem 1.3. This improvement also propagates to other problems considered in Reference [31] such as ℓ p -low-rank approximation, entrywise ℓ p -norm CUR decomposition and ℓ p -low-rank approximation in distributed and streaming models.

Quantile Regression. Given a matrix

Here τ is a parameter in (0, 1). An efficient algorithm to calculate a (1 + ε)-approximate solution to quantile regression was proposed in Reference [36]. 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,thepoly(d ) term in the running time can be directly improved.

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 ∈ R n×d such that for any

holds simultaneously for all x ∈ R d with constant probability, then κ = Ω(d ).

Roughly speaking, our proof is based on the crucial observation that, the histogram of the ℓ 1norm of columns in the deterministic embedding Π/κ should look like that of a discretized standard Cauchy distribution. That is, there are at most 2 i columns in Π/κ with ℓ 1 -norm larger than Θ((n/d )2 -i ). This is because if we choose a matrix A ∈ R n×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. However, if the embedding Π/κ contains more than 2 i columns with ℓ 1 -norm larger than Θ((n/d )2 -i ), then with constant probability, there exists some i ∈

In that case, it can be shown that after projection by Π/κ,thejth column of A has ℓ 1 -norm larger than Θ((n/d )2 -i ), which violates the condition in Equation (1).

To prove κ = Ω(d ),letc ∈ R n be a vector whose entries are all i.i.d. sampled from N (0, 1). With constant probability c 1 = Ω(n). However, we are able to show that the constraint we put on the histogram of the ℓ 1 -norm of columns in Π/κ implies that Πc/κ 1 = O (n/d ) and hence κ = Ω(d ).

The formal analysis in Section 3.1 shows that κ = Ω(d log -2 r ) when n ≫ r .

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 Reference [30]. Unlike previous approaches [24,30,35], we do not use the existence of an Auerbach basis to prove the dilation bound. Our analysis is based on tighter tail bounds for sums of absolute values of independent standard Cauchy (and also p-stable) random variables in Lemmas 2.12 and 2.14.Let{X i } be R = exp(exp(O (d ))) independent standard Cauchy random variables. Based on the tighter tail bounds, it can be shown that with probability

which enables us to now apply a 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 Reference [24] and its analysis. The sparse Cauchy embedding in Reference [24]has O (d 5 ) rows. In each column, there is a single nonzero entry that is sampled from the standard Cauchy distribution. The O (d ) dilation bound follows the standard approach [30] of using the existence of an 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 Reference [10] to analyze the CountSketch embedding. A coordinate 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 Tight Bounds for ℓ 1 Oblivious Subspace Embeddings 8:9 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 (d 2 ) heavy coordinates and the embedding has Ω(d 4 ) rows, then 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 of the O (d 2 ) standard Cauchy random variables associated with the heavy coordinates are at least Ω(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 Reference [24] almost follows the histogram predicted by our lower bound argument, except for the lower tail part. As predicted by our lower bound argument, for an embedding Π, which has the optimal κ = O (d ) distortion, the ℓ 1 -norm of each column in Π should be larger than a constant. However, the standard Cauchy distribution is heavytailed in both directions. 3 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. I ti ss h o w ni nC o r o l l a r y6.4 that standard Cauchy random variables are still "approximately 1stable" 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 of rows is O (d 4 ), which seems difficult to improve.

Our alternate approach is still based on the technique of splitting coordinates. Unlike the approach in Reference [24], which is based on splitting coordinates according to the ℓ 1 leverage scores, in this new approach, for any vector y = Ax , a coordinate i is heavy if |y i |≥ 1 d 2 y 1 and light otherwise. When light coordinates contribute more to the ℓ 1 -norm of y, we show that the sparse Cauchy embedding in Reference [24] 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 [15], 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 y 2 ≥ Ω( 1 d ) y 1 and thus any ℓ 2 oblivious subspace embedding with constant distortion will also be an ℓ 1 oblivious subspace embedding with O (d ) distortion. See Section 5 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 the 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.14 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 (d 2 ) 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 most of the ℓ 1 -norm, even if we zero out each coordinate with probability 1 -ε for a small constant ε, the resulting vector will still have a sufficiently ℓ 1 -norm, with large enough probability. Thus, if we zero out each standard Cauchy random variable in the sparse Cauchy part with probability 1 -ε, then 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 the new embedding. This idea is formalized in Section 6.1.

Followup Work

Building upon our Theorem 1.2, followup work in Reference [18]improvedourℓ 1 oblivious suspace embedding from r = exp(exp(O (d ))) to r = exp(poly(d )), and generalized it from a constant distortion to a 1 + ε distortion, obtaining overall dimension r = exp(poly(d/ε)).OurTheorem1.2 is still useful though, as a suitably generalized version of it in terms of ε (see Reference [18]for details) is composed with another oblivious subspace embedding in the work of Reference [18], which is important for making their subspace embedding have a dimension r independent of n.

Additional followup work includes Reference [19], which uses our framework for proving Theorem 1.3, and obtains a more general reduction in terms of any embedding for the ℓ 2 -norm; we refer the reader to Reference [19] for further details.

PRELIMINARIES

Throughout this article, we use [n]todenotetheset{1, 2,...,n}.W euse • p to denote the ℓ pnorm of a vector or the entry-wise ℓ p -norm of a matrix. The following lemma is a direct application of Hölder's inequality. Lemma 2.1. For any x ∈ R n and 1 ≤ p ≤ q ≤ 2, we have

For u ∈ R n and 1 ≤ a ≤ b ≤ n,letu a:b denote the vector with ith coordinate equal to u i when a ≤ i ≤ b, and zero otherwise. For a matrix S ∈ R n×m ,weuseS i, * to denote the ith row of S,and S * , j to denote the jth column of S.

For two vectors u, v ∈ R n ,weuse u, v to denote the inner product of u and v.

Definition 2.2. For p ∈ [1, 2], a distribution over r × n matrices Π is an ℓ p oblivious subspace embedding, if for any fixed

Here κ is the distortion of Π.

Throughout the article, we use X ≃ Y to mean that X and Y have the same distribution. We use X Y to denote stochastic dominance, i.e., X Y iff for any

Stable Distribution

Definition 2.3 (p-stable Distribution). A distribution D is p-stable if for any n real numbers a 1 , a 2 ,...,a n ,wehave

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

p-stable distributions exist for any 0 < p ≤ 2 (see, e.g., Reference [28]). We let D p 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 [28].

Lemma 2.4 (Theorem 1.2 in Reference [28]). For

where c p > 0 is a constant that depends only on p.

Tight Bounds for ℓ 1 Oblivious Subspace Embeddings

8:11

The following lemma is established in Reference [24] by using Lemma 2.4.

Lemma 2.5 (Lemma 8 in Reference [24]). For 1 ≤ p < 2,letX p ∼D p . There exists a constant α p such that α p |C | | X p | p , where C is a standard Cauchy random variable and α p is a constant that depends only on p.

Tail Inequalities

We use the following standard form of the Chernoff bound and Bernstein's inequality. Lemma 2.6 (Chernoff Bound). Suppose X 1 , X 2 ,...,X n are independent random variables taking values in [0, 1].LetX = n i=1 X i . For any δ > 0, we have

Var[X i ] be the variance of X . For any t > 0, we have

The following Bernstein-type lower tail inequality is due to Maurer [21].

Lemma 2.8 ( [21]). Suppose X 1 , X 2 ,...,X n are independent positive random variables that satisfy E[X 2 i ] < ∞.LetX = n i=1 X i . For any t > 0, we have

.

We use the following tail inequality of a Gaussian random vector, whose proof can be found in Appendix A. Lemma 2.9. Let (a 1 , a 2 ,...,a n ) be a fixed vector. For i ∈ [n],l e t{X i } be n possibly dependent standard Gaussian random variables. For any 1 ≤ p ≤ 2, we have

Here C p > 1 is an absolute constant that depends only on p.

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

The following corollary is a direct implication of Lemmas 2.10 and 2.5.

where α p is the constant in Lemma 2.5.

For the sum of absolute values of independent standard Cauchy random variables, it is possible to prove an upper tail inequality stronger than that in Lemma 2.10. The proof of the lemma can be found in Appendix A. Lemma 2.12. For i ∈ [n],let{X i } be n independent standard Cauchy random variables. There exists a constant U 1 , such that for any n ≥ 3,

The following corollary is a direct implication of Lemma 2.12 and Lemma 2.5.

Corollary 2.13. Suppose

,l e t{X i } be n independent p-stable random variables. There exists a constant U p that depends only on p, such that for any n ≥ 3,

We use the following lower tail inequality for the sum of absolute values of independent p-stable random variables, whose proof can be found in Appendix A. Lemma 2.14. Suppose 1 ≤ p < 2.Fori ∈ [n],let{X i } be n independent p-stable random variables. There exists a constant L p that depends only on p, such that for sufficiently large n and T ,

ε-nets

We use the following standard ε-net construction in the analysis of our subspace embeddings.

Definition 2.15. For any 1 ≤ p ≤ 2, for a given

.W e say N⊆B is an ε-net of B if for any y ∈ B, there exists a ŷ ∈Nsuch that yŷ p ≤ ε. Lemma 2.16 (see, e.g., Reference [33, p. 74]). For a given A ∈ R n×d , there exists an ε-net

Known ℓ 2 Oblivious Subspace Embeddings

In References [4,10,11,24,25], a series of results on sparse ℓ 2 oblivious subspace embedding are obtained.

Lemma 2.17 (CountSketch [10,24,25]). There exists an ℓ 2 oblivious subspace embedding over O (d 2 ) × n matrices Π, where each column of Π has a single non-zero entry and the distortion κ = 2. Lemma 2.18 (OSNAP [11,25]). 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 (log B 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}.IntheOSNAP embedding, each column is chosen to have s = O (log B 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.19. For any y ∈ R n ,

The following lemma deals with the ℓ p -norm of a vector and its ℓ p -norm after projection using CountSketch or OSNAP. Its proof can be found in Appendix A. Lemma 2.20. For any y ∈ R n and sufficiently large ω, with probability 1 -exp(Ω(ωd log d )),

We remark that since one can permute entries of y arbitrarily, Lemma 2.20 gives a bound for any subset of d 2 entries of y.

Well-conditioned Bases

We recall the definition and some existential results on well-coditioned matrices with respect to ℓ p -norms. Definition 2.21 ((α, β, p)-well-conditioning [14]). For a given matrix U ∈ R n×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) U p ≤ α and (ii) x q ≤ β Ux p for any x ∈ R d . Lemma 2.22. For any full rank matrix A ∈ R n×d and p ∈ [1, 2], there exists a basis matrix U ∈ R n×d of A such that U is (d, 1, p)-well-conditioned.

Proof. By Auerbach's Lemma (see, e.g., Reference [33, p. 75]), there exists a set of basis vectors u 1 , u 2 ,...,u d of the column space of A, and a set of basis vectors v 1 , v 2 ,...,v d , such that

Here, • q is the dual norm of • p . We let U be the matrix whose first column is u 1 • d 1/q , second column is u 2 • d 1/q ,...,and the last column is u d • d 1/q . Clearly,

For any x ∈ R d , since the ith column of U is u i • d 1/q , by Hölder's inequality,

Thus, by Lemma 2.1,

which implies β = 1.

HARDNESS RESULT

The Lower Bound

The goal of this section is to prove Theorem 1.1. We restate it here for convenience.

Theorems 1.1 (Restated). For 1 ≤ p < 2, if a distribution over r × n matrices Π is an ℓ p oblivious subspace embedding, then the distortion

By Yao's minimax principle [37], it suffices to show that there exists a hard distribution A over R n×d such that for any Π ∈ R r ×n ,if

then

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. All entries in other columns are zero. This finishes our construction of A. The following lemma is a direct implication of Lemma 2.9 and our construction. Lemma 3.1. For each column c in A, with probability at least 0.99, the following holds:

p n 1/p . Here C p is the constant in Lemma 2.9.

Tight Bounds for ℓ 1 Oblivious Subspace Embeddings 8:15 Lemma 3.2. For any matrix Π ∈ R r ×n that satisfies the inequality in Equation ( 2), the ℓ p -norm of each column of Π is at most C 2 p κ (4n/d ) 1/p , where C p is the constant in Lemma 2.9.

Proof. Suppose for contradiction that there exists an i ∈ [n] for which the ith column of Π has ℓ p -norm larger than C 2 p κ (4n/d ) 1/p . Consider the vector M j , which is the jth M-column, whose ith entry is a standard Gaussian random variable, i.e., (4n/d ) • (j -1) + 1 ≤ i ≤ (4n/d ) • j.W efirst show that with probability at least 0.99, ΠM j p > C p κ (4n/d ) 1/p . According to the 2-stability of the standard Gaussian distribution, for any k ∈ [r ],

according to Lemma 2.9, with probability at least 0.99,

which implies the condition in Equation ( 2)isviolated. Lemma 3.3. For any matrix Π ∈ R r ×n that satisfies the condition in Equation ( 2), for any 0 ≤ i < log(n/d ), the number of columns in Π with ℓ p -norm larger than C 2 p κ2 (i+1)/p is at most

, where C p is the constant in Lemma 2.9.

Proof. Suppose for contradiction that for some 0 ≤ i < log(n/d ), the number of columns in Π with ℓ p -norm larger than C 2 p κ2 (i+1)/p is larger than

p κ2 (i+1)/p and (ii) π j l is a standard Gaussian random variable. According to Lemma 3.1, with probability at least 0.99, π j p ≤ C p 2 (i+1)/p .Now,weshowthatwithprobabilityatleast0.99,

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 ],

according to Lemma 2.9, with probability at least 0.99, Ππ j p ≥ C -1 p Π * ,l p > C p κ2 (i+1)/p ≥ κ π j p , which implies the condition in Equation ( 2)isviolated.

Lemma 3.4. For any matrix Π ∈ R r ×n that satisfies the condition in Equation ( 2), we have

Proof. We partition the columns of Π into two parts. We let Π L be the submatrix of Π formed by columns with ℓ p -norm at most 2 1/p C 2 p κ and Π H be the submatrix formed by columns with ℓ p -norm larger than 2

For Π L , since all the columns have ℓ p -norm at most 2 1/p C 2 p κ,wehave

where the first inequality follows from Lemma 2.1 and the last equality follows from the fact that Π L has at most n columns. Notice that for any 1

Now consider the vector D, which is the D-column in A. According to Lemma 3.1,withprobability at least 0.99, D p = Ω(n 1/p ). Due to the 2-stability of the standard Gaussian distribution,

According to Lemma 2.9, with probability at least 0.99,

According to the condition in Equation ( 2), we have

Now, we show that the lower bound can be further improved to

We first note that r should be at least d; otherwise, if we take a full-rank matrix A ∈ R n×d ,then 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.

When n ≤ rd 2/(2-p ) ,log 2/p (n/d ) = O (log 2/p r ), which means the lower bound in Equation ( 3) holds. When n > rd 2/(2-p ) , we repeat the argument above but only consider the first rd 2/(2-p ) columns of Π. By doing so, we get a lower bound of

which is always stronger than the lower bound of

Necessity of Dependence on r

The goal of this section is to prove Theorem 3.5.

Theorem 3.5. Let r = exp(4 • 10 4 • (24(U p L -1 p ) 1/p ) 2d ), where U p and L p are the constants in Corollary 2.13 and Lemma 2.14, respectively. For 1 ≤ p < 2, there exists an ℓ p oblivious subspace embedding over r × n matrices Π, where the distortion κ is a constant that depends only on p.

Our construction for the embedding in Theorem 3.5 is actually the same as the dense p-stable embedding in Reference [30](forp = 1) and Theorem 6 in Reference [24](for1< p < 2), whose entries are i.i.d. sampled from the scaled p-stable distribution (r log r ) -1/p D p .

For any given matrix A ∈ R n×d and any x ∈ R d , we show that

According to the definition of the p-stable distribution in Definition 2.3, for any i ∈ [r ],

Since the entries in Π are independent, the entries in the vector ΠAx are also independent. Thus, according to Corollary 2.13, with probability at least 1 -

However, according to Lemma 2.14, by setting T = 200(24(U p L -1 p ) 1/p ) d , with probability at least 1 -

It follows by a union bound that for any

We build an ε-net

Again by a union bound, with probability at least 0.99, we have for any y ∈N,

Condition on the event stated above. Now, we show that for any x ∈ R d ,

For any x ∈ R d ,l e ty = Ax . By homogeneity, we can assume y p = 1. We claim that y can be written as y = y 0 + y 1 + y 2 + ..., where for any i ≥ 0, we have (i)

According to the definition of an ε-net, there exists a vector y 0 ∈Nfor which yy 0 p ≤ ε and y 0 p = 1. If y = y 0 , then we stop. Otherwise, we consider the vector y-y 0 y-y 0 p . Again, we can find a vector ŷ1 ∈Nsuch that y-y 0 y-y 0 p -ŷ1 p ≤ ε and ŷ1 p = 1. Here, we set y 1 = yy 0 p • ŷ1 and continue this process inductively.

It follows that

Thus, Π is a valid ℓ p oblivious subspace embedding with κ ≤ 2(4U p L -1 p ) 1/p , which is a constant that depends only on p.

Tight Bounds for ℓ 1 Oblivious Subspace Embeddings 8:19

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 ∈ R n×d ,letU be a (d, 1, 1)-well-conditioned basis of A. There exists an ℓ 1 oblivious subspace embedding over O (d 2 ) × n matrices Π where each column of Π has two non-zero entries and with probability 0.99, for any x ∈ R d ,

Theorem 4.2. For any given A ∈ R n×d and sufficiently large B,letU 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 (log B d ) non-zero entries and with probability 0.99, for any

Our embedding for Theorems 4.1 and 4.2 can be written as Π = (Π 1 , Π 2 ) T . For Theorem 4.1, Π 1 is sampled from the CountSketch embedding in Lemma 2.17,s c a l e db yad log d factor. For Theorem 4.2, Π 1 is sampled from the OSNAP embedding in Lemma 2.18 with O (B • d log d ) rows, O (log B d ) non-zero entries per column, and scaled by a d log B factor. Suppose Π 1 has R 1 rows. Let R 2 = min{R 1 , d 1.1 }. Π 2 can be written as ΦD : R n → R R 2 as follows:

• Φ is an R 2 × 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 E 1 , E 2 and E 3 ,w h i c hw ew i l l 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.

No Overestimation

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

Here { Xi,j } are dependent standard Cauchy random variables. Since U is a (d, 1, 1)-wellconditioned basis of A,wehave

Tight Bounds for ℓ 1 Oblivious Subspace Embeddings 8:21

where the second inequality follows from Lemma 2.1. Thus, for Theorem 4.1,

since Π 1 is sampled from an ℓ 2 oblivious subspace embedding and scaled by a factor of d log d. For Theorem 4.2, Π 1 Ux 1 ≥ Π 1 Ux 2 ≥ Ω(log B) Ux 1 , since Π 1 is sampled from an ℓ 2 oblivious subspace embedding and scaled by a factor of d log B. Now, we analyze those vectors Ux 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 ∈ R d ,i f (Ux) d 2 +1:n 1 ≥ 0.5 Ux 1 , then with probability at least 1exp(-32d log d ), we have

Proof. Let y = Ux. By homogeneity, we assume y 1 = 1. According to the given condition, we have y d 2 +1:n 1 ≥ 0.5. Notice that y d 2 +1:n ∞ ≤ 1/d 2 , since, otherwise,

,where

Furthermore, by Hölder's inequality, we have

Thus, by Bernstein's inequality in Lemma 2.7,wehave Since

Thus, the number of B i which satisfy

Now consider Π 2 y. According to the 1-stability of the standard Cauchy distribution,

where {X i } are independent standard Cauchy random variables. Notice that conditioned on the event stated above, the number of B i which satisfy

where {X i } are independent standard Cauchy random variables. According to Lemma 2.14, by setting T = 2exp(32d log d ), with probability at least 1 -1/T ,we have ) d .LetE 3 be the event that for all y ∈N,if y d 2 +1:n 1 ≥ 0.5, then Π 2 y 1 ≥ Ω(log d ) y 1 (for Theorem 4.1)or Π 2 y 1 ≥ Ω(log B) y 1 (for Theorem 4.2). Now, we show that E 3 holds with constant probability. Lemma 4.9. E 3 holds with probability at least 0.999. Lemma 5.3. Let E 1 be the event that Π 2 U p ≤ O (d log d ). E 1 holds with probability at least 0.999. Furthermore, conditioned on E 1 , for any x ∈ R d , we have

Let E 2 be the event that for any x ∈ R d ,

Since Π 1 is sampled from an ℓ 2 oblivious subspace embedding with κ = 2, and scaled by a factor of d 2/p-1 , E 2 holds with probability at least 0.999. 5Without loss of generality, we assume

Of course, this order is unknown and is not used by our embeddings. Lemma 5.4. Conditioned on E 2 , for any x ∈ d , have

Proof. By homogeneity, we can assume Ux p = 1. Notice that (Ux) d 2 +1:n ∞ ≤ d -2/p , since otherwise Ux p ≥ (Ux) 1:d 2 p > 1. By Hölder's inequality,

Here the first inequality follows from Lemma 2.1 and the fact that Π 1 Ux has R 1 rows, the second inequality holds, since R 1 ≤ O (d 2 ) and E 2 holds. Lemma 5.5. Conditioned on E 2 , for any x ∈ R d ,i f (Ux) 1:d 2 p ≥ 0.5 Ux p ,t h e n Π 1 Ux p ≥ Ω(1) Ux p .

Proof. Notice that

where the second inequality follows from Lemma 2.1 and the third inequality follows from the condition that (Ux) 1:d 2 p ≥ 0.5 Ux p .T h u s , Π 1 Ux p ≥ Π 1 Ux 2 ≥ Ω(1) Ux p , since Π 1 is sampled from an ℓ 2 oblivious subspace embedding and scaled by a factor of d 2/p-1 .

The proof of the following lemma is almost identical to that of Lemma 4.8. We omit the proof here. Theorem 6.1 can be viewed as the following equivalent two-step procedure. For any given vector y = Ux, 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(-Ω(d 2 ε)),wehave

Thus, by Maurer's inequality in Lemma 2.8, with probability at least 1 -exp(-Ω(d 2 ε)),wehave

The rest 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.ForanygivenA ∈ R n×d ,letU be a (d, 1, p)-well-conditioned basis for A. For any constant 0 < ε < 1, there exists an ℓ p oblivious subspace embedding over O (d 2 ) ×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 ∈ R d ,

The number of rows in Theorems 6.1 and 6.2 cannot be further reduced. It is shown in Reference [26] (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 = Ω(d 2 ). Now, we sketch how to generalize this lower bound to distributions 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 Theorems 6.1 and 6.2 are 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.6, 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 Reference [26] 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(d 2 ) rows. This establishes the desired lower bound of r = Ω(d 2 ).

Improving Sparsity Based on Truncation

In this section, we show how to use a truncation argument to improve the construction in Reference [24].

Before formally stating the construction, we first define the truncation operation. For a given parameter α > 0, for any x ∈ R,define

.

Here, we note some elementary properties of the truncation operation. Lemma 6.3. For a given parameter α > 0, for any x ∈ R, we have

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],l e t{X i } be n independent standard Cauchy random variables. The following holds.

where X is a standard Cauchy random variable.

Now, we are ready to state the main result of this section. Theorem 6.5. There exists an ℓ 1 oblivious subspace embedding over O (d 4 ) × n matrices Π where 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 Reference [24] and the Π 2 part of the embedding for Theorems 4.1 and 4.2, except for replacing standard Cauchy random variables with truncated standard Cauchy random variables. Let R = O (d 4 ) be the number of rows of Π.HereΠ can be written as ΦD : R n → R R , defined as follows:

and all remaining entries 0.

• D is an n × n random diagonal matrix where D i,i = trunc α (X i ).Here{X i } are i.i.d. samples from the standard Cauchy distribution and α < 1/4 is a positive constant. Now, we sketch how to modify the proof of Theorem 2 in Reference [24] to prove the distortion bound of our new embedding.

In the proof of Theorem 2 in Reference [24], the authors define five events: E U , E L , E H , E C and E L . Notice that for our new embedding, the event E C 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 (d 4 log 5 d ), and the definition of the event E L is changed to ΠU L 1 ≤ O (1/(d log 2 d )) correspondingly. Lemma 16 and Lemma 22 in the proof for Theorem 2 in Reference [24] show that E U and E L 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 "approximate 1-stability" of truncated standard Cauchy random variables in Corollary 6.4.

Lemma 13 is changed to the following: Given E L , for any fixed y ∈ Y L ,wehave Pr Πy 1 ≤ 1 4 -α y 1 ≤ exp(-Ω(d log d )).

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 α tobeaconstantsmallerthan1/4. Similarly, the constant 1/8 in Lemma 14 also needs 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 E H and E L , for any y ∈ Y H ,wehave Πy 1 ≥ Ω(α ) y 1 . This finishes our modification to the proof of Theorem 2 in Reference [24]. By applying the truncation argument to p-stable random variables, a similar result can be obtained for ℓ p oblivious subspace embeddings. We let Y i be an indicator variable such that Thus, Π (y 1:d 2 ) p ≤ s 1/p-1/2 (ωd log d ) 1-1/p y 1:d 2 p ≤ s 1/p-1/2 (ωd log d ) 1-1/p y p .