distribution over from which the matrix is drawn such that for and for any unit-length vector , the claim below holds. One can obtain the JL lemma from the distributional version by setting and for some pair u,v both in X. Then the JL lemma follows by a union bound over all such pairs. Speeding up the JL transform Given A, computing the matrix vector product takes time. There has been some work in deriving distributions for which the matrix vector product can be computed in less than time. There are two major lines of work. The first, Fast Johnson Lindenstrauss Transform (FJLT), was introduced by Ailon and Chazelle in 2006. This method allows the computation of the matrix vector product in just for any constant . Another approach is to build a distribution supported over matrices that are sparse. This method allows keeping only an fraction of the entries in the matrix, which means the computation can be done in just time. Furthermore, if the vector has only non-zero entries, the Sparse JL takes time , which may be much less than the time used by Fast JL. Tensorized random projections It is possible to combine two JL matrices by taking the so-called face-splitting product, which is defined as the tensor products of the rows (was proposed by V. Slyusar in 1996 for radar and digital antenna array applications). More directly, let and be two matrices. Then the face-splitting product is This idea of tensorization was used by Kasiviswanathan et al. 2010 for differential privacy. JL matrices defined like this use fewer random bits, and can be applied quickly to vectors that have tensor structure, due to the following identity: , where is the element-wise (Hadamard) product. Such computations have been used to efficiently compute polynomial kernels and many other . In 2020 it was shown that if the matrices are independent or Gaussian matrices, the combined matrix satisfies the distributional JL lemma if the number of rows is at least . For large this is as good as the completely random Johnson-Lindenstrauss, but a matching lower bound in the same paper shows that this exponential dependency on is necessary. Alternative JL constructions are suggested to circumvent this. See also Random projection Restricted isometry property Notes References Further reading . Journal version of a paper previously appearing at PODC 2001. . . Lemmas Metric geometry