0pt0pt 1in*1 subsection

# An Introduction to Johnson–Lindenstrauss Transforms

Casper Benjamin Freksen Work done while at the Computer Science Department,
Aarhus University<EMAIL_ADDRESS>
(28th August 2024)

###### Abstract

Johnson–Lindenstrauss Transforms are powerful tools for reducing the
dimensionality of data while preserving key characteristics of that data, and
they have found use in many fields from machine learning to differential
privacy and more. This note explains what they are; it gives an overview of
their use and their development since they were introduced in the 1980s; and
it provides many references should the reader wish to explore these topics
more deeply.

The text was previously a main part of the introduction of my PhD thesis
[(78)], but it has been adapted to be self contained and serve as a (hopefully
good) starting point for readers interested in the topic.

##  Chapter 1 The Why, What, and How

###  1 The Problem

Consider the following scenario: We have some data that we wish to process but
the data is too large, e.g. processing the data takes too much time, or
storing the data takes too much space. A solution would be to compress the
data such that the valuable parts of the data are kept and the other parts
discarded. Of course, what is considered valuable is defined by the data
processing we wish to apply to our data. To make our scenario more concrete
let us say that our data consists of vectors in a high dimensional Euclidean
space, $\mathbb{R}^{d}$, and we wish to find a transform to embed these
vectors into a lower dimensional space, $\mathbb{R}^{m}$, where $m\ll d$, so
that we can apply our data processing in this lower dimensional space and
still get meaningful results. The problem in this more concrete scenario is
known as _dimensionality reduction_.

As an example, let us pretend to be a library with a large corpus of texts and
whenever a person returns a novel that they liked, we would like to recommend
some similar novels for them to read next. Or perhaps we wish to be able to
automatically categorise the texts into groups such as fiction/non-fiction or
child/young-adult/adult literature. To be able to use the wealth of research
on similarity search and classification we need a suitable representation of
our texts, and here a common choice is called bag-of-words. For a language or
vocabulary with $d$ different words, the bag-of-words representation of a text
$t$ is a vector $x\in\mathbb{R}^{d}$ whose $i$th entry is the number of times
the $i$th word occurs in $t$. For example, if the language is just [“be”,
“is”, “not”, “or”, “question”, “that”, “the”, “to”] then the text “to be or
not to be” is represented as $(2,0,1,1,0,0,0,2)^{\transp}$. To capture some of
the context of the words, we can instead represent a text as the count of so-
called $n$-grams111These are sometimes referred to as shingles., which are
sequences of $n$ consecutive words, e.g. the 2-grams of “to be or not to be”
are [“to be”, “be or”, “or not”, “not to”, “to be”], and we represent such a
bag-of-$n$-grams as a vector in $\mathbb{R}^{(d^{n})}$. To compare two texts
we compute the distance between the vectors of those texts, because the
distance between vectors of texts with mostly the same words (or $n$-grams) is
small222We might wish to apply some normalisation to the vectors, e.g. tf-idf
[(134)], so that rare words are weighted more and text length is less
significant.. For a more realistic language such as English with $d\approx
171000$ words [(180)] or that of the “English” speaking internet at $d\gtrsim
4790000$ words [(208)], the dimension quickly becomes infeasable. While we
only need to store the nonzero counts of words (or $n$-grams) to represent a
vector, many data processing algorithms have a dependency on the vector
dimension $d$ (or $d^{n}$), e.g. using nearest-neighbour search to find
similar novels to recommend [(6)] or using neural networks to classify our
texts [(167)]. These algorithms would be infeasible for our library use case
if we do not first reduce the dimension of our data.

A seemingly simple approach would be to select a subset of the coordinates,
say if the data contained redundant or irrelevant coordinates. This is known
as _feature selection_ [(105), (93), (100)], and can be seen as
projecting333Here we slightly bend the definition of projection in the sense
that we represent a projected vector as the coefficients of the of the linear
combination of the (chosen) basis of the subspace we project onto, rather than
as the result of that linear combination. If $A\in\mathbb{R}^{m\times d}$ is a
matrix with the subspace basis vectors as rows, we represent the projection of
a vector $x\in\mathbb{R}^{d}$ as the result of $Ax\in\mathbb{R}^{m}$ rather
than $A^{\transp}Ax\in\mathbb{R}^{d}$. onto an axis aligned subspace, i.e. a
subspace whose basis is a subset of $\\{e_{1},\dotsc,e_{d}\\}$.

We can build upon _feature selection_ by choosing the basis from a richer set
of vectors. For instance, in principal component analysis as dimensionality
reduction (PCA) [(154), (90)] we let the basis of the subspace be the $m$
first eigenvectors (ordered decreasingly by eigenvalue) of $X^{\transp}X$,
where the rows of $X\in\mathbb{R}^{n\times d}$ are our $n$ high dimensional
vectors444Here it is assumed that the mean of our vectors is $\mathbf{0}$,
otherwise the mean vector of our vectors should be subtracted from each of the
rows of $X$.. This subspace maximises the variance of the data in the sense
that the first eigenvector is the axis that maximises variance and subsequent
eigenvectors are the axes that maximise variance subject to being orthogonal
to all previous eigenvectors [(135), (93), (101)].

But what happens if we choose a basis randomly?

###  2 The Johnson–Lindenstrauss Lemma(s)

In JL84555Or rather in 1982 as that was when a particular “Conference in
Modern Analysis and Probability” was held at Yale University, but the
proceedings were published in JL84. it was discovered that projecting onto a
random basis approximately preserves pairwise distances with high probability.
In order to prove a theorem regarding Lipschitz extensions of functions from
metric spaces into $\ell_{2}$, Johnson:1984:EoLMiaHS (JL84) proved the
following lemma.

######  Lemma 1.1 (Johnson–Lindenstrauss lemma (Johnson:1984:EoLMiaHS, JL84)).

For every $d\in\mathbb{N}_{1},\varepsilon\in(0,1)$, and
$X\subset\mathbb{R}^{d}$, there exists a function $f\colon
X\to\mathbb{R}^{m}$, where $m=\Theta(\varepsilon^{-2}\log|X|)$ such that for
every $x,y\in X$,

$\bigl{|}\,\|f(x)-f(y)\|_{2}^{2}-\|x-y\|_{2}^{2}\,\bigr{|}\leq\varepsilon\|x-y\|_{2}^{2}.$
(1)

###### Proof.

The gist of the proof is to first define $f(x)\coloneq(d/m)^{1/2}Ax$, where
$A\in\mathbb{R}^{m\times d}$ are the first $m$ rows of a random orthogonal
matrix. They then showed that $f$ preserves the norm of any vector with high
probability, or more formally that the distribution of $f$ satisfies the
following lemma.

######  Lemma 1.2 (Distributional Johnson–Lindenstrauss lemma
(Johnson:1984:EoLMiaHS, JL84)).

For every $d\in\mathbb{N}_{1}$ and $\varepsilon,\delta\in(0,1)$, there exists
a probability distribution $\mathcal{F}$ over linear functions
$f\colon\mathbb{R}^{d}\to\mathbb{R}^{m}$, where
$m=\Theta(\varepsilon^{-2}\log\frac{1}{\delta})$ such that for every
$x\in\mathbb{R}^{d}$,

$\Pr_{f\sim\mathcal{F}}\Bigl{[}\,\bigl{|}\,\|f(x)\|_{2}^{2}-\|x\|_{2}^{2}\,\bigr{|}\leq\varepsilon\|x\|_{2}^{2}\,\Bigr{]}\geq
1-\delta.$ (2)

By choosing $\delta=1/|X|^{2}$, we can union bound over all pairs of vectors
$x,y\in X$ and show that their distance (i.e. the $\ell_{2}$ norm of the
vector $x-y$) is preserved simultaneously for all pairs with probability at
least $1-\binom{|X|}{2}/|X|^{2}>1/2$. ∎

We will use the term Johnson–Lindenstrauss distribution (JLD) to refer to a
distribution $\mathcal{F}$ that is a witness to lemma 1.2, and the term
Johnson–Lindenstrauss transform (JLT) to a function $f$ witnessing lemma 1.1,
e.g. a sample of a JLD.

A few things to note about these lemmas are that when sampling a JLT from a
JLD it is independent of the input vectors themselves; the JLT is only
dependendent on the source dimension $d$, number of vectors $|X|$, and
distortion $\varepsilon$. This allows us to sample a JLT without having access
to the input data, e.g. to compute the JLT before the data exists, or to
compute the JLT in settings where the data is too large to store on or move to
a single machine666Note that the sampled transform only satisfies lemma 1.1
with some (high) probability. In the setting where we have access to the data,
we can avoid this by resampling the transform until it satisfies lemma 1.1 for
our specific dataset.. Secondly, the target dimension $m$ is independent from
the source dimension $d$, meaning there are potentially very significant
savings in terms of dimensionality, which will become more apparent shortly.

Compared to PCA, the guarantees that JLTs give are different: PCA finds an
embedding with optimal average distortion of distances between the original
and the embedded vectors, i.e.
$A_{\mathsf{PCA}}=\operatorname*{arg\,min}_{A\in\mathbb{R}^{m\times
d}}\sum_{x\in X}\mathopen{\lVert}A^{\transp}Ax-x\mathclose{\rVert}_{2}^{2}$
(Jolliffe:2002:PCA, Jol02), whereas a JLT bounds the worst case distortion
between the distances within the original space and distances within the
embedded space. As for computing the transformations, a common777There are
also other approaches that compute an approximate PCA more efficiently than
this, e.g. (Rokhlin:2009:aRAfPCA, RST09, AH14). way of performing PCA is done
by computing the covariance matrix and then performing eigenvalue
decomposition, which results in a running time888Here $\omega\lesssim 2.373$
is the exponent from the running time of squared matrix multiplication
(Williams:2012:MMFtCW, Wil12, Le␣14). of
$\mathcal{O}(\mathopen{\lvert}X\mathclose{\rvert}d^{2}+d^{\omega})$
(Demmel:2007:FLAiS, DDH07), compared to
$\Theta(\mathopen{\lvert}X\mathclose{\rvert}d\log d)$ and999Here
$\mathopen{\lVert}X\mathclose{\rVert}_{0}$ is the total number of nonzero
entries in the set of vectors $X$, i.e.
$\mathopen{\lVert}X\mathclose{\rVert}_{0}\coloneq\sum_{x\in
X}\mathopen{\lVert}x\mathclose{\rVert}_{0}$ where
$\mathopen{\lVert}x\mathclose{\rVert}_{0}\coloneq\mathopen{\lvert}\\{i\mid
x_{i}\neq 0\\}\mathclose{\rvert}$ for a vector $x$.
$\Theta(\mathopen{\lVert}X\mathclose{\rVert}_{0}\varepsilon^{-1}\log\mathopen{\lvert}X\mathclose{\rvert})$
that can be achieved by the JLDs “FJLT” and “Block SparseJL”, respectively,
which will be introduced in section 4. As such, PCA and JLDs are different
tools appropriate for different scenarios (see e.g.
(Breger:2019:otRAoMCMRIwOP, Bre+19) where the two techniques are compared
empirically in the domain of medicinal imaging; see also (Dasgupta:2000:EwRP,
Das00, BM01, FB03, FM03, Tan+05, DB06, Arp+14, Woj+16, Bre+20)). That is not
to say the two are mutually exclusive, as one could apply JL to quickly shave
off some dimensions followed by PCA to more carefully reduce the remaining
dimensions (e.g. Rokhlin:2009:aRAfPCA, RST09, HMT11, Xie+16, Yan+20). For more
on PCA, we refer the interested reader to (Jolliffe:2002:PCA, Jol02), which
provides an excellent in depth treatment of the topic.

One natural question to ask with respect to JLDs and JLTs is if the target
dimension is optimal. This is indeed the case as Kane:2011:AOEJLF (KMN11,
JW13) independently give a matching lower bound of
$m=\Omega(\varepsilon^{-2}\log\frac{1}{\delta})$ for any JLD that satisfies
lemma 1.2, and Larsen:2017:OotJLL (LN17) showed that the bound in lemma 1.1 is
optimal up constant factors for almost the entire range of $\varepsilon$ with
the following theorem.

######  Theorem 1.3 ((Larsen:2017:OotJLL, LN17)).

For any integers $n,d\geq 2$ and
$\lg^{0.5001}n/\sqrt{\min\\{d,n\\}}<\varepsilon<1$ there exists a set of
points $X\subset\mathbb{R}^{d}$ of size $n$ such that any function
$f:X\to\mathbb{R}^{m}$ satisfying eq. 1 must have

$m=\Omega\bigl{(}\varepsilon^{-2}\log(\varepsilon^{2}n)\bigr{)}.$ (3)

Note that if $\varepsilon\leq\sqrt{\lg n/\min\\{d,n\\}}$ then
$\varepsilon^{-2}\lg n\geq\min\\{d,n\\}$, and embedding $X$ into dimension
$\min\\{d,|X|\\}$ can be done isometrically by the identity function or by
projecting onto $\operatorname{span}(X)$, respectively.

Alon:2017:OCoAIPaDR (AK17) extended the result in (Larsen:2017:OotJLL, LN17)
by providing a lower bound for the gap in the range of $\varepsilon$.

######  Theorem 1.4 ((Alon:2017:OCoAIPaDR, AK17)).

There exists an absolute positive constant $0<c<1$ so that for any $n\geq
d>cd\geq m$ and for all $\varepsilon\geq 2/\sqrt{n}$, there exists a set of
points $X\subset\mathbb{R}^{d}$ of size $n$ such that any function
$f:X\to\mathbb{R}^{m}$ satisfying eq. 1 must have

$m=\Omega\bigl{(}\varepsilon^{-2}\log(2+\varepsilon^{2}n)\bigr{)}.$ (4)

It is, however, possible to circumvent these lower bounds by restricting the
set of input vectors we apply the JLTs to. For instance, Klartag:2005:EPaRP
(KM05, Dir16, BDN15a) provide target dimension upper bounds for JLTs that are
dependent on statistical properties of the input set $X$. Similarly, JLTs can
be used to approximately preserve pairwise distances simultaneously for an
entire subspace using $m=\Theta(\varepsilon^{-2}t\log(t/\varepsilon))$, where
$t$ denotes the dimension of the subspace (Sarlos:2006:IAAfLMvRP, Sar06),
which is a great improvement when $t\ll|X|,d$.

Another useful property of JLTs is that they approximately preserve dot
products. Corollary 1.5 formalises this property in terms of lemma 1.1, though
it is sometimes (Sarlos:2006:IAAfLMvRP, Sar06, AV06) stated in terms of lemma
1.2. Corollary 1.5 has a few extra requirements on $f$ and $X$ compared to
lemma 1.1, but these are not an issue if the JLT is sampled from a JLD, or if
we add the negations of all our vectors to $X$, which only slightly increases
the target dimension.

######  Corollary 1.5.

Let $d,\varepsilon,X$ and $f$ be as defined in lemma 1.1, and furthermore let
$f$ be linear. Then for every $x,y\in X$, if $-y\in X$ then

$|\mathopen{\langle}f(x),f(y)\mathclose{\rangle}-\mathopen{\langle}x,y\mathclose{\rangle}|\leq\varepsilon\|x\|_{2}\|y\|_{2}.$
(5)

###### Proof.

If at least one of $x$ and $y$ is the $\mathbf{0}$-vector, then eq. 5 is
trivially satisfied as $f$ is linear. If $x$ and $y$ are both unit vectors
then we assume w.l.o.g. that
$\mathopen{\lVert}x+y\mathclose{\rVert}_{2}\geq\mathopen{\lVert}x-y\mathclose{\rVert}_{2}$
and we proceed as follows, utilising the polarisation identity:
$4\mathopen{\langle}u,v\mathclose{\rangle}=\|u+v\|_{2}^{2}-\|u-v\|_{2}^{2}$.

$\displaystyle
4\bigl{|}\mathopen{\langle}f(x),f(y)\mathclose{\rangle}-\mathopen{\langle}x,y\mathclose{\rangle}\bigr{|}$
$\displaystyle=\bigl{|}\|f(x)+f(y)\|_{2}^{2}-\|f(x)-f(y)\|_{2}^{2}-4\mathopen{\langle}x,y\mathclose{\rangle}\bigr{|}$
$\displaystyle\leq\bigl{|}(1+\varepsilon)\|x+y\|_{2}^{2}-(1-\varepsilon)\|x-y\|_{2}^{2}-4\mathopen{\langle}x,y\mathclose{\rangle}\bigr{|}$
$\displaystyle=\bigl{|}4\mathopen{\langle}x,y\mathclose{\rangle}+\varepsilon(\|x+y\|_{2}^{2}+\|x-y\|_{2}^{2})-4\mathopen{\langle}x,y\mathclose{\rangle}\bigr{|}$
$\displaystyle=\varepsilon(2\|x\|_{2}^{2}+2\|y\|_{2}^{2})$
$\displaystyle=4\varepsilon.$

Otherwise we can reduce to the unit vector case.

$\displaystyle|\mathopen{\langle}f(x),f(y)\mathclose{\rangle}-\mathopen{\langle}x,y\mathclose{\rangle}|$
$\displaystyle=\biggl{|}\mathopen{\Big{missing}}\langle
f\bigl{(}\frac{x}{\|x\|_{2}}\bigr{)},f\bigl{(}\frac{y}{\|y\|_{2}}\bigr{)}\mathclose{\Big{missing}}\rangle-\mathopen{\Big{missing}}\langle\frac{x}{\|x\|_{2}},\frac{y}{\|y\|_{2}}\mathclose{\Big{missing}}\rangle\biggr{|}\|x\|_{2}\|y\|_{2}$
$\displaystyle\leq\varepsilon\|x\|_{2}\|y\|_{2}.$

∎

9

Before giving an overview of the development of JLDs in section 4, let us
return to our scenario and example in section 1 and show the wide variety of
fields where dimensionality reduction via JLTs have found use. Furthermore, to
make us more familiar with lemma 1.1 and its related concepts, we will pick a
few examples of how the lemma is used.

###  3 The Use(fulness) of Johnson–Lindenstrauss

JLDs and JLTs have found uses and parallels in many fields and tasks, some of
which we will list below. Note that there are some overlap between the
following categories, as e.g. (Fern:2003:RPfHDDCaCEA, FB03) uses a JLD for an
_ensemble_ of weak learners to learn a mixture of Gaussians _clustering_ , and
(Pilanci:2015:RSoCPwSG, PW15) solves _convex optimisation_ problems in a way
that gives _differential privacy_ guarantees.

Nearest-neighbour search

have benefited from the Johnson–Lindenstrauss lemmas on multiple occasions,
including (Kleinberg:1997:TAfNNSiHD, Kle97, KOR00), which used JL to randomly
partition space rather than reduce the dimension, while others
(Ailon:2009:tFJLTaANN, AC09, HIM12) used the dimensionality reduction
properties of JL more directly. Variations on these results include
consructing locality sensitive hashing schemes (Datar:2004:LSHSBopSD, Dat+04)
and finding nearest neighbours without false negatives
(Sankowski:2017:ANNSwFNflfc, SW17).

Clustering

with results in various sub-areas such as mixture of Gaussians
(Dasgupta:1999:LMoG, Das99, FB03, UDS07), subspace clustering
(Heckel:2017:DRSC, HTB17), graph clustering (Sakai:2009:FSCwRPaS, SI09,
Guo+20), self-organising maps (Ritter:1989:SOSM, RK89, Kas98), and $k$-means
(Becchetti:2019:ODRfkMBSatJLL, Bec+19, Coh+15, Bou+14, Liu+17, SF18), which
will be explained in more detail in section 3.1.

Outlier detection

where there have been works for various settings of outliers, including
approximate nearest-neighbours (deVries:2010:FLAiVHDS, dVCH10, SZK15) and
Gaussian vectors (Navarro-Esteban:2020:HDODuRP, NC20), while
(Zhao:2020:SUODtSUOD, Zha+20) uses JL as a preprocessor for a range of outlier
detection algorithms in a distributed computational model, and
(Aouf:2012:ADODuRSP, AP12) evaluates the use of JLTs for outlier detection of
text documents.

Ensemble learning

where independent JLTs can be used to generate training sets for weak learners
for bagging (Schclar:2009:RPEC, SR09) and with the voting among the learners
weighted by how well a given JLT projects the data (Cannings:2017:RPEC, CS17,
Can20). The combination of JLTs with multiple learners have also found use in
the regime of learning high-dimensional distributions from few datapoints
(i.e. $\mathopen{\lvert}X\mathclose{\rvert}\ll d$)
(Durrant:2013:RPaRLaLDEfFOtD, DK13, ZK19, Niy+20).

Adversarial machine learning

where Johnson–Lindenstrauss can both be used to defend against adversarial
input (Nguyen:2016:TRMuRP, Ngu+16, Wee+19, Tar+19) as well as help craft such
attacks (Li:2020:PaPDBBA, Li+20).

Miscellaneous machine learning

where, in addition to the more specific machine learning topics mentioned
above, Johnson–Lindenstrauss has been used together with support vector
machines (Calderbank:2009:CLUSDRaLitMD, CJS09, Pau+14, LL20), Fisher’s linear
discriminant (Durrant:2010:CFLDACoRPD, DK10), and neural networks
(Schmidt:2018:SRPLGPDRfDL, Sch18), while (Kim:2020:ARPGwVR, KY20) uses JL to
facilitate stochastic gradient descent in a distributed setting.

Numerical linear algebra

with work focusing on low rank approximation (Cohen:2015:DRfkMCaLRA, Coh+15,
MM20), canonical correlation analysis (Avron:2014:EDRfCCA, Avr+14), and
regression in a local (Thanei:2017:RPfLSR, THM17, MM09, Kab14, Sla17) and a
distributed (Heinze:2016:DLDSEuRP, HMM16) computational model. Futhermore, as
many of these subfields are related some papers tackle multiple numerical
linear algebra problems at once, e.g. low rank approximation, regression, and
approximate matrix multiplication (Sarlos:2006:IAAfLMvRP, Sar06), and a line
of work (Meng:2013:LDSEiISTaAtRLR, MM13, CW17, NN13) have used JLDs to perform
subspace embeddings which in turn gives algorithms for $\ell_{p}$ regression,
low rank approximation, and leverage scores.

For further reading, there are surveys (Mahoney:2011:RAfMaD, Mah11, HMT11,
Woo14) covering much of JLDs’ use in numerical linear algebra.

Convex optimisation

in which Johnson–Lindenstrauss has been used for (integer) linear programming
(Vu:2015:UtJLLiLaIP, VPL15) and to improve a cutting plane method for finding
a point in a convex set using a separation oracle (TatLee:2015:aFCPMaiIfCaCO,
TSC15, Jia+20). Additionally, (Zhang:2013:RtOSbDRP, Zha+13) studies how to
recover a high-dimensional optimisation solution from a JL dimensionality
reduced one.

Differential privacy

have utilised Johnson–Lindenstrauss to provide sanitised solutions to the
linear algebra problems of variance estimation (Blocki:2012:tJLTIPDP, Blo+12),
regression (Sheffet:2019:DPOLS, She19, SKD19, ZLW09), Euclidean distance
estimation (Kenthapadi:2013:PvtJLT, Ken+13, LKR06, GLK13, Tur+08, Xu+17), and
low-rank factorisation (Upadhyay:2018:tPoPfLRF, Upa18), as well as convex
optimisation (Pilanci:2015:RSoCPwSG, PW15, KJ16), collaborative filtering
(Yang:2017:PPCFvtJLT, Yan+17) and solutions to graph-cut queries
(Blocki:2012:tJLTIPDP, Blo+12, Upa13). Furthermore,
(Upadhyay:2015:REFJLTwAiDPaCS, Upa15) analysis various JLDs with respect to
differential privacy and introduces a novel one designed for this purpose.

Neuroscience

where it is used as a tool to process data in computational neuroscience
(Ganguli:2012:CSSaDiNIPaDA, GS12, ALG13), but also as a way of modelling
neurological processes (Ganguli:2012:CSSaDiNIPaDA, GS12, ALG13, All+14, PP14).
Interestingly, there is some evidence (Murthy:2008:TORSitDMB, MFL08, SA09,
Car+13) to suggest that JL-like operations occur in nature, as a large set of
olifactory sensory inputs (projection neurons) map onto a smaller set of
neurons (Kenyon cells) in the brains of fruit flies, where each Kenyon cell is
connected to a small and seemingly random subset of the projection neurons.
This is reminiscent of sparse JL constructions, which will be introduced in
section 4.1, though I am not neuroscientifically adept enough to judge how far
these similarities between biological constructs and randomised linear algebra
extend.

Other topics

where Johnson–Lindenstrauss have found use include graph sparsification
(Spielman:2011:GSbER, SS11), graph embeddings in Euclidean spaces
(Frankl:1988:tJLLatSosG, FM88), integrated circuit design
(Vempala:1998:RPanAtVLSI, Vem98), biometric authentication
(Arpit:2014:aAoRPiCB, Arp+14), and approximating minimum spanning trees (Har-
Peled:2000:WCCAtMST, HI00).

For further examples of Johnson–Lindenstrauss use cases, please see
(Indyk:2001:AAoLDGE, Ind01, Vem04).

Now, let us dive deeper into the areas of clustering and streaming algorithms
to see how Johnson–Lindenstrauss can be used there.

####  3.1 Clustering

Clustering can be defined as partitioning a dataset such that elements are
similar to elements in the same partition while being dissimilar to elements
in other partitions. A classic clustering problem is the so-called $k$-means
clustering where the dataset $X\subset\mathbb{R}^{d}$ consists of points in
Euclidean space. The task is to choose $k$ cluster centers
$c_{1},\dotsc,c_{k}$ such that they minimise the sum of squared distances from
datapoints to their nearest cluster center, i.e.

$\operatorname*{arg\,min}_{c_{1},\dotsc,c_{k}}\sum_{x\in
X}\min_{i}\|x-c_{i}\|_{2}^{2}.$ (6)

This creates a Voronoi partition, as each datapoint is assigned to the
partition corresponding to its nearest cluster center. We let $X_{i}\subseteq
X$ denote the set of points that have $c_{i}$ as their closest center. It is
well known that for an optimal choice of centers, the centers are the means of
their corresponding partitions, and furthermore, the cost of any choice of
centers is never lower than the sum of squared distances from datapoints to
the mean of their assigned partition, i.e.

$\sum_{x\in X}\min_{i}\|x-c_{i}\|_{2}^{2}\geq\sum_{i=1}^{k}\sum_{x\in
X_{i}}\Bigl{\|}x-\frac{1}{|X_{i}|}\sum_{y\in X_{i}}y\Bigr{\|}_{2}^{2}.$ (7)

It has been shown that finding the optimal centers, even for $k=2$, is NP-hard
(Aloise:2009:NPHoESoSC, Alo+09, Das08); however, various heuristic approaches
have found success such as the commonly used Lloyd’s algorithm
(Lloyd:1982:LSQiPCM, Llo82). In Lloyd’s algorithm, after initialising the
centers in some way we iteratively improve the choice of centers by assigning
each datapoint to its nearest center and then updating the center to be the
mean of the datapoints assigned to it. These two steps can then be repeated
until some termination criterion is met, e.g. when the centers have converged.
If we let $t$ denote the number of iterations, then the running time becomes
$\mathcal{O}(t|X|kd)$, as we use $\mathcal{O}(|X|kd)$ time per iteration to
assign each data point to its nearest center. We can improve this running time
by quickly embedding the datapoints into a lower dimensional space using a JLT
and then running Lloyd’s algorithm in this smaller space. The Fast
Johnson–Lindenstrauss Transform, which we will introduce later, can for many
sets of parameters embed a vector in $\mathcal{O}(d\log d)$ time reducing the
total running time to $\mathcal{O}(|X|d\log d+t|X|k\varepsilon^{-2}\log|X|)$.
However, for this to be useful we need the partitioning of points in the lower
dimensional space to correspond to an (almost) equally good partition in the
original higher dimensional space.

In order to prove such a result we will use the following lemma, which shows
that the cost of a partitioning, with its centers chosen as the means of the
partitions, can be written in terms of pairwise distances between datapoints
in the partitions.

######  Lemma 1.6.

Let $k,d\in\mathbb{N}_{1}$ and $X_{i}\subset\mathbb{R}^{d}$ for101010We use
$[k]$ to denote the set $\\{1,\dotsc,k\\}$. $i\in[k].$

$\sum_{i=1}^{k}\sum_{x\in X_{i}}\Bigl{\|}x-\frac{1}{|X_{i}|}\sum_{y\in
X_{i}}y\Bigr{\|}_{2}^{2}=\frac{1}{2}\sum_{i=1}^{k}\frac{1}{|X_{i}|}\sum_{x,y\in
X_{i}}\|x-y\|_{2}^{2}.$ (8)

The proof of footnote 10 consists of various linear algebra manipulations and
can be found in section 5. Now we are ready to prove the following
proposition, which states that if we find a partitioning whose cost is within
$(1+\gamma)$ of the optimal cost in low dimensional space, that partitioning
when moving back to the high dimensional space is within
$(1+4\varepsilon)(1+\gamma)$ of the optimal cost there.

######  Proposition 1.7.

Let $k,d\in\mathbb{N}_{1}$, $X\subset\mathbb{R}^{d}$, $\varepsilon\leq 1/2$,
$m=\Theta(\varepsilon^{-2}\log|X|)$, and $f:X\to\mathbb{R}^{m}$ be a JLT. Let
$Y\subset\mathbb{R}^{m}$ be the embedding of $X$. Let $\kappa_{m}^{*}$ denote
the optimal cost of a partitioning of $Y$, with respect to eq. 6. Let
$Y_{1},\dotsc,Y_{k}\subseteq Y$ be a partitioning of $Y$ with cost
$\kappa_{m}$ such that $\kappa_{m}\leq(1+\gamma)\kappa_{m}^{*}$ for some
$\gamma\in\mathbb{R}$. Let $\kappa_{d}^{*}$ be the cost of an optimal
partitioning of $X$ and $\kappa_{d}$ be the cost of the partitioning
$X_{1},\dotsc,X_{k}\subseteq X$, satisfying $Y_{i}=\\{f(x)\mid x\in X_{i}\\}$.
Then

$\kappa_{d}\leq(1+4\varepsilon)(1+\gamma)\kappa_{d}^{*}.$ (9)

###### Proof.

Due to footnote 10 and the fact that $f$ is a JLT we know that the cost of our
partitioning is approximately preserved when going back to the high
dimensional space, i.e. $\kappa_{d}\leq\kappa_{m}/(1-\varepsilon)$.
Furthermore, since the cost of $X$’s optimal partitioning when embedded down
to $Y$ cannot be lower than the optimal cost of partitioning $Y$, we can
conclude $\kappa_{m}^{*}\leq(1+\varepsilon)\kappa_{d}^{*}$. Since
$\varepsilon\leq 1/2$, we have
$1/(1-\varepsilon)=1+\varepsilon/(1-\varepsilon)\leq 1+2\varepsilon$ and also
$(1+\varepsilon)(1+2\varepsilon)=(1+3\varepsilon+2\varepsilon^{2})\leq
1+4\varepsilon$. Combining these inequalities we get

$\displaystyle\kappa_{d}$ $\displaystyle\leq\frac{1}{1-\varepsilon}\kappa_{m}$
$\displaystyle\leq(1+2\varepsilon)(1+\gamma)\kappa_{m}^{*}$
$\displaystyle\leq(1+2\varepsilon)(1+\gamma)(1+\varepsilon)\kappa_{d}^{*}$
$\displaystyle\leq(1+4\varepsilon)(1+\gamma)\kappa_{d}^{*}.$

∎

By pushing the constant inside the $\Theta$-notation, proposition 1.7 shows
that we can achieve a $(1+\varepsilon)$ approximation111111Here the
approximation ratio is between any $k$-means algorithm running on the high
dimensional original data and on the low dimensional projected data. of
$k$-means with
$m=\Theta(\varepsilon^{-2}\log\mathopen{\lvert}X\mathclose{\rvert})$. However,
by more carefully analysing which properties are needed, we can improve upon
this for the case where $k\ll\mathopen{\lvert}X\mathclose{\rvert}$.
Boutsidis:2014:RDRfkMC (Bou+14) showed that projecting down to a target
dimension of $m=\Theta(\varepsilon^{-2}k)$ suffices for a slightly worse
$k$-means approximation factor of $(2+\varepsilon)$. This result was expanded
upon in two ways by Cohen:2015:DRfkMCaLRA (Coh+15), who showed that projecting
down to $m=\Theta(\varepsilon^{-2}k)$ achieves a $(1+\varepsilon)$
approximation ratio, while projecting all the way down to
$m=\Theta(\varepsilon^{-2}\log k)$ still suffices for a $(9+\varepsilon)$
approximation ratio. The $(1+\varepsilon)$ case has recently been further
improved upon by both Becchetti:2019:ODRfkMBSatJLL (Bec+19), who have shown
that one can achieve the $(1+\varepsilon)$ approximation ratio for $k$-means
when projecting down to $m=\Theta\bigl{(}\varepsilon^{-6}(\log
k+\log\log|X|)\log\varepsilon^{-1}\bigr{)}$, and by
Makarychev:2019:PoJLTfkMakMC (MMR19), who independently have proven an even
better bound of $m=\Theta\bigl{(}\varepsilon^{-2}\log k/\varepsilon\bigr{)}$,
essentially giving a “best of worlds” result with respect to
(Cohen:2015:DRfkMCaLRA, Coh+15).

For an overview of the history of $k$-means clustering, we refer the
interested reader to (Bock:2008:OaEotkMAiCA, Boc08).

####  3.2 Streaming

The field of streaming algorithms is characterised by problems where we
receive a sequence (or stream) of items and are queried on the items received
so far. The main constraint is usually that we only have limited access to the
sequence, e.g. that we are only allowed one pass over it, and that we have
very limited space, e.g. polylogarithmic in the length of the stream. To make
up for these constraints we are allowed to give approximate answers to the
queries. The subclass of streaming problems we will look at here are those
where we are only allowed a single pass over the sequence and the items are
updates to a vector and a query is some statistic on that vector, e.g. the
$\ell_{2}$ norm of the vector. More formally, and to introduce the notation,
let $d\in\mathbb{N}_{1}$ be the number of different items and let
$T\in\mathbb{N}_{1}$ be the length of the stream of updates
$(i_{j},v_{j})\in[d]\times\mathbb{R}$ for $j\in[T]$, and define the vector $x$
at time $t$ as $x^{(t)}\coloneq\sum_{j=1}^{t}v_{j}e_{i_{j}}$. A query $q$ at
time $t$ is then a function of $x^{(t)}$, and we will omit the (t) superscript
when referring to the current time.

There are a few common variations on this model with respect to the updates.
In the _cash register_ model or _insertion only_ model $x$ is only incremented
by bounded integers, i.e. $v_{j}\in[M]$, for some $M\in\mathbb{N}_{1}$. In the
_turnstile_ model, $x$ can only be incremented or decremented by bounded
integers, i.e. $v_{j}\in\\{-M,\dotsc,M\\}$ for some $M\in\mathbb{N}_{1}$, and
the _strict turnstile_ model is as the turnstile model with the additional
constraint that the entries of $x$ are always non-negative, i.e.
$x^{(t)}_{i}\geq 0$, for all $t\in[T]$ and $i\in[d]$.

As mentioned above, we are usually space constrained so that we cannot
explicitely store $x$ and the key idea to overcome this limitation is to store
a linear _sketch_ of $x$, that is storing $y\coloneq f(x)$, where
$f\colon\mathbb{R}^{d}\to\mathbb{R}^{m}$ is a linear function and $m\ll d$,
and then answering queries by applying some function on $y$ rather than $x$.
Note that since $f$ is linear, we can apply it to each update individually and
compute $y$ as the sum of the sketched updates. Furthermore, we can aggregate
results from different streams by adding the different sketches, allowing us
to distribute the computation of the streaming algorithm.

The relevant Johnson–Lindenstrauss lemma in this setting is lemma 1.2 as with
a JLD we get linearity and are able to sample a JLT before seeing any data at
the cost of introducing some failure probability.

Based on JLDs, the most natural streaming problem to tackle is second
frequency moment estimation in the turnstile model, i.e. approximating
$\|x\|_{2}^{2}$, which has found use in database query optimisation
(Alon:2002:TJaSJSiLS, Alo+02, WDJ91, DeW+92) and network data analysis
(Gilbert:2001:QQSaAoND, Gil+01, CG05) among other areas. Simply letting $f$ be
a sample from a JLD and returning $\|f(x)\|_{2}^{2}$ on queries, gives a
factor $(1\pm\varepsilon)$ approximation with failure probability $\delta$
using
$\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta}+\mathopen{\lvert}f\mathclose{\rvert})$
words121212Here we assume that a word is large enough to hold a sufficient
approximation of any real number we use and to hold a number from the stream,
i.e. if $w$ denotes the number of bits in a word then $w=\Omega(\log d+\log
M)$. of space, where $\mathopen{\lvert}f\mathclose{\rvert}$ denotes the words
of space needed to store and apply $f$. However, the approach taken by the
streaming literature is to estimate $\|x\|_{2}^{2}$ with constant error
probability using
$\mathcal{O}(\varepsilon^{-2}+\mathopen{\lvert}f\mathclose{\rvert})$ words of
space, and then sampling $\mathcal{O}(\log\frac{1}{\delta})$ JLTs
$f_{1},\dotsc,f_{\mathcal{O}(\log
1/\delta)}\colon\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{O}(\varepsilon^{-2})}$
and responding to a query with
$\operatorname*{median}_{k}\|f_{k}(x)\|_{2}^{2}$, which reduces the error
probability to $\delta$. This allows for simpler analyses as well more
efficient embeddings (in the case of Count Sketch) compared to using a single
bigger JLT, but it comes at the cost of not embedding into $\ell_{2}$, which
is needed for some applications outside of streaming. With this setup the task
lies in constructing space efficient JLTs and a seminal work here is the AMS
Sketch a.k.a. AGMS Sketch a.k.a. Tug-of-War Sketch (Alon:1999:tSCoAtFM, AMS99,
Alo+02), whose JLTs can be defined as $f_{i}\coloneq m^{-1/2}Ax$, where
$A\in\\{-1,1\\}^{m\times d}$ is a random matrix. The key idea is that each row
$r$ of $A$ can be backed by a hash function $\sigma_{r}\colon[d]\to\\{-1,1\\}$
that need only be 4-wise independent, meaning that for any set of 4 distinct
keys $\\{k_{1},\dotsc k_{4}\\}\subset[d]$ and 4 (not necessarily distinct)
values $v_{1},\dotsc v_{4}\in\\{-1,1\\}$, the probability that the keys hash
to those values is
$\Pr_{\sigma_{r}}[\bigwedge_{i}\sigma_{r}(k_{i})=v_{i}]=\mathopen{\big{missing}}\lvert\\{-1,1\\}\mathclose{\big{missing}}\rvert^{-4}$.
This can for instance131313See e.g. (Thorup:2012:TB5IHwAtLPaSME, TZ12) for
other families of $k$-wise independent hash functions. be attained by
implementing $\sigma_{r}$ as 3rd degree polynomial modulus a sufficiently
large prime with random coefficients (Wegman:1981:NHFaTUiAaSE, WC81), and so
such a JLT need only use $\mathcal{O}(\varepsilon^{-2})$ words of space.
Embedding a scaled standard unit vector with such a JLT takes
$\mathcal{O}(\varepsilon^{-2})$ time leading to an overall update time of the
AMS Sketch of $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$.

A later improvement of the AMS Sketch is the so-called Fast-AGMS Sketch
(Cormode:2005:SSTtNDAQT, CG05) a.k.a. Count Sketch (Charikar:2004:FFIiDS,
CCF04, TZ12), which sparsifies the JLTs such that each column in their matrix
representations only has one non-zero entry. Each JLT can be represented by a
pairwise independent hash function
$h\colon[d]\to[\mathcal{O}(\varepsilon^{-2})]$ to choose the position of each
nonzero entry and a 4-wise independent hash function
$\sigma\colon[d]\to\\{-1,1\\}$ to choose random signs as before. This reduces
the standard unit vector embedding time to $\mathcal{O}(1)$ and so the overall
update time becomes $\mathcal{O}(\log\frac{1}{\delta})$ for Count Sketch. It
should be noted that the JLD inside Count Sketch is also known as Feature
Hashing, which we will return to in section 4.1.

Despite not embedding into $\ell_{2}$, due to the use of the non-linear
median, AMS Sketch and Count Sketch approximately preserve dot products
similarly to corollary 1.5 (Cormode:2005:SSTtNDAQT, CG05, Theorem 2.1 and
Theorem 3.5). This allows us to query for the (approximate) frequency of any
particular item as

$\operatorname*{median}_{k}\mathopen{\langle}f_{k}(x),f_{k}(e_{i})\mathclose{\rangle}=\mathopen{\langle}x,e_{i}\mathclose{\rangle}\pm\varepsilon\|x\|_{2}\|e_{i}\|_{2}=x_{i}\pm\varepsilon\|x\|_{2}$

with probability at least $1-\delta$.

This can be extended to finding frequent items in an insertion only stream
(Charikar:2004:FFIiDS, CCF04). The idea is to use a slightly
larger141414Rather than each JLT having a target dimension of
$\mathcal{O}(\varepsilon^{-2})$, the analysis needs the target dimension to be
$\mathcal{O}\Bigl{(}\frac{\|\operatorname{tail}_{k}(x)\|_{2}^{2}}{(\varepsilon
x_{i_{k}})^{2}}\Bigr{)}$, where $\operatorname{tail}_{k}(x)$ denotes $x$ with
its $k$ largest entries zeroed out. Count Sketch instance to maintain a heap
of the $k$ approximately most frequent items of the stream so far. That is, if
we let $i_{k}$ denote the $k$th most frequent item (i.e. $\bigl{|}\\{j\mid
x_{j}\geq x_{i_{k}}\\}\bigr{|}=k$), then with probability $1-\delta$ we have
$x_{j}>(1-\varepsilon)x_{i_{k}}$ for every item $j$ in our heap.

For more on streaming algorithms, we refer the reader to
(Muthukrishnan:2005:DSAaA, Mut05) and (Nelson:2011:SaSHDV, Nel11), which also
relates streaming to Johnson–Lindenstrauss.

###  4 The Tapestry of Johnson–Lindenstrauss Transforms

> Isti mirant stella
>
> —Scene 32, The Bayeux Tapestry (Bayeux:1070:tBT, Unk70)

As mentioned in section 2, the original JLD from (Johnson:1984:EoLMiaHS, JL84)
is a distribution over functions $f\colon\mathbb{R}^{d}\to\mathbb{R}^{m}$,
where151515We will usually omit the normalisation or scaling factor (the
$(d/m)^{1/2}$ for this JLD) when discussing JLDs as they are textually noisy,
not that interesting, and independent of randomness and input data.
$f(x)=(d/m)^{1/2}Ax$ and $A$ is a random $m\times d$ matrix whose rows form an
orthonormal basis of some $m$-dimensional subspace of $\mathbb{R}^{d}$, i.e.
the rows are unit vectors and pairwise orthogonal. While Johnson:1984:EoLMiaHS
(JL84) showed that $m=\Theta(\varepsilon^{-2}\log|X|)$ suffices to prove lemma
1.1, they did not give any bounds on the constant in the big-$\mathcal{O}$
expression. This was remedied in (Frankl:1988:tJLLatSosG, FM88), which proved
that
$m=\bigl{\lceil}9(\varepsilon^{2}-2\varepsilon^{3}/3)^{-1}\ln|X|\bigr{\rceil}+1$
suffices for the same JLD if $m<\sqrt{|X|}$. This bound was further improved
in (Frankl:1990:SGAotBD, FM90) by removing the $m<\sqrt{|X|}$ restriction and
lowering the bound to
$m=\bigl{\lceil}8(\varepsilon^{2}-2\varepsilon^{3}/3)^{-1}\ln|X|\bigr{\rceil}$.

The next thread of JL research worked on simplifying the JLD constructions as
Indyk:1998:ANNTRtCoD (Har-Peled:2012:ANNTRtCoD, HIM12) showed that sampling
each entry in the matrix i.i.d. from a properly scaled Gaussian distribution
is a JLD. The rows of such a matrix do not form a basis as they are with high
probability not orthogonal; however, the literature still refer to this and
most other JLDs as random projections. Shortly thereafter
Arriaga:2006:aAToLRCaRP (AV06) constructed a JLD by sampling i.i.d. from a
Rademacher161616The Rademacher distribution is the uniform distribution on
$\\{-1,1\\}$. distribution, and Achlioptas:2003:DFRPJLwBC (Ach03) sparsified
the Rademacher construction such that the entries $a_{ij}$ are sampled i.i.d.
with $\Pr[a_{ij}=0]=2/3$ and $\Pr[a_{ij}=-1]=\Pr[a_{ij}=1]=1/6$. We will refer
to such sparse i.i.d. Rademacher constructions as Achlioptas constructions.
The Gaussian and Rademacher results have later been generalised
(Matousek:2008:oVotJLL, Mat08, IN07, KM05) to show that a JLD can be
constructed by sampling each entry in a $m\times d$ matrix i.i.d. from any
distribution with mean 0, variance 1, and a subgaussian tail171717A real
random variable $X$ with mean 0 has a subgaussian tail if there exists
constants $\alpha,\beta>0$ such that for all $\lambda>0$,
$\Pr\bigl{[}|X|>\lambda\bigr{]}\leq\beta e^{-\alpha\lambda^{2}}$.. It should
be noted that these developments have a parallel in the streaming literature
as the previously mentioned AMS Sketch (Alon:1999:tSCoAtFM, AMS99, Alo+02) is
identical to the Rademacher construction (Arriaga:2006:aAToLRCaRP, AV06),
albeit with constant error probability.

As for the target dimension for these constructions, (Har-
Peled:2012:ANNTRtCoD, HIM12) proved that the Gaussian construction is a JLD if
$m\geq
8(\varepsilon^{2}-2\varepsilon^{3}/3)^{-1}\bigl{(}\ln|X|+\mathcal{O}(\log
m)\bigr{)}$, which roughly corresponds to an additional additive
$\mathcal{O}(\varepsilon^{-2}\log\log|X|)$ term over the original
construction. This additive $\log\log$ term was shaved off by the proof in
(Dasgupta:2002:aEPoaToJaL, DG02), which concerns itself with the original JLD
construction but can easily181818The main part of the proof in
(Dasgupta:2002:aEPoaToJaL, DG02) is showing that the $\ell_{2}$ norm of a
vector of i.i.d. Gaussians is concentrated around the expected value. A vector
projected with the Gaussian construction is distributed as a vector of i.i.d.
Gaussians. be adapted to the Gaussian construction, and the proof in
(Arriaga:2006:aAToLRCaRP, AV06), which also give the same $\log\log$ free
bound for the dense Rademacher construction. Achlioptas:2003:DFRPJLwBC (Ach03)
showed that his construction also achieves
$m=\bigl{\lceil}8(\varepsilon^{2}-2\varepsilon^{3}/3)^{-1}\ln|X|\bigr{\rceil}$.
The constant of 8 has been improved for the Gaussian and dense Rademacher
constructions in the sense that Rojo:2010:ItJLL (Rojo:2010:ItJLL, RN10, Ngu09)
have been able to replace the bound with more intricate191919For example, one
of the bounds for the Rademacher construction is
$m\geq\frac{2(d-1)\alpha^{2}}{d\varepsilon^{2}}$, where
$\alpha\coloneq\frac{Q+\sqrt{Q^{2}+5.98}}{2}$,
$Q\coloneq\Phi^{-1}(1-1/|X|^{2})$, and $\Phi^{-1}$ is the quantile function of
the standard Gaussian random variable. expressions, which yield a 10 to 40 %
improvement for many sets of parameters. However, in the distributional
setting it has been shown in (Burr:2018:OBfJLT, BGK18) that $m\geq
4\varepsilon^{-2}\ln\frac{1}{\delta}(1-o(1))$ is necessary for any JLD to
satisfy lemma 1.2, which corresponds to a constant of $8$ if we prove lemma
1.1 the usual way by setting $\delta=n^{-2}$ and union bounding over all pairs
of vectors.

There seems to have been some confusion in the literature regarding the
improvements in target dimension. The main pitfall was that some papers (e.g.
Achlioptas:2003:DFRPJLwBC, Ach03, HIM12, DG02, RN10, BGK18) were only
referring to (Frankl:1988:tJLLatSosG, FM88) when referring to the target
dimension bound of the original construction. As such,
(Achlioptas:2003:DFRPJLwBC, Ach03, HIM12) mistakenly claim to improve the
constant for the target dimension with their constructions. Furthermore,
(Achlioptas:2001:DFRP, Ach01) is sometimes (e.g. in Ailon:2009:tFJLTaANN,
AC09, Mat08, Sch18) the only work credited for the Rademacher construction,
despite it being developed independently and published 2 years prior in
(Arriaga:1999:aAToLRCaRP, AV99).

All the constructions that have been mentioned so far in this section, embed a
vector by performing a relatively dense and unstructured matrix-vector
multiplication, which takes $\Theta(m\|x\|_{0})=\mathcal{O}(md)$
time202020$\|x\|_{0}$ is the number of nonzero entries in the vector $x$. to
compute. This sparked two distinct but intertwined strands of research seeking
to reduce the embedding time, namely the sparsity-based JLDs which dealt with
the density of the embedding matrix and the fast Fourier transform-based which
introduced more structure to the matrix.

####  4.1 Sparse Johnson–Lindenstrauss Transforms

The simple fact underlying the following string of results is that if $A$ has
$s$ nonzero entries per column, then $f(x)=Ax$ can be computed in
$\Theta(s\|x\|_{0})$ time. The first result here is the Achlioptas
construction (Achlioptas:2003:DFRPJLwBC, Ach03) mentioned above, whose column
sparsity $s$ is $m/3$ in expectancy, which leads to an embedding time that is
a third of the full Rademacher construction212121Here we ignore any overhead
that switching to a sparse matrix representation would introduce.. However,
the first superconstant improvement is due to Dasgupta:2010:aSJLT (DKS10), who
based on heuristic approaches (Weinberger:2009:FHfLSML, Wei+09, Shi+09a,
LLS07, GD08) constructed a JLD with
$s=\mathcal{O}(\varepsilon^{-1}\log\frac{1}{\delta}\log^{2}\frac{m}{\delta})$.
Their construction, which we will refer to as the DKS construction, works by
sampling $s$ hash functions
$h_{1},\dotsc,h_{s}\colon[d]\to\\{-1,1\\}\times[m]$ independently, such that
each source entry $x_{i}$ will be hashed to $s$ random signs
$\sigma_{i,1},\dotsc,\sigma_{i,s}$ and $s$ target coordinates
$j_{i,1},\dotsc,j_{i,s}$ (with replacement). The embedding can then be defined
as $f(x)\coloneq\sum_{i}\sum_{k}e_{j_{i,k}}\sigma_{i,k}x_{i}$, which is to say
that every source coordinate is hashed to $s$ output coordinates and randomly
added to or subtracted from those output coordinates. The sparsity analysis
was later tightened to show that
$s=\mathcal{O}(\varepsilon^{-1}\log\frac{1}{\delta}\log\frac{m}{\delta})$
suffices (Kane:2010:aDSJLT, KN10, KN14) and even
$s=\mathcal{O}\Bigl{(}\varepsilon^{-1}\bigl{(}\frac{\log\frac{1}{\delta}\log\log\log\frac{1}{\delta}}{\log\log\frac{1}{\delta}}\bigr{)}^{2}\Bigr{)}$
suffices for the DKS construction assuming
$\varepsilon<\log^{-2}\frac{1}{\delta}$ (Braverman:2010:RCREGatSJLT, BOR10),
while (Kane:2014:SJLT, KN14) showed that
$s=\Omega(\varepsilon^{-1}\log^{2}\frac{1}{\delta}/\log^{2}\frac{1}{\varepsilon})$
is neccessary for the DKS construction.

Kane:2014:SJLT (KN14) present two constructions that circumvent the DKS lower
bound by ensuring that the hash functions do not collide within a column, i.e.
$j_{i,a}\neq j_{i,b}$ for all $i$, $a$, and $b$. The first construction, which
we will refer to as the graph construction, simply samples the $s$ coordinates
without replacement. The second construction, which we will refer to as the
block construction, partitions the output vector into $s$ consecutive blocks
of length $m/s$ and samples one output coordinate per block. Note that the
block construction is the same as Count Sketch from the streaming literature
(Cormode:2005:SSTtNDAQT, CG05, CCF04), though the hash functions differ and
the output is interpreted differently. Kane:2014:SJLT (KN14) prove that
$s=\Theta(\varepsilon^{-1}\log\frac{1}{\delta})$ is both neccessary and
sufficient in order for their two constructions to satisfy lemma 1.2. Note
that while Count Sketch is even sparser than the lower bound for the block
construction, it does not contradict it as Count sketch does not embed into
$\ell_{2}^{m}$ as it computes the median, which is nonlinear. As far as
general sparsity lower bounds go, (Dasgupta:2010:aSJLT, DKS10) shows that an
average column sparsity of
$s_{\mathrm{avg}}=\Omega\bigl{(}\min\\{\varepsilon^{-2},\varepsilon^{-1}\sqrt{\log_{m}d}\\}\bigr{)}$
is neccessary for a sparse JLD, while Nelson:2013:SLBfDRM (NN13a) improves
upon this by showing that there exists a set of points $X\in\mathbb{R}^{d}$
such that any JLT for that set must have column sparsity
$s=\Omega(\varepsilon^{-1}\log|X|/\log\frac{1}{\varepsilon})$ in order to
satisfy lemma 1.1. And so it seems that we have almost reached the limit of
the sparse JL approach, but why should theory be in the way of a good result?
Let us massage the definitions so as to get around these lower bounds.

The hard instances used to prove the lower bounds (Nelson:2013:SLBfDRM, NN13a,
KN14) consist of very sparse vectors, e.g.
$x=(1/\sqrt{2},1/\sqrt{2},0,\dotsc,0)^{\transp}$, but the vectors we are
interested in applying a JLT to might not be so unpleasant, and so by
restricting the input vectors to be sufficiently “nice”, we can get meaningful
result that perform better than what the pessimistic lower bound would
indicate. The formal formulation of this niceness is bounding the
$\ell_{\infty}/\ell_{2}$ ratio of the vectors lemmas 1.1 and 1.2 need apply
to. Let us denote this norm ratio as $\nu\in[1/\sqrt{d},1]$, and revisit some
of the sparse JLDs. The Achlioptas construction (Achlioptas:2003:DFRPJLwBC,
Ach03) can be generalised so that the expected number of nonzero entries per
column is $qm$ rather than $\frac{1}{3}m$ for a parameter $q\in[0,1]$.
Ailon:2009:tFJLTaANN (AC09) show that if
$\nu=\mathcal{O}\bigl{(}\sqrt{\log\frac{1}{\delta}}/\sqrt{d}\bigr{)}$ then
choosing $q=\Theta\bigl{(}\frac{\log^{2}1/\delta}{d}\bigr{)}$ and sampling the
nonzero entries from a Gaussian distribution suffices. This result is
generalised in (Matousek:2008:oVotJLL, Mat08) by proving that for all
$\nu\in[1/\sqrt{d},1]$ choosing
$q=\Theta(\nu^{2}\log\frac{d}{\varepsilon\delta})$ and sampling the nonzero
entries from a Rademacher distribution is a JLD for the vectors constrained by
that $\nu$.

Be aware that sometimes (e.g. in Dasgupta:2010:aSJLT, DKS10, BOR10) this
bound222222Which seems to be the only thing in (Matousek:2008:oVotJLL, Mat08)
related to a bound on $q$. on $q$ is misinterpreted as a lower bound stating
that $qm=\tilde{\Omega}(\varepsilon^{-2})$ is neccessary for the Achlioptas
construction when $\nu=1$. However, Matousek:2008:oVotJLL (Mat08) only loosely
argues that his bound is tight for $\nu\leq d^{-0.1}$, and if it indeed was
tight at $\nu=1$, the factors hidden by the $\tilde{\Omega}$ would lead to the
contradiction that $m\geq
qm=\Omega(\varepsilon^{-2}\log\frac{1}{\delta}\log\frac{d}{\varepsilon\delta})=\omega(m)$.

The heuristic (Weinberger:2009:FHfLSML, Wei+09, Shi+09a, LLS07, GD08) that
(Dasgupta:2010:aSJLT, DKS10) is based on is called Feature Hashing a.k.a. the
hashing trick a.k.a. the hashing kernel and is a sparse JL construction with
exactly 1 nonzero entry per column232323i.e. the DKS, graph, or block
construction with $s=1$.. The block construction can then be viewed as the
concatenation of $s=\Theta(\varepsilon^{-1}\log\frac{1}{\delta})$ feature
hashing instances, and the DKS construction can be viewed as the sum of
$s=\mathcal{O}(\varepsilon^{-1}\log\frac{1}{\delta}\log\frac{m}{\delta})$
Feature Hashing instances or alternatively as first duplicating each entry of
$x\in\mathbb{R}^{d}$ $s$ times before applying Feature Hashing to the enlarged
vector $x^{\prime}\in\mathbb{R}^{sd}$: Let
$f_{\mathsf{dup}}\colon\mathbb{R}^{d}\to\mathbb{R}^{sd}$ be a function that
duplicates each entry in its input $s$ times, i.e.
$f_{\mathsf{dup}}(x)_{(i-1)s+j}=x^{\prime}_{(i-1)s+j}\coloneq x_{i}$ for
$i\in[d],j\in[s]$, then $f_{\mathsf{DKS}}=f_{\mathsf{FH}}\circ
f_{\mathsf{dup}}$.

This duplication is the key to the analysis in (Dasgupta:2010:aSJLT, DKS10) as
$f_{\mathsf{dup}}$ is isometric (up to normalisation) and it ensures that the
$\ell_{\infty}/\ell_{2}$ ratio of $x^{\prime}$ is small, i.e. $\nu\leq
1/\sqrt{s}$ from the point of view of the Feature Hashing data structure
($f_{\mathsf{FH}}$). And so, any lower bound on the sparsity of the DKS
construction (e.g. the one given in (Kane:2014:SJLT, KN14)) gives an upper
bound on the values of $\nu$ for which Feature Hashing is a JLD: If $u$ is a
unit vector such that a DKS instance with sparsity $\hat{s}$ fails to preserve
$u$s norm within $1\pm\varepsilon$ with probability $\delta$, then it must be
the case that Feature Hashing fails to preserve the norm of
$f_{\mathsf{dup}}(u)$ within $1\pm\varepsilon$ with probability $\delta$, and
therefore the $\ell_{\infty}/\ell_{2}$ ratio for which Feature Hashing can
handle all vectors is strictly less than $1/\sqrt{\hat{s}}$.

Written more concisely the statement is
$s_{\mathsf{DKS}}=\Omega(a)\implies\nu_{\mathsf{FH}}=\mathcal{O}(1/\sqrt{a})$
and by contraposition242424Contraposition is $(P\implies Q)\implies(\neg
Q\implies\neg P)$ and it does not quite prove what was just claimed without
some assumptions that $s_{\mathsf{DKS}}$, $\nu_{\mathsf{FH}}$, and $a$ do not
behave too erratically. $\nu_{\mathsf{FH}}=\Omega(1/\sqrt{a})\implies
s_{\mathsf{DKS}}=\mathcal{O}(a)$, where $s_{\mathsf{DKS}}$ is the minimum
column sparsity of a DKS construction that is a JLD, $\nu_{\mathsf{FH}}$ is
the maximum $\ell_{\infty}/\ell_{2}$ constraint for which Feature Hashing is a
JLD, and $a$ is any positive expression. Furthermore, if we prove an upper
bound on $\nu_{\mathsf{FH}}$ using a hard instance that is identical to an
$x^{\prime}$ that the DKS construction can generate after duplication, we can
replace the previous two implications with bi-implications.

(Weinberger:2009:FHfLSML, Wei+09) claims to give a bound on
$\nu_{\mathsf{FH}}$, but it sadly contains an error in its proof of this bound
(Dasgupta:2010:aSJLT, DKS10, Wei+10). Dahlgaard:2017:PHFfSEaDR (DKT17) improve
the $\nu_{\mathsf{FH}}$ lower bound to
$\nu_{\mathsf{FH}}=\Omega\Bigl{(}\sqrt{\frac{\varepsilon\log(1+\frac{4}{\varepsilon})}{\log\frac{1}{\delta}\log\frac{m}{\delta}}}\Bigr{)}$,
and Freksen:2018:FUtHT (FKL18) give an intricate but tight bound for
$\nu_{\mathsf{FH}}$ shown in theorem 1.8, where the hard instance used to
prove the upper bound is identical to an $x^{\prime}$ from the DKS
construction.

######  Theorem 1.8 ((Freksen:2018:FUtHT, FKL18)).

There exist constants $C\geq D>0$ such that for every
$\varepsilon,\delta\in(0,1)$ and $m\in\mathbb{N}_{1}$ the following holds. If
$\frac{C\lg\frac{1}{\delta}}{\varepsilon^{2}}\leq
m<\frac{2}{\varepsilon^{2}\delta}$ then

$\nu_{\mathsf{FH}}(m,\varepsilon,\delta)=\Theta\biggl{(}\sqrt{\varepsilon}\min\Bigl{\\{}\frac{\log\frac{\varepsilon
m}{\log\frac{1}{\delta}}}{\log\frac{1}{\delta}},\sqrt{\frac{\log\frac{\varepsilon^{2}m}{\log\frac{1}{\delta}}}{\log\frac{1}{\delta}}}\Bigr{\\}}\biggr{)}.$

Otherwise, if $m\geq\frac{2}{\varepsilon^{2}\delta}$ then
$\nu_{\mathsf{FH}}(m,\varepsilon,\delta)=1$. Moreover if
$m<\frac{D\lg\frac{1}{\delta}}{\varepsilon^{2}}$ then
$\nu_{\mathsf{FH}}(m,\varepsilon,\delta)=0$.

Furthermore, if an $x\in\\{0,1\\}^{d}$ satisfies
$\nu_{\mathsf{FH}}<\|x\|_{2}^{-1}<1$ then

$\Pr_{f\sim\mathsf{FH}}\Bigl{[}\bigl{|}\|f(x)\|_{2}^{2}-\|x\|_{2}^{2}\bigr{|}>\varepsilon\|x\|_{2}^{2}\Bigr{]}>\delta.$

This bound gives a tight tradeoff between target dimension $m$, distortion
$\varepsilon$, error probability $\delta$, and $\ell_{\infty}/\ell_{2}$
constraint $\nu$ for Feature Hashing, while showing how to construct hard
instances for Feature Hashing: Vectors with the shape
$x=(1,\dotsc,1,0,\dotsc,0)^{\transp}$ are hard instances if they contain few
$1$s, meaning that Feature Hashing cannot preserve their norms within
$1\pm\varepsilon$ with probability $\delta$. Theorem 1.8 is used in corollary
1.9 to provide a tight tradeoff between $m$, $\varepsilon$, $\delta$, $\nu$,
and column sparsity $s$ for the DKS construction.

######  Corollary 1.9.

Let $\nu_{\mathsf{DKS}}\in[1/\sqrt{d},1]$ denote the largest
$\ell_{\infty}/\ell_{2}$ ratio required, $\nu_{\mathsf{FH}}$ denote the
$\ell_{\infty}/\ell_{2}$ constraint for Feature Hashing as defined in theorem
1.8, and $s_{\mathsf{DKS}}\in[m]$ as the minimum column sparsity such that the
DKS construction with that sparsity is a JLD for the subset of vectors
$x\in\mathbb{R}^{d}$ that satisfy
$\|x\|_{\infty}/\|x\|_{2}\leq\nu_{\mathsf{DKS}}$. Then

$s_{\mathsf{DKS}}=\Theta\Bigl{(}\frac{\nu_{\mathsf{DKS}}^{2}}{\nu_{\mathsf{FH}}^{2}}\Bigr{)}.$

The proof of this corollary is deferred to section 6.

Jagadeesan:2019:USJLFfFH (Jag19) generalised the result from
(Freksen:2018:FUtHT, FKL18) to give a lower bound252525Here a lower bound
refers to a lower bound on $\nu$ as a function of $m$, $\varepsilon$,
$\delta$, and $s$. on the $m$, $\varepsilon$, $\delta$, $\nu$, and $s$
tradeoff for any sparse Rademacher construction with a chosen column sparsity,
e.g. the block and graph constructions, and gives a matching upper bound for
the graph construction.

####  4.2 Structured Johnson–Lindenstrauss Transforms

As we move away from the sparse JLDs we will slightly change our idea of what
an efficient JLD is. In the previous section the JLDs were especially fast
when the vectors were sparse, as the running time scaled with
$\mathopen{\lVert}x\mathclose{\rVert}_{0}$, whereas we in this section will
optimise for dense input vectors such that an embedding time of
$\mathcal{O}(d\log d)$ is a satisfying result.

The chronologically first asymptotic improvement over the original JLD
construction is due to Ailon:2009:tFJLTaANN (AC09) who introduced the so-
called Fast Johnson–Lindenstrauss Transform (FJLT). As mentioned in the
previous section, (Ailon:2009:tFJLTaANN, AC09) showed that we can use a very
sparse (and therefore very fast) embedding matrix as long as the vectors have
a low $\ell_{\infty}/\ell_{2}$ ratio, and furthermore that applying a
randomised Walsh–Hadamard transform to a vector results in a low
$\ell_{\infty}/\ell_{2}$ ratio with high probability. And so, the FJLT is
defined as $f(x)\coloneq PHDx$, where $P\in\mathbb{R}^{m\times d}$ is a sparse
Achlioptas matrix with Gaussian entries and
$q=\Theta\bigl{(}\frac{\log^{2}1/\delta}{d}\bigr{)}$, $H\in\\{-1,1\\}^{d\times
d}$ is a Walsh–Hadamard matrix262626One definition of the Walsh–Hadamard
matrices is that the entries are
$H_{ij}=(-1)^{\mathopen{\langle}i-1,j-1\mathclose{\rangle}}$ for all
$i,j\in[d]$, where $\mathopen{\langle}a,b\mathclose{\rangle}$ denote the dot
product of the ($\lg d$)-bit vectors corresponding to the binary
representation of the numbers $a,b\in\\{0,\dotsc,d-1\\}$, and $d$ is a power
of two. To illustrate its recursive nature, a large Walsh–Hadamard matrix can
be described as a Kronecker product of smaller Walsh–Hadamard matrices, i.e.
if $d>2$ and $H^{(n)}$ refers to a $n\times n$ Walsh–Hadamard matrix, then
$H^{(d)}=H^{(2)}\otimes H^{(d/2)}=\begin{pmatrix}H^{(d/2)}&H^{(d/2)}\\\
H^{(d/2)}&-H^{(d/2)}\end{pmatrix}$., and $D\in\\{-1,0,1\\}^{d\times d}$ is a
random diagonal matrix with i.i.d. Rademachers on the diagonal. As the
Walsh–Hadamard transform can be computed using a simple recursive formula, the
expected embedding time becomes $\mathcal{O}(d\log
d+m\log^{2}\frac{1}{\delta})$. And as mentioned, (Matousek:2008:oVotJLL,
Mat08) showed that we can sample from a Rademacher rather than a Gaussian
distribution when constructing the matrix $P$. The embedding time improvement
of FJLT over previous constructions depends on the relationship between $m$
and $d$. If $m=\Theta(\varepsilon^{-2}\log\frac{1}{\delta})$ and
$m=\mathcal{O}(\varepsilon^{-4/3}d^{1/3})$, FJLT’s embedding time becomes
bounded by the Walsh–Hadamard transform at $\mathcal{O}(d\log d)$, but at
$m=\Theta(d^{1/2})$ FJLT is only barely faster than the original construction.

Ailon:2009:FDRuRSoDBCHC (AL09) improved the running time of the FJLT
construction to $\mathcal{O}(d\log m)$ for $m=\mathcal{O}(d^{1/2-\gamma})$ for
any fixed $\gamma>0$. The increased applicable range of $m$ was achieved by
applying multiple randomised Walsh–Hadamard transformations, i.e. replacing
$HD$ with $\prod_{i}HD^{(i)}$, where the $D^{(i)}$s are a constant number of
independent diagonal Rademacher matrices, as well as by replacing $P$ with
$BD$ where $D$ is yet another diagonal matrix with Rademacher entries and $B$
is consecutive blocks of specific partial Walsh–Hadamard matrices (based on
so-called binary dual BCH codes (see e.g. MacWilliams:1977:tToECC, MS77)). The
reduction in running time comes from altering the transform slightly by
partitioning the input into consecutive blocks of length $\text{poly}(m)$ and
applying the randomised Walsh–Hadamard transforms to each of them
independently. We will refer to this variant of FJLT as the BCHJL
construction.

The next pattern of results has roots in compressed sensing and approaches the
problem from another angle: Rather than being fast only when $m\ll d$, they
achieve $\mathcal{O}(d\log d)$ embedding time even when $m$ is close to $d$,
at the cost of $m$ being suboptimal. Before describing these constructions,
let us set the scene by briefly introducing some concepts from compressed
sensing.

Roughly speaking, compressed sensing concerns itself with recovering a sparse
signal via a small number of linear measurements and a key concept here is the
Restricted Isometry Property (Candes:2005:DbLP, CT05, CT06, CRT06, Don06).

######  Definition 1.10 (Restricted Isometry Property).

Let $d,m,k\in\mathbb{N}_{1}$ with $m,k<d$ and $\varepsilon\in(0,1)$. A linear
function $f\colon\mathbb{R}^{d}\to\mathbb{R}^{m}$ is said to have the
Restricted Isometry Property of order $k$ and level $\varepsilon$ (which we
will denote as $(k,\varepsilon)$-RIP) if for all $x\in\mathbb{R}^{d}$ with
$\|x\|_{0}\leq k$,

$\bigl{|}\|f(x)\|_{2}^{2}-\|x\|_{2}^{2}\bigr{|}\leq\varepsilon\|x\|_{2}^{2}.$
(10)

In the compressed sensing literature it has been shown
(Candes:2006:NOSRfRPUES, CT06, RV08) that the subsampled Hadamard transform
(SHT) defined as $f(x)\coloneq SHx$, has the $(k,\varepsilon)$-RIP with high
probability for $m=\Omega\bigl{(}\varepsilon^{-2}k\log^{4}d\bigr{)}$ while
allowing a vector to be embedded in $\mathcal{O}(d\log d)$ time. Here
$H\in\\{-1,1\\}^{d\times d}$ is the Walsh–Hadamard matrix and
$S\in\\{0,1\\}^{m\times d}$ samples $m$ entries of $Hx$ with replacement, i.e.
each row in $S$ has one non-zero entry per row, which is chosen uniformly and
independently, i.e. $S$ is a uniformly random feature selection matrix.
Inspired by this transform and the FJLT mentioned previously,
Ailon:2013:aAOUFJLT (AL13) were able to show that the subsampled randomised
Hadamard transform (SRHT) defined as $f(x)\coloneq SHDx$, is a JLT if
$m=\Theta(\varepsilon^{-4}\log|X|\log^{4}d)$. Once again $D$ denotes a random
diagonal matrix with Rademacher entries, and $S$ and $H$ is as in the SHT.
Some related results include Do:2009:FaEDRuSRM (Do+09) who before
(Ailon:2013:aAOUFJLT, AL13) were able to get a bound of
$m=\Theta(\varepsilon^{-2}\log^{3}|X|)$ in the large set case where $|X|\geq
d$, (Tropp:2011:IAotSRHT, Tro11) which showed how the SRHT construction
approximately preserves the norms of a subspace of vectors, and
(Lei:2020:ISRHTfLSVM, LL20) which modified the sampling matrix $S$ to improve
precision when used as a preprocessor for support vector machines (SVMs) by
sacrificing input data independence.

This target dimension bound of (Ailon:2013:aAOUFJLT, AL13) was later tightened
by Krahmer:2011:NaIJLEvtRIP (KW11), who showed that
$m=\Theta(\varepsilon^{-2}\log|X|\log^{4}d)$ suffices for the SRHT. This was a
corollary of a more general result, namely that if
$\sigma\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ applies random signs
equivalently to the $D$ matrices mentioned previously and
$f\colon\mathbb{R}^{d}\to\mathbb{R}^{m}$ has the
$\bigl{(}\Omega(\log|X|),\varepsilon/4\bigr{)}$-RIP then $f\circ\sigma$ is a
JLT with high probability. An earlier result by Baraniuk:2008:aSPotRIPfRM
(Bar+08) showed that a transform sampled from a JLD has the
$\bigl{(}\mathcal{O}(\varepsilon^{2}m/\log d),\varepsilon\bigr{)}$-RIP with
high probability. And so, as one might have expected from their appearance,
the Johnson–Lindenstrauss Lemma and the Restricted Isometry Property are
indeed cut from the same cloth.

Another transform from the compressed sensing literature uses so-called
Toeplitz or partial circulant matrices (Bajwa:2007:TSCSM, Baj+07, Rau09,
Rom09, Hau+10, RRT12, Baj12, DJR19), which can be defined in the following
way. For $m,d\in\mathbb{N}_{1}$ we say that $T\in\mathbb{R}^{m\times d}$ is a
real Toeplitz matrix if there exists
$t_{-(m-1)},t_{-(m-2)}\dotsc,t_{d-1}\in\mathbb{R}$ such that $T_{ij}=t_{j-i}$.
This has the effect that the entries on any one diagonal are the same (see
fig. 1) and computing the matrix-vector product corresponds to computing the
convolution with a vector of the $t$s. Partial circulant matrices are special
cases of Toeplitz matrices where the diagonals “wrap around” the ends of the
matrix, i.e. $t_{-i}=t_{d-i}$ for all $i\in[m-1]$.

$\begin{pmatrix}t_{0}&t_{1}&t_{2}&\cdots&t_{d-1}\\\
t_{-1}&t_{0}&t_{1}&\cdots&t_{d-2}\\\ t_{-2}&t_{-1}&t_{0}&\cdots&t_{d-3}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
t_{-(m-1)}&t_{-(m-2)}&t_{-(m-3)}&\cdots&t_{d-m}\end{pmatrix}$ Figure 1: The
structure of a Toeplitz matrix.

As a JLT, the Toeplitz construction is $f(x)\coloneq TDx$, where
$T\in\\{-1,1\\}^{m\times d}$ is a Toeplitz matrix with i.i.d. Rademacher
entries and $D\in\\{-1,0,1\\}^{d\times d}$ is a diagonal matrix with
Rademacher entries as usual. Note that the convolution of two vectors
corresponds to the entrywise product in Fourier space, and we can therefore
employ fast Fourier transform (FFT) to embed a vector with the Toeplitz
construction in time $\mathcal{O}(d\log d)$. This time can even be reduced to
$\mathcal{O}(d\log m)$ as we realise that by partitioning $T$ into
$\frac{d}{m}$ consecutive blocks of size $m\times m$, each block is also a
Toeplitz matrix, and by applying each individually the embedding time becomes
$\mathcal{O}(\frac{d}{m}m\log m)$.

Combining the result from (Krahmer:2011:NaIJLEvtRIP, KW11) with RIP bounds for
Toeplitz matrices (Rauhut:2012:RIfPRCM, RRT12) gives that
$m=\Theta\bigl{(}\varepsilon^{-1}\log^{3/2}|X|\log^{3/2}d+\varepsilon^{-2}\log|X|\log^{4}d\bigr{)}$
is sufficient for the Toeplitz construction to be a JLT with high probability.
However, the Toeplitz construction has also been studied directly as a JLD
without going via its RIP bounds. Hinrichs:2011:JLLfCM (HV11) showed that
$m=\Theta(\varepsilon^{-2}\log^{3}\frac{1}{\delta})$ is sufficient for the
Toeplitz construction, and this bound was improved shortly thereafter in
(Vybiral:2011:aVotJLLfCM, Vyb11) to
$m=\Theta(\varepsilon^{-2}\log^{2}\frac{1}{\delta})$. The question then is if
we can tighten the analysis to shave off the last $\log$ factor and get the
elusive result of a JLD with optimal target dimension and $\mathcal{O}(d\log
d)$ embedding time even when $m$ is close to $d$. Sadly, this is not the case
as Freksen:2020:oUTaCMfJLT (FL20) showed that there exists
vectors272727Curiously, the hard instances for the Toeplitz construction are
very similar to the hard instances for Feature Hashing used in
(Freksen:2018:FUtHT, FKL18). that necessitates
$m=\Omega(\varepsilon^{-2}\log^{2}\frac{1}{\delta})$ for the Toeplitz
construction.

Just as JLTs are used as preprocessors to speed up algorithms that solve the
problems we actually care about, we can also use a JLT to speed up other JLTs
in what one could refer to as compound JLTs. More explicitely if
$f_{1}\colon\mathbb{R}^{d}\to\mathbb{R}^{d^{\prime}}$ and
$f_{2}\colon\mathbb{R}^{d^{\prime}}\to\mathbb{R}^{m}$ with $m\ll d^{\prime}\ll
d$ are two JLTs and computing $f_{1}(x)$ is fast, we could hope that computing
$(f_{2}\circ f_{1})(x)$ is fast as well as $f_{2}$ only need to handle
$d^{\prime}$ dimensional vectors and hope that $(f_{2}\circ f_{1})$ preserves
the norm sufficiently well since both $f_{1}$ and $f_{2}$ approximately
preserve norms individually. As presented here, the obvious candidate for
$f_{1}$ is one of the RIP-based JLDs, which was succesfully applied in
(Bamberger:2017:OFJLEfLDS, BK17). In their construction, which we will refer
to as GRHD282828Due to the choice of matrix names in
(Bamberger:2017:OFJLEfLDS, BK17)., $f_{1}$ is the SRHT and $f_{2}$ is the
dense Rademacher construction (i.e. $f(x)\coloneq A_{\mathsf{Rad}}SHDx$), and
it can embed a vector in time $\mathcal{O}(d\log m)$ for
$m=\mathcal{O}(d^{1/2-\gamma})$ for any fixed $\gamma>0$. This is a similar
result to the construction of Ailon:2009:FDRuRSoDBCHC (AL09), but unlike that
construction, GRHD handles the remaining range of $m$ more gracefully as for
any $r\in[1/2,1]$ and $m=\mathcal{O}(d^{r})$, the embedding time for GRHD
becomes $\mathcal{O}(d^{2r}\log^{4}d)$. However the main selling point of the
GRHD construction is that it allows the simultaneous embedding of sufficiently
large sets of points $X$ to be computed in total time $\mathcal{O}(|X|d\log
m)$, even when $m=\Theta(d^{1-\gamma})$ for any fixed $\gamma>0$, by utilising
fast matrix-matrix multiplication techniques (Lotti:1983:otACoRMM, LR83).

Another compound JLD is based on the so-called lean Walsh transforms (LWT)
(Liberty:2011:DFRPaLWT, LAS11), which are defined based on so-called seed
matrices. For $r,c\in\mathbb{N}_{1}$ we say that $A_{1}\in\mathbb{C}^{r\times
c}$ is a seed matrix if $r<c$, its columns are of unit length, and its rows
are pairwise orthogonal and have the same $\ell_{2}$ norm. As such, partial
Walsh–Hadamard matrices and partial Fourier matrices are seed matrices (up to
normalisation); however, for simplicity’s sake we will keep it real by
focusing on partial Walsh–Hadamard matrices. We can then define a LWT of order
$l\in\mathbb{N}_{1}$ based on this seed as $A_{l}\coloneq A_{1}^{\otimes
l}=A_{1}\otimes\dotsb\otimes A_{1}$, where $\otimes$ denotes the Kronecker
product, which we will quickly define. Let $A$ be a $m\times n$ matrix and $B$
be a $p\times q$ matrix, then the Kronecker product $A\otimes B$ is the
$mp\times nq$ block matrix defined as

$A\otimes B\coloneq\begin{pmatrix}A_{11}B&\cdots&A_{1n}B\\\
\vdots&\ddots&\vdots\\\ A_{m1}B&\cdots&A_{mn}B\end{pmatrix}.$

Note that $A_{l}$ is a $r^{l}\times c^{l}$ matrix and that any Walsh–Hadamard
matrix can be written as $A_{l}$ for some $l$ and the $2\times 2$
Walsh–Hadamard matrix292929Here we ignore the $r<c$ requirement of seed
matrices. as $A_{1}$. Furthermore, for a constant sized seed the time
complexity of applying $A_{l}$ to a vector is $O(c^{l})$ by using an algorithm
similar to FFT. We can then define the compound transform which we will refer
to as LWTJL, as $f(x)\coloneq GA_{l}Dx$, where $D\in\\{-1,1\\}^{d\times d}$ is
a diagonal matrix with Rademacher entries, $A_{l}\in\mathbb{R}^{r^{l}\times
d}$ is a LWT, and $G\in\mathbb{R}^{m\times r^{l}}$ is a JLT, and $r$ and $c$
are constants. One way to view LWTJL is as a variant of GRHD where the
subsampling occurs on the seed matrix rather than the final Walsh–Hadamard
matrix. If $G$ can be applied in $\mathcal{O}(r^{l}\log r^{l})$ time, e.g. if
$G$ is the BCHJL construction (Ailon:2009:FDRuRSoDBCHC, AL09) and
$m=\mathcal{O}(r^{l(1/2-\gamma)})$, the total embedding time becomes
$\mathcal{O}(d)$, as $r^{l}=d^{\alpha}$ for some $\alpha<1$. However, in order
to prove that LWTJL satisfies lemma 1.2 the analysis of
(Liberty:2011:DFRPaLWT, LAS11) imposes a few requirements on $r$, $c$, and the
vectors we wish to embed, namely that $\log r/\log c\geq 1-2\delta$ and
$\nu=\mathcal{O}(m^{-1/2}d^{-\delta})$, where $\nu$ is an upper bound on the
$\ell_{\infty}/\ell_{2}$ ratio as introduced at the end of section 4.1. The
bound on $\nu$ is somewhat tight as shown in proposition 1.11.

######  Proposition 1.11.

For any seed matrix define $\mathsf{LWT}$ as the LWTJL distribution seeded
with that matrix. Then for all $\delta\in(0,1)$, there exists a vector
$x\in\mathbb{C}^{d}$ (or $x\in\mathbb{R}^{d}$, if the seed matrix is a real
matrix) satisfying
$\|x\|_{\infty}/\|x\|_{2}=\Theta(\log^{-1/2}\frac{1}{\delta})$ such that

$\Pr_{f\sim\mathsf{LWT}}[f(x)=\mathbf{0}]>\delta.$ (11)

The proof of proposition 1.11 can be found in section 7, and it is based on
constructing $x$ as a few copies of a vector that is orthogonal to the rows of
the seed matrix.

The last JLD we will cover is based on so-called Kac random walks, and despite
Ailon:2009:tFJLTaANN (AC09) conjecturing that such a construction could
satisfy lemma 1.1, it was not until Jain:2020:KMJaLaMOFJLT (Jai+20) that a
proof was finally at hand. As with the lean Walsh transforms above, let us
first define Kac random walks before describing how they can be used to
construct JLDs. A Kac random walk is a Markov chain of linear transformations,
where for each step we choose two coordinates at random and perform a random
rotation on the plane spanned by these two coordinates, or more formally:

######  Definition 1.12 (Kac random walk (Kac:1956:FoKT, Kac56)).

For a given dimention $d\in\mathbb{N}_{1}$, let $K^{(0)}\coloneq
I\in\\{0,1\\}^{d\times d}$ be the identity matrix, and for each $t>0$ sample
$(i_{t},j_{t})\in\binom{[d]}{2}$ and $\theta_{t}\in[0,2\pi)$ independently and
uniformly at random. Then define the Kac random walk of length $t$ as
$K^{(t)}\coloneq R^{(i_{t},j_{t},\theta_{t})}K^{(t-1)}$, where
$R^{(i,j,\theta)}\in\mathbb{R}^{d\times d}$ is the rotation in the $(i,j)$
plane by $\theta$ and is given by

$\displaystyle R^{(i,j,\theta)}e_{k}$ $\displaystyle\coloneq e_{k}$
$\displaystyle\forall k\notin\\{i,j\\},$ $\displaystyle
R^{(i,j,\theta)}(ae_{i}+be_{j})$
$\displaystyle\coloneq(a\cos\theta-b\sin\theta)e_{i}+(a\sin\theta+b\cos\theta)e_{j}$
.

The main JLD introduced in (Jain:2020:KMJaLaMOFJLT, Jai+20), which we will
refer to as KacJL, is a compound JLD where both $f_{1}$ and $f_{2}$ consists
of a Kac random walk followed by subsampling, which can be defined more
formally in the following way. Let $T_{1}\coloneq\Theta(d\log d)$ be the
length of the first Kac random walk,
$d^{\prime}\coloneq\min\\{d,\Theta(\varepsilon^{-2}\log|X|\log^{2}\log|X|\log^{3}d)\\}$
be the intermediate dimension, $T_{2}\coloneq\Theta(d^{\prime}\log|X|)$ be the
length of the second Kac random walk, and
$m\coloneq\Theta(\varepsilon^{-2}\log|X|)$ be the target dimension, and then
define the JLT as $f(x)=(f_{2}\circ f_{1})(x)\coloneq
S^{(m,d^{\prime})}K^{(T_{2})}S^{(d^{\prime},d)}K^{(T_{1})}x$, where
$K^{(T_{1})}\in\mathbb{R}^{d\times d}$ and
$K^{(T_{2})}\in\mathbb{R}^{d^{\prime}\times d^{\prime}}$ are independent Kac
random walks of length $T_{1}$ and $T_{2}$, respectively, and
$S^{(d^{\prime},d)}\in\\{0,1\\}^{d^{\prime}\times d}$ and
$S^{(m,d^{\prime})}\in\\{0,1\\}^{m\times d^{\prime}}$ projects onto the first
$d^{\prime}$ and $m$ coordinates303030The paper lets $d^{\prime}$ and $m$ be
random variables, but with the way the JLD is presented here a deterministic
projection suffices, though it may affect constants hiding in the
big-$\mathcal{O}$ expressions., respectively. Since $K^{(T)}$ can be applied
in time $\mathcal{O}(T)$, the KacJL construction is JLD with embedding time
$\mathcal{O}(d\log
d+\min\\{d\log|X|,\varepsilon^{-2}\log^{2}|X|\log^{2}\log|X|\log^{3}d\\})$
with asymptotically optimal target dimension, and by only applying the first
part ($f_{1}$), KacJL achieves an embedding time of $\mathcal{O}(d\log d)$ but
with a suboptimal target dimension of
$\mathcal{O}(\varepsilon^{-2}\log|X|\log^{2}\log|X|\log^{3}d)$.

Jain:2020:KMJaLaMOFJLT (Jai+20) also proposes a version of their JLD
construction that avoids computing trigonometric functions313131Recall that
$\sin(\pi/4)=2^{-1/2}$ and that similar results holds for cosine and for the
other angles. by choosing the angles $\theta_{t}$ uniformly at random from the
set $\\{\pi/4,3\pi/4,5\pi/4,7\pi/4\\}$ or even the singleton set
$\\{\pi/4\\}$. This comes at the cost323232Note that the various Kac walk
lengths are only shown to be sufficient, and so tighter analysis might shorten
them and perhaps remove the cost of using simpler angles. of increasing
$T_{1}$ by a factor of $\log\log d$ and $T_{2}$ by a factor of $\log d$, and
for the singleton case multiplying with random signs (as we have done with the
$D$ matrices in many of the previous constructions) and projecting down onto a
random subset of coordinates rather than the $d^{\prime}$ or $m$ first.

9

This concludes the overview of Johnson–Lindenstrauss distributions and
transforms, though there are many aspects we did not cover such as space
usage, preprocessing time, randomness usage, and norms other than $\ell_{2}$.
However, a summary of the main aspects we did cover (embedding times and
target dimensions of the JLDs) can be found in table 1.

Name | Embedding time | Target dimension | Ref. | Constraints
---|---|---|---|---
Original | $\mathcal{O}(\|x\|_{0}m)$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Johnson:1984:EoLMiaHS, JL84) |
Gaussian | $\mathcal{O}(\|x\|_{0}m)$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Har-Peled:2012:ANNTRtCoD, HIM12) |
Rademacher | $\mathcal{O}(\|x\|_{0}m)$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Arriaga:2006:aAToLRCaRP, AV06) |
Achlioptas | $\mathcal{O}(\frac{1}{3}\|x\|_{0}m)$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Achlioptas:2003:DFRPJLwBC, Ach03) |
DKS | $\mathcal{O}(\|x\|_{0}\varepsilon^{-1}\log\frac{m}{\delta}\log\frac{1}{\delta})$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Dasgupta:2010:aSJLT, DKS10, KN14) |
Block JL | $\mathcal{O}(\|x\|_{0}\varepsilon^{-1}\log\frac{1}{\delta})$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Kane:2014:SJLT, KN14) |
Feature Hashing | $\mathcal{O}(\|x\|_{0})$ | $\mathcal{O}(\varepsilon^{-2}\delta^{-1})$ | (Weinberger:2009:FHfLSML, Wei+09, FKL18) |
Feature Hashing | $\mathcal{O}(\|x\|_{0})$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Freksen:2018:FUtHT, FKL18) | $\nu\ll 1$
FJLT | $\mathcal{O}(d\log d+m\log^{2}\frac{1}{\delta})$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Ailon:2009:tFJLTaANN, AC09) |
BCHJL | $\mathcal{O}(d\log m)$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Ailon:2009:FDRuRSoDBCHC, AL09) | $m=o(d^{1/2})$
SRHT | $\mathcal{O}(d\log d)$ | $\mathcal{O}(\varepsilon^{-2}\log|X|\log^{4}d)$ | (Ailon:2013:aAOUFJLT, AL13, KW11) |
SRHT | $\mathcal{O}(d\log d)$ | $\mathcal{O}(\varepsilon^{-2}\log^{3}|X|)$ | (Do:2009:FaEDRuSRM, Do+09) | $|X|\geq d$
Toeplitz | $\mathcal{O}(d\log m)$ |  $\mathcal{O}\Bigl{(}$ $\varepsilon^{-1}\log^{3/2}|X|\log^{3/2}d\allowbreak+\varepsilon^{-2}\log|X|\log^{4}d$ $\Bigr{)}$ | (Krahmer:2011:NaIJLEvtRIP, KW11) |
Toeplitz | $\mathcal{O}(d\log m)$ | $\mathcal{O}(\varepsilon^{-2}\log^{2}\frac{1}{\delta})$ | (Hinrichs:2011:JLLfCM, HV11, Vyb11) |
Toeplitz | $\mathcal{O}(d\log m)$ | $\Omega(\varepsilon^{-2}\log^{2}\frac{1}{\delta})$ | (Freksen:2020:oUTaCMfJLT, FL20) |
GRHD | $\mathcal{O}(d\log m)$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Bamberger:2017:OFJLEfLDS, BK17) | $m=o(d^{1/2})$
GRHD | $\mathcal{O}(d^{2r}\log^{4}d)$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Bamberger:2017:OFJLEfLDS, BK17) | $m=O(d^{r})$
LWTJL | $\mathcal{O}(d)$ | $\mathcal{O}(\varepsilon^{-2}\log\frac{1}{\delta})$ | (Liberty:2011:DFRPaLWT, LAS11) | $\nu=\mathcal{O}(m^{-1/2}d^{-\delta})$
KacJL |  $\mathcal{O}\biggl{(}$ $d\log d\\\ +\min\Bigl{\\{}$ $d\log|X|,\\\ \varepsilon^{-2}\log^{2}|X|\log^{2}\log|X|\log^{3}d$ $\Bigr{\\}}$ $\biggr{)}$ | $\mathcal{O}(\varepsilon^{-2}\log|X|)$ | (Jain:2020:KMJaLaMOFJLT, Jai+20) |
KacJL | $\mathcal{O}(d\log d)$ | $\mathcal{O}(\varepsilon^{-2}\log|X|\log^{2}\log|X|\log^{3}d)$ | (Jain:2020:KMJaLaMOFJLT, Jai+20) |

Table 1: The tapestry tabularised.

##  Chapter 2 Deferred Proofs

###  5 $k$-Means Cost is Pairwise Distances

Let us first repeat the lemma to remind ourselves what we need to show.

######  Lemma 10.

Let $k,d\in\mathbb{N}_{1}$ and $X_{i}\subset\mathbb{R}^{d}$ for
$i\in\\{1,\dotsc,k\\}$, then

$\sum_{i=1}^{k}\sum_{x\in X_{i}}\Big{\|}x-\frac{1}{|X_{i}|}\sum_{y\in
X_{i}}y\Big{\|}_{2}^{2}=\frac{1}{2}\sum_{i=1}^{k}\frac{1}{|X_{i}|}\sum_{x,y\in
X_{i}}\|x-y\|_{2}^{2}.$

In order to prove footnote 10 we will need the following lemma.

######  Lemma 2.1.

Let $d\in\mathbb{N}_{1}$ and $X\subset\mathbb{R}^{d}$ and define
$\mu\coloneq\frac{1}{|X|}\sum_{x\in X}x$ as the mean of $X$, then it holds
that

$\sum_{x,y\in X}\mathopen{\langle}x-\mu,y-\mu\mathclose{\rangle}=0.$

###### Proof of lemma 2.1.

The lemma follows from the definition of $\mu$ and the linearity of the real
inner product.

$\displaystyle\sum_{x,y\in X}\mathopen{\langle}x-\mu,y-\mu\mathclose{\rangle}$
$\displaystyle=\sum_{x,y\in
X}\big{(}\mathopen{\langle}x,y\mathclose{\rangle}-\mathopen{\langle}x,\mu\mathclose{\rangle}-\mathopen{\langle}y,\mu\mathclose{\rangle}+\mathopen{\langle}\mu,\mu\mathclose{\rangle}\big{)}$
$\displaystyle=\sum_{x,y\in
X}\mathopen{\langle}x,y\mathclose{\rangle}-\sum_{x\in
X}2|X|\mathopen{\langle}x,\mu\mathclose{\rangle}+|X|^{2}\mathopen{\langle}\mu,\mu\mathclose{\rangle}$
$\displaystyle=\sum_{x,y\in
X}\mathopen{\langle}x,y\mathclose{\rangle}-2\sum_{x\in
X}\mathopen{\big{missing}}\langle x,\sum_{y\in
X}y\mathclose{\big{missing}}\rangle+\mathopen{\big{missing}}\langle\sum_{x\in
X}x,\sum_{y\in X}y\mathclose{\big{missing}}\rangle$
$\displaystyle=\sum_{x,y\in
X}\mathopen{\langle}x,y\mathclose{\rangle}-2\sum_{x,y\in
X}\mathopen{\langle}x,y\mathclose{\rangle}+\sum_{x,y\in
X}\mathopen{\langle}x,y\mathclose{\rangle}$ $\displaystyle=0.$

∎

###### Proof of footnote 10.

We will first prove an identity for each partition, so let $X_{i}\subseteq
X\subset\mathbb{R}^{d}$ be any partition of the dataset $X$ and define
$\mu_{i}\coloneq\frac{1}{|X_{i}|}\sum_{x\in X_{i}}x$ as the mean of $X_{i}$.

$\displaystyle\frac{1}{2|X_{i}|}\sum_{x,y\in X_{i}}\|x-y\|_{2}^{2}$
$\displaystyle=\frac{1}{2|X_{i}|}\sum_{x,y\in
X_{i}}\|(x-\mu_{i})-(y-\mu_{i})\|_{2}^{2}$
$\displaystyle=\frac{1}{2|X_{i}|}\sum_{x,y\in
X_{i}}\big{(}\|x-\mu_{i}\|_{2}^{2}+\|y-\mu_{i}\|_{2}^{2}-2\mathopen{\langle}x-\mu_{i},y-\mu_{i}\mathclose{\rangle}\big{)}$
$\displaystyle=\sum_{x\in
X_{i}}\|x-\mu_{i}\|_{2}^{2}-\frac{1}{2|X_{i}|}\sum_{x,y\in
X_{i}}2\mathopen{\langle}x-\mu_{i},y-\mu_{i}\mathclose{\rangle}$
$\displaystyle=\sum_{x\in X_{i}}\|x-\mu_{i}\|_{2}^{2},$

where the last equality holds by lemma 2.1. We now substitute each term in the
sum in footnote 10 using the just derived identity:

$\sum_{i=1}^{k}\sum_{x\in X_{i}}\Big{\|}x-\frac{1}{|X_{i}|}\sum_{y\in
X_{i}}y\Big{\|}_{2}^{2}=\frac{1}{2}\sum_{i=1}^{k}\frac{1}{|X_{i}|}\sum_{x,y\in
X_{i}}\|x-y\|_{2}^{2}.$

∎

###  6 Super Sparse DKS

The tight bounds on the performance of feature hashing presented in theorem
1.8 can be extended to tight performance bounds for the DKS construction.
Recall that the DKS construction, parameterised by a so-called column sparsity
$s\in\mathbb{N}_{1}$, works by first mapping a vector $x\in\mathbb{R}^{d}$ to
an $x^{\prime}\in\mathbb{R}^{sd}$ by duplicating each entry in $x$ $s$ times
and then scaling with $1/\sqrt{s}$, before applying feature hashing to
$x^{\prime}$, as $x^{\prime}$ has a more palatable $\ell_{\infty}/\ell_{2}$
ratio compared to $x$. The setting for the extended result is that if we wish
to use the DKS construction but we only need to handle vectors with a small
$\|x\|_{\infty}/\|x\|_{2}$ ratio, we can choose a column sparsity smaller than
the usual $\Theta(\varepsilon^{-1}\log\frac{1}{\delta}\log\frac{m}{\delta})$
and still get the Johnson–Lindenstrauss guarantees. This is formalised in
corollary 1.9. The two pillars of theorem 1.8 we use in the proof of corollary
1.9 is that the feature hashing tradeoff is tight and that we can force the
DKS construction to create hard instances for feature hashing.

######  Corollary 1.9.

Let $\nu_{\mathsf{DKS}}\in[1/\sqrt{d},1]$ denote the largest
$\ell_{\infty}/\ell_{2}$ ratio required, $\nu_{\mathsf{FH}}$ denote the
$\ell_{\infty}/\ell_{2}$ constraint for feature hashing as defined in theorem
1.8, and $s_{\mathsf{DKS}}\in[m]$ as the minimum column sparsity such that the
DKS construction with that sparsity is a JLD for the subset of vectors
$x\in\mathbb{R}^{d}$ that satisfy
$\|x\|_{\infty}/\|x\|_{2}\leq\nu_{\mathsf{DKS}}$. Then

$s_{\mathsf{DKS}}=\Theta\Bigl{(}\frac{\nu_{\mathsf{DKS}}^{2}}{\nu_{\mathsf{FH}}^{2}}\Bigr{)}.$
(12)

The upper bound part of the $\Theta$ in corollary 1.9 shows how sparse we can
choose the DKS construction to be and still get Johnson–Lindenstrauss
guarantees for the data we care about, while the lower bound shows that if we
choose a sparsity below this bound, there exists vectors who get distorted too
much too often despite having an $\ell_{\infty}/\ell_{2}$ ratio of at most
$\nu_{\mathsf{DKS}}$.

###### Proof of corollary 1.9.

Let us first prove the upper bound:
$s_{\mathsf{DKS}}=\mathcal{O}\bigl{(}\frac{\nu_{\mathsf{DKS}}^{2}}{\nu_{\mathsf{FH}}^{2}}\bigr{)}$.

Let
$s\coloneq\Theta\bigl{(}\frac{\nu_{\mathsf{DKS}}^{2}}{\nu_{\mathsf{FH}}^{2}}\bigr{)}\in[m]$
be the column sparsity, and let $x\in\mathbb{R}^{d}$ be a unit vector with
$\|x\|_{\infty}\leq\nu_{\mathsf{DKS}}$. The goal is now to show that a DKS
construction with sparsity $s$ can embed $x$ while preserving its norm within
$1\pm\varepsilon$ with probability at least $1-\delta$ (as defined in lemma
1.2). Let $x^{\prime}\in\mathbb{R}^{sd}$ be the unit vector constructed by
duplicating each entry in $x$ $s$ times and scaling with $1/\sqrt{s}$ as in
the DKS construction. We now have

$\|x^{\prime}\|_{\infty}\leq\frac{\nu_{\mathsf{DKS}}}{\sqrt{s}}=\Theta(\nu_{\mathsf{FH}}).$
(13)

Let $\mathsf{DKS}$ denote the JLD from the DKS construction with column
sparsity $s$, and let $\mathsf{FH}$ denote the feature hashing JLD. Then we
can conclude

$\displaystyle\Pr_{f\sim\mathsf{DKS}}\Bigl{[}\bigl{|}\|f(x)\|_{2}^{2}-1\bigr{|}\leq\varepsilon\Bigr{]}$
$\displaystyle=\Pr_{g\sim\mathsf{FH}}\Bigl{[}\bigl{|}\|g(x^{\prime})\|_{2}^{2}-1\bigr{|}\leq\varepsilon\Bigr{]}\geq
1-\delta,$

where the inequality is implied by eqs. 13 and 1.8.

Now let us prove the lower bound:
$s_{\mathsf{DKS}}=\Omega\bigl{(}\frac{\nu_{\mathsf{DKS}}^{2}}{\nu_{\mathsf{FH}}^{2}}\bigr{)}$.

Let $s\coloneq
o\bigl{(}\frac{\nu_{\mathsf{DKS}}^{2}}{\nu_{\mathsf{FH}}^{2}}\bigr{)}$, and
let
$x=(\nu_{\mathsf{DKS}},\dotsc,\nu_{\mathsf{DKS}},0,\dotsc,0)^{\transp}\in\mathbb{R}^{d}$
be a unit vector. We now wish to show that a DKS construction with sparsity
$s$ will preserve the norm of $x$ to within $1\pm\varepsilon$ with probability
strictly less than $1-\delta$. As before, define
$x^{\prime}\in\mathbb{R}^{sd}$ as the unit vector the DKS construction
computes when duplicating every entry in $x$ $s$ times and scaling with
$1/\sqrt{s}$. This gives

$\|x^{\prime}\|_{\infty}=\frac{\nu_{\mathsf{DKS}}}{\sqrt{s}}=\omega(\nu_{\mathsf{FH}}).$
(14)

Finally, let $\mathsf{DKS}$ denote the JLD from the DKS construction with
column sparsity $s$, and let $\mathsf{FH}$ denote the feature hashing JLD.
Then we can conclude

$\displaystyle\Pr_{f\sim\mathsf{DKS}}\Bigl{[}\bigl{|}\|f(x)\|_{2}^{2}-1\bigr{|}\leq\varepsilon\Bigr{]}$
$\displaystyle=\Pr_{g\sim\mathsf{FH}}\Bigl{[}\bigl{|}\|g(x^{\prime})\|_{2}^{2}-1\bigr{|}\leq\varepsilon\Bigr{]}<1-\delta,$

where the inequality is implied by eqs. 14 and 1.8, and the fact that
$x^{\prime}$ has the shape of an asymptotically worst case instance for
feature hashing. ∎

###  7 LWTJL Fails for Too Sparse Vectors

######  Proposition 1.11.

For any seed matrix define $\mathsf{LWT}$ as the LWTJL distribution seeded
with that matrix. Then for all $\delta\in(0,1)$, there exists a vector
$x\in\mathbb{C}^{d}$ (or $x\in\mathbb{R}^{d}$, if the seed matrix is a real
matrix) satisfying
$\|x\|_{\infty}/\|x\|_{2}=\Theta(\log^{-1/2}\frac{1}{\delta})$ such that

$\Pr_{f\sim\mathsf{LWT}}[f(x)=\mathbf{0}]>\delta.$

###### Proof.

The main idea is to construct the vector $x$ out of segments that are
orthogonal to the seed matrix with some probability, and then show that $x$ is
orthogonal to all copies of the seed matrix simultaneously with probability
larger than $\delta$.

Let $r,c\in\mathbb{N}_{1}$ be constants and $A_{1}\in\mathbb{C}^{r\times c}$
be a seed matrix. Let $d$ be the source dimension of the LWTJL construction,
$D\in\\{-1,0,1\\}^{d\times d}$ be the random diagonal matrix with i.i.d.
Rademachers, $l\in\mathbb{N}_{1}$ such that $c^{l}=d$, and
$A_{l}\in\mathbb{C}^{r^{l}\times c^{l}}$ be the the LWT, i.e. $A_{l}\coloneq
A_{1}^{\otimes l}$. Since $r<c$ there exists a nontrivial vector
$z\in\mathbb{C}^{c}\setminus\\{\mathbf{0}\\}$ that is orthogonal to all $r$
rows of $A_{1}$ and $\|z\|_{\infty}=\Theta(1)$. Now define
$x\in\mathbb{C}^{d}$ as $k\in\mathbb{N}_{1}$ copies of $z$ followed by a
padding of $0$s, where $k=\lfloor\frac{1}{c}\lg\frac{1}{\delta}-1\rfloor$.
Note that if the seed matrix is real, we can choose $z$ and therefore $x$ to
be real as well.

The first thing to note is that

$\|x\|_{0}\leq ck<\lg\frac{1}{\delta},$

which implies that

$\Pr_{D}[Dx=x]=2^{-\|x\|_{0}}>\delta.$

Secondly, due to the Kronecker structure of $A_{l}$ and the fact that $z$ is
orthogonal to the rows of $A_{1}$, we have

$Ax=\mathbf{0}.$

Taken together, we can conclude

$\Pr_{f\sim\mathsf{LWT}}[f(x)=\mathbf{0}]\geq\Pr_{D}[A_{l}Dx=\mathbf{0}]\geq\Pr_{D}[Dx=x]>\delta.$

Now we just need to show that
$\|x\|_{\infty}/\|x\|_{2}=\Theta(\log^{-1/2}\frac{1}{\delta})$. Since $c$ is a
constant and $x$ is consists of $k=\Theta(\log\frac{1}{\delta})$ copies of $z$
followed by zeroes,

$\displaystyle\|x\|_{\infty}$ $\displaystyle=\|z\|_{\infty}$
$\displaystyle=\Theta(1),$ $\displaystyle\|z\|_{2}$ $\displaystyle=\Theta(1),$
$\displaystyle\|x\|_{2}$ $\displaystyle=\sqrt{k}\|z\|_{2}$
$\displaystyle=\Theta\bigl{(}\sqrt{\log\frac{1}{\delta}}\bigr{)},$

which implies the claimed ratio,

$\frac{\|x\|_{\infty}}{\|x\|_{2}}=\Theta(\log^{-1/2}\frac{1}{\delta}).$

∎

The following corollary is just a restatement of proposition 1.11 in terms of
lemma 1.2, and the proof therefore follows immediately from proposition 1.11.

######  Corollary 2.2.

For every $m,d,\in\mathbb{N}_{1}$, and $\delta,\varepsilon\in(0,1)$, and LWTJL
distribution $\mathsf{LWT}$ over $f\colon\mathbb{K}^{d}\to\mathbb{K}^{m}$,
where $\mathbb{K}\in\\{\mathbb{R},\mathbb{C}\\}$ and $m<d$ there exists a
vector $x\in\mathbb{K}^{d}$ with
$\|x\|_{\infty}/\|x\|_{2}=\Theta(\log^{-1/2}\frac{1}{\delta})$ such that

$\Pr_{f\sim\mathsf{LWT}}\Bigl{[}\,\bigl{|}\,\|f(x)\|_{2}^{2}-\|x\|_{2}^{2}\,\bigr{|}\leq\varepsilon\|x\|_{2}^{2}\,\Bigr{]}<1-\delta.$

itemauthordefault10highlight itemauthordefault10highlight
itemauthordefault10highlight

## References

  * (1) Nir Ailon and Bernard Chazelle  “Approximate nearest neighbors and the fast Johnson–Lindenstrauss transform”  In _Proceedings of the 38th Symposium on Theory of Computing_ , STOC ’06  ACM, 2006, pp. 557–563  DOI: 10.1145/1132516.1132597
  * (2) Nir Ailon and Bernard Chazelle  “The fast Johnson–Lindenstrauss transform and approximate nearest neighbors”  In _Journal on Computing_ 39.1 SIAM, 2009, pp. 302–322  DOI: 10.1137/060673096
  * (3) Dimitris Achlioptas  “Database-friendly Random Projections”  In _Proceedings of the 20th Symposium on Principles of Database Systems_ , PODS ’01  ACM, 2001, pp. 274–281  DOI: 10.1145/375551.375608
  * (4) Dimitris Achlioptas  “Database-friendly random projections: Johnson–Lindenstrauss with binary coins”  In _Journal of Computer and System Sciences_ 66.4 Elsevier, 2003, pp. 671–687  DOI: 10.1016/S0022-0000(03)00025-4
  * (5) Farhad Pourkamali Anaraki and Shannon Hughes  “Memory and Computation Efficient PCA via Very Sparse Random Projections”  In _Proceedings of the 31st International Conference on Machine Learning (ICML ’14)_ 32.2, Proceedings of Machine Learning Research (PMLR)  PMLR, 2014, pp. 1341–1349
  * (6) Alexandr Andoni and Piotr Indyk  “Nearest Neighbors in High-Dimensional Spaces”  In _Handbook of Discrete and Computational Geometry_ CRC Press, 2017, pp. 1135–1155
  * (7) Noga Alon and Bo’Az B. Klartag  “Optimal Compression of Approximate Inner Products and Dimension Reduction”  In _Proceedings of the 58th Symposium on Foundations of Computer Science_ , FOCS ’17  IEEE, 2017, pp. 639–650  DOI: 10.1109/FOCS.2017.65
  * (8) Nir Ailon and Edo Liberty  “Fast dimension reduction using Rademacher series on dual BCH codes”  In _Proceedings of the 19th Symposium on Discrete Algorithms_ , SODA ’08  SIAM, 2008, pp. 1–9
  * (9) Nir Ailon and Edo Liberty  “Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes”  In _Discrete & Computational Geometry_ 42.4, 2009, pp. 615–630  DOI: 10.1007/s00454-008-9110-x
  * (10) Nir Ailon and Edo Liberty  “An Almost Optimal Unrestricted Fast Johnson–Lindenstrauss Transform”  In _Proceedings of the 22nd Symposium on Discrete Algorithms_ , SODA ’11  SIAM, 2011, pp. 185–191  DOI: 10.1137/1.9781611973082.17
  * (11) Nir Ailon and Edo Liberty  “An Almost Optimal Unrestricted Fast Johnson–Lindenstrauss Transform”  In _Transactions on Algorithms_ 9.3 ACM, 2013, pp. 21:1–21:12  DOI: 10.1145/2483699.2483701
  * (12) Madhu Advani, Subhaneil Lahiri and Surya Ganguli  “Statistical mechanics of complex neural systems and high dimensional data”  In _Journal of Statistical Mechanics: Theory and Experiment_ 2013.03 IOP Publishing, 2013, pp. P03014  DOI: 10.1088/1742-5468/2013/03/p03014
  * (13) Zeyuan Allen-Zhu, Rati Gelashvili, Silvio Micali and Nir Shavit  “Sparse sign-consistent Johnson–Lindenstrauss matrices: Compression with neuroscience-based constraints”  In _Proceedings of the National Academy of Sciences (PNAS)_ 111.47 National Academy of Sciences, 2014, pp. 16872–16876  DOI: 10.1073/pnas.1419100111
  * (14) Noga Alon, Phillip B. Gibbons, Yossi Matias and Mario Szegedy  “Tracking Join and Self-Join Sizes in Limited Storage”  In _Journal of Computer and System Sciences_ 64.3 Elsevier, 2002, pp. 719–747  DOI: 10.1006/jcss.2001.1813
  * (15) Daniel Aloise, Amit Deshpande, Pierre Hansen and Preyas Popat  “NP-hardness of Euclidean sum-of-squares clustering”  In _Machine Learning_ 75 Springer, 2009, pp. 245–248  DOI: 10.1007/s10994-009-5103-0
  * (16) Noga Alon, Phillip B. Gibbons, Yossi Matias and Mario Szegedy  “Tracking Join and Self-Join Sizes in Limited Storage”  In _Proceedings of the 18th Symposium on Principles of Database Systems_ , PODS ’99  ACM, 1999, pp. 10–20  DOI: 10.1145/303976.303978
  * (17) Noga Alon, Yossi Matias and Mario Szegedy  “The Space Complexity of Approximating the Frequency Moments”  In _Proceedings of the 28th Symposium on Theory of Computing_ , STOC ’96  ACM, 1996, pp. 20–29  DOI: 10.1145/237814.237823
  * (18) Noga Alon, Yossi Matias and Mario Szegedy  “The Space Complexity of Approximating the Frequency Moments”  In _Journal of Computer and System Sciences_ 58.1, 1999, pp. 137–147  DOI: 10.1006/jcss.1997.1545
  * (19) Mazin Aouf and Laurence Anthony F. Park  “Approximate Document Outlier Detection Using Random Spectral Projection”  In _Proceedings of the 25th Australasian Joint Conference on Artificial Intelligence (AI ’12)_ 7691, Lecture Notes in Computer Science (LNCS)  Springer, 2012, pp. 579–590  DOI: 10.1007/978-3-642-35101-3_49
  * (20) Devansh Arpit, Ifeoma Nwogu, Gaurav Srivastava and Venu Govindaraju  “An Analysis of Random Projections in Cancelable Biometrics”  In _arXiv e-prints_ , 2014  arXiv:1401.4489 [cs.CV]
  * (21) Rosa I. Arriaga and Santosh S. Vempala  “An algorithmic theory of learning: Robust concepts and random projection”  In _Machine Learning_ 63.2 Springer, 2006, pp. 161–182  DOI: 10.1007/s10994-006-6265-7
  * (22) Rosa I. Arriaga and Santosh S. Vempala  “An Algorithmic Theory of Learning: Robust Concepts and Random Projection”  In _Proceedings of the 40th Symposium on Foundations of Computer Science_ , FOCS ’99  IEEE, 1999, pp. 616–623  DOI: 10.1109/SFFCS.1999.814637
  * (23) Haim Avron, Christos Boutsidis, Sivan Toledo and Anastasios Zouzias  “Efficient Dimensionality Reduction for Canonical Correlation Analysis”  In _Journal on Scientific Computing_ 36.5 SIAM, 2014, pp. S111–S131  DOI: 10.1137/130919222
  * (24) Waheed Uz Zaman Bajwa, Jarvis D. Haupt, Gil M. Raz, Stephen J. Wright and Robert D. Nowak  “Toeplitz-Structured Compressed Sensing Matrices”  In _Proceedings of the 14th Workshop on Statistical Signal Processing_ , SSP ’07  IEEE, 2007, pp. 294–298  DOI: 10.1109/SSP.2007.4301266
  * (25) Waheed Uz Zaman Bajwa  “Geometry of random Toeplitz-block sensing matrices: bounds and implications for sparse signal processing”  In _Proceedings of the Compressed Sensing track of the 7th Conference on Defense, Security, and Sensing (DSS ’12)_ 8365, Proceedings of SPIE  SPIE, 2012, pp. 16–22  DOI: 10.1117/12.919475
  * (26) Richard Baraniuk, Mark Davenport, Ronald DeVore and Michael Wakin  “A Simple Proof of the Restricted Isometry Property for Random Matrices”  In _Constructive Approximation_ 28.3 Springer, 2008, pp. 253–263  DOI: 10.1007/s00365-007-9003-x
  * (27) Jean Bourgain, Sjoerd Dirksen and Jelani Nelson  “Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space”  In _Proceedings of the 47th Symposium on Theory of Computing_ , STOC ’15  ACM, 2015, pp. 499–508  DOI: 10.1145/2746539.2746541
  * (28) Jean Bourgain, Sjoerd Dirksen and Jelani Nelson  “Toward a unified theory of sparse dimensionality reduction in Euclidean space”  In _Geometric and Functional Analysis (GAFA)_ 25.4 Springer, 2015, pp. 1009–1088  DOI: 10.1007/s00039-015-0332-9
  * (29) Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni and Chris Schwiegelshohn  “Oblivious dimension reduction for $k$-means: beyond subspaces and the Johnson–Lindenstrauss lemma”  In _Proceedings of the 51st Symposium on Theory of Computing_ , STOC ’19  ACM, 2019, pp. 1039–1050  DOI: 10.1145/3313276.3316318
  * (30) Michael A. Burr, Shuhong Gao and Fiona Knoll  “Optimal Bounds for Johnson–Lindenstrauss Transformations”  In _Journal of Machine Learning Research_ 19.73 JMLR, 2018, pp. 1–22
  * (31) Stefan Bamberger and Felix Krahmer  “Optimal Fast Johnson–Lindenstrauss Embeddings for Large Data Sets”  In _arXiv e-prints_ , 2017  arXiv:1712.01774 [cs.DS]
  * (32) Jeremiah Blocki, Avrim Blum, Anupam Datta and Or Sheffet  “The Johnson–Lindenstrauss Transform Itself Preserves Differential Privacy”  In _Proceedings of the 53rd Symposium on Foundations of Computer Science_ , FOCS ’12  IEEE, 2012, pp. 410–419  DOI: 10.1109/FOCS.2012.67
  * (33) Ella Bingham and Heikki Mannila  “Random Projection in Dimensionality Reduction: Applications to Image and Text Data”  In _Proceedings of the 7th International Conference on Knowledge Discovery and Data Mining_ , KDD ’01  ACM, 2001, pp. 245–250
  * (34) Hans-Hermann Bock  “Origins and Extensions of the $k$-Means Algorithm in Cluster Analysis”  In _Electronic Journal for History of Probability and Statistics_ 4.2, 2008, pp. 9:1–9:18
  * (35) Vladimir Braverman, Rafail Ostrovsky and Yuval Rabani  “Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson–Lindenstrauss Transform” Presented at the Embedding worshop (DANW01) at Isaac Newton Institute for Mathematical Sciences  In _arXiv e-prints_ , 2010  arXiv:1011.2590 [cs.DS]
  * (36) Christos Boutsidis, Anastasios Zouzias, Michael W. Mahoney and Petros Drineas  “Randomized Dimensionality Reduction for $k$-Means Clustering”  In _Transactions on Information Theory_ 61.2 IEEE, 2014, pp. 1045–1062  DOI: 10.1109/TIT.2014.2375327
  * (37) Anna Breger, Gabriel Ramos Llorden, Gonzalo Vegas Sanchez-Ferrero, W. Hoge, Martin Ehler and Carl-Fredrik Westin  “On the Reconstruction Accuracy of Multi-Coil MRI with Orthogonal Projections”  In _arXiv e-prints_ , 2019  arXiv:1910.13422 [physics.med-ph]
  * (38) Anna Breger, José Ignacio Orlando, Pavol Harár, Monika Dörfler, Sophie Klimscha, Christoph Grechenig, Bianca S. Gerendas, Ursula Schmidt-Erfurth and Martin Ehler  “On Orthogonal Projections for Dimension Reduction and Applications in Augmented Target Loss Functions for Learning Problems”  In _Journal of Mathematical Imaging and Vision_ 62.3 Springer, 2020, pp. 376–394  DOI: 10.1007/s10851-019-00902-2
  * (39) Christos Boutsidis, Anastasios Zouzias and Petros Drineas  “Random Projections for $k$-means Clustering”  In _Advances in Neural Information Processing Systems 23_ , NIPS ’10  Curran Associates, Inc., 2010, pp. 298–306
  * (40) Timothy I. Cannings  “Random projections: Data perturbation for classification problems”  In _WIREs Computational Statistics_ 13.1 Wiley, 2020, pp. e1499  DOI: 10.1002/wics.1499
  * (41) Sophie J.. Caron, Vanessa Ruta, L.. Abbott and Richard Axel  “Random convergence of olfactory inputs in the Drosophila mushroom body”  In _Nature_ 497.7447 Springer Nature, 2013, pp. 113–117  DOI: 10.1038/nature12063
  * (42) Moses Charikar, Kevin C. Chen and Martin Farach-Colton  “Finding Frequent Items in Data Streams”  In _Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP ’02)_ 2380, Lecture Notes in Computer Science (LNCS)  Springer, 2002, pp. 693–703  DOI: 10.1007/3-540-45465-9_59
  * (43) Moses Charikar, Kevin C. Chen and Martin Farach-Colton  “Finding Frequent Items in Data Streams”  In _Theoretical Computer Science_ 312.1 Elsevier, 2004, pp. 3–15  DOI: 10.1016/S0304-3975(03)00400-6
  * (44) Graham Cormode and Minos N. Garofalakis  “Sketching Streams Through the Net: Distributed Approximate Query Tracking”  In _Proceedings of the 31st International Conference on Very Large Data Bases_ , VLDB ’05  ACM, 2005, pp. 13–24
  * (45) Robert Calderbank, Sina Jafarpour and Robert Schapire  “Compressed Learning: Universal Sparse Dimensionality Reduction and Learning in the Measurement Domain”, Manuscript, 2009  URL: https://core.ac.uk/display/21147568
  * (46) Michael B. Cohen, Cameron Musco and Christopher Musco  “Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling”  In _Proceedings of the 28th Symposium on Discrete Algorithms_ , SODA ’17  SIAM, 2017, pp. 1758–1777  DOI: 10.1137/1.9781611974782.115
  * (47) Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco and Madalina Persu  “Dimensionality Reduction for $k$-Means Clustering and Low Rank Approximation”  In _Proceedings of the 47th Symposium on Theory of Computing_ , STOC ’15  ACM, 2015, pp. 163–172  DOI: 10.1145/2746539.2746569
  * (48) Emmanuel J. Candès, Justin K. Romberg and Terence Tao  “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information”  In _Transactions on Information Theory_ 52.2 IEEE, 2006, pp. 489–509  DOI: 10.1109/TIT.2005.862083
  * (49) Timothy I. Cannings and Richard J. Samworth  “Random Projection Ensemble Classification”  In _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ 79.4 Wiley, 2017, pp. 959–1035  DOI: 10.1111/rssb.12228
  * (50) Emmanuel J. Candès and Terence Tao  “Decoding by linear programming”  In _Transactions on Information Theory_ 51.12 IEEE, 2005, pp. 4203–4215  DOI: 10.1109/TIT.2005.858979
  * (51) Emmanuel J. Candès and Terence Tao  “Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?”  In _Transactions on Information Theory_ 52.12 IEEE, 2006, pp. 5406–5425  DOI: 10.1109/TIT.2006.885507
  * (52) Kenneth L. Clarkson and David P. Woodruff  “Low rank approximation and regression in input sparsity time”  In _Proceedings of the 45th Symposium on Theory of Computing_ , STOC ’13  ACM, 2013, pp. 81–90  DOI: 10.1145/2488608.2488620
  * (53) Kenneth L. Clarkson and David P. Woodruff  “Low-Rank Approximation and Regression in Input Sparsity Time”  In _Journal of the ACM_ 63.6 ACM, 2017, pp. 54:1–54:45  DOI: 10.1145/3019134
  * (54) Sanjoy Dasgupta  “Experiments with Random Projection”  In _Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence_ , UAI ’00  Morgan Kaufmann, 2000, pp. 143–151
  * (55) Sanjoy Dasgupta  “The hardness of $k$-means clustering”, 2008
  * (56) Sanjoy Dasgupta  “Learning Mixtures of Gaussians”  In _Proceedings of the 40th Symposium on Foundations of Computer Science_ , FOCS ’99  IEEE, 1999, pp. 634–644  DOI: 10.1109/SFFCS.1999.814639
  * (57) Mayur Datar, Nicole Immorlica, Piotr Indyk and Vahab Seyed Mirrokni  “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions”  In _Proceedings of the 20th Symposium on Computational Geometry_ , SoCG ’04  ACM, 2004, pp. 253–262  DOI: 10.1145/997817.997857
  * (58) Sampath Deegalla and Henrik Boström  “Reducing High-Dimensional Data by Principal Component Analysis vs. Random Projection for Nearest Neighbor Classification”  In _Proceedings of the 5th International Conference on Machine Learning and Applications_ , ICMLA ’06  IEEE, 2006, pp. 245–250  DOI: 10.1109/ICMLA.2006.43
  * (59) James Demmel, Ioana Dumitriu and Olga Holtz  “Fast linear algebra is stable”  In _Numerische Mathematik_ 108.1 Springer, 2007, pp. 59–91  DOI: 10.1007/s00211-007-0114-x
  * (60) David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider and S. Seshadri  “Practical Skew Handling in Parallel Joins”  In _Proceedings of the 18th International Conference on Very Large Data Bases_ , VLDB ’92  Morgan Kaufmann, 1992, pp. 27–40
  * (61) Sanjoy Dasgupta and Anupam Gupta  “An Elementary Proof of a Theorem of Johnson and Lindenstrauss”  In _Random Structures & Algorithms_ 22.1 Wiley, 2002, pp. 60–65  DOI: 10.1002/rsa.10073
  * (62) Sjoerd Dirksen  “Dimensionality Reduction with Subgaussian Matrices: A Unified Theory”  In _Foundations of Computational Mathematics volume_ 16.5 Springer, 2016, pp. 1367–1396  DOI: 10.1007/s10208-015-9280-x
  * (63) Sjoerd Dirksen, Hans Christian Jung and Holger Rauhut  “One-bit compressed sensing with partial Gaussian circulant matrices”  In _Information and Inference: A Journal of the IMA_ Oxford University Press, 2019, pp. iaz017  DOI: 10.1093/imaiai/iaz017
  * (64) Robert J. Durrant and Ata Kabán  “Compressed Fisher Linear Discriminant Analysis: Classification of Randomly Projected Data”  In _Proceedings of the 16th International Conference on Knowledge Discovery and Data Mining_ , KDD ’10  ACM, 2010, pp. 1119–1128  DOI: 10.1145/1835804.1835945
  * (65) Robert Durrant and Ata Kabán  “Random Projections as Regularizers: Learning a Linear Discriminant Ensemble from Fewer Observations than Dimensions”  In _Proceedings of the 5th Asian Conference on Machine Learning (ACML ’13)_ 29, Proceedings of Machine Learning Research (PMLR)  PMLR, 2013, pp. 17–32
  * (66) Anirban Dasgupta, Ravi Kumar and Tamás Sarlós  “A Sparse Johnson–Lindenstrauss Transform”  In _Proceedings of the 42nd Symposium on Theory of Computing_ , STOC ’10  ACM, 2010, pp. 341–350  DOI: 10.1145/1806689.1806737
  * (67) Søren Dahlgaard, Mathias Bæk Tejs Knudsen and Mikkel Thorup  “Practical Hash Functions for Similarity Estimation and Dimensionality Reduction”  In _Advances in Neural Information Processing Systems 30_ , NIPS ’17  Curran Associates, Inc., 2017, pp. 6615–6625
  * (68) Thong T. Do, Lu Gan, Yi Chen, Nam Hoai Nguyen and Trac D. Tran  “Fast and efficient dimensionality reduction using Structurally Random Matrices”  In _Proceedings of the 34th International Conference on Acoustics, Speech, and Signal Processing_ , ICASSP ’09  IEEE, 2009, pp. 1821–1824  DOI: 10.1109/ICASSP.2009.4959960
  * (69) David L. Donoho  “For Most Large Underdetermined Systems of Equations, the Minimal $\ell_{1}$-norm Near-Solution Approximates the Sparsest Near-Solution”  In _Communications on Pure and Applied Mathematics_ 59.7 Wiley, 2006, pp. 907–934  DOI: 10.1002/cpa.20131
  * (70) Timothy Vries, Sanjay Chawla and Michael E. Houle  “Finding Local Anomalies in Very High Dimensional Space”  In _Proceedings of the 10th International Conference on Data Mining_ , ICDM ’03  IEEE, 2010, pp. 128–137  DOI: 10.1109/ICDM.2010.151
  * (71) Xiaoli Zhang Fern and Carla E. Brodley  “Random Projection for High Dimensional Data Clustering: A Cluster Ensemble Approach”  In _Proceedings of the 20th International Conference on Machine Learning_ , ICML ’03  AAAI Press, 2003, pp. 186–193
  * (72) Casper Benjamin Freksen, Lior Kamma and Kasper Green Larsen  “Fully Understanding the Hashing Trick”  In _Advances in Neural Information Processing Systems 31_ , NeurIPS ’18  Curran Associates, Inc., 2018, pp. 5394–5404
  * (73) Casper Benjamin Freksen and Kasper Green Larsen  “On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms”  In _Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC ’17)_ 92, Leibniz International Proceedings in Informatics (LIPIcs)  Schloss Dagstuhl, 2017, pp. 32:1–32:12  DOI: 10.4230/LIPIcs.ISAAC.2017.32
  * (74) Casper Benjamin Freksen and Kasper Green Larsen  “On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms”  In _Algorithmica_ 82.2 Springer, 2020, pp. 338–354  DOI: 10.1007/s00453-019-00644-y
  * (75) Dmitriy Fradkin and David Madigan  “Experiments with Random Projections for Machine Learning”  In _Proceedings of the 9th International Conference on Knowledge Discovery and Data Mining_ , KDD ’03  ACM, 2003, pp. 517–522  DOI: 10.1145/956750.956812
  * (76) Peter Frankl and Hiroshi Maehara  “The Johnson–Lindenstrauss lemma and the sphericity of some graphs”  In _Journal of Combinatorial Theory, Series B_ 44.3 Elsevier, 1988, pp. 355–362  DOI: 10.1016/0095-8956(88)90043-3
  * (77) Peter Frankl and Hiroshi Maehara  “Some geometric applications of the beta distribution”  In _Annals of the Institute of Statistical Mathematics (AISM)_ 42 Springer, 1990, pp. 463–474  DOI: 10.1007/BF00049302
  * (78) Casper Benjamin Freksen  “A Song of Johnson and Lindenstrauss”, 2020
  * (79) Kuzman Ganchev and Mark Dredze  “Small Statistical Models by Random Feature Mixing”  In _Mobile NLP workshop at the 46th Annual Meeting of the Association for Computational Linguistics (ACL ’08)_ , ACL08-Mobile-NLP, 2008, pp. 19–20
  * (80) Anna C. Gilbert, Yannis Kotidis, Shanmugavelayutham Muthukrishnan and M.. Strauss  “QuickSAND: Quick Summary and Analysis of Network Data”, 2001
  * (81) Chris Giannella, Kun Liu and Hillol Kargupta  “Breaching Euclidean Distance-Preserving Data Perturbation using few Known Inputs”  In _Data & Knowledge Engineering_ 83, 2013, pp. 93–110  DOI: 10.1016/j.datak.2012.10.004
  * (82) Surya Ganguli and Haim Sompolinsky  “Compressed Sensing, Sparsity, and Dimensionality in Neuronal Information Processing and Data Analysis”  In _Annual Review of Neuroscience_ 35.1 Annual Reviews, 2012, pp. 485–508  DOI: 10.1146/annurev-neuro-062111-150410
  * (83) Xiao Guo, Yixuan Qiu, Hai Zhang and Xiangyu Chang  “Randomized spectral co-clustering for large-scale directed networks”  In _arXiv e-prints_ , 2020  arXiv:2004.12164 [stat.ML]
  * (84) Sariel Har-Peled  “A Replacement for Voronoi Diagrams of Near Linear Size”  In _Proceedings of the 42nd Symposium on Foundations of Computer Science_ , FOCS ’01  IEEE, 2001, pp. 94–103  DOI: 10.1109/SFCS.2001.959884
  * (85) Jarvis D. Haupt, Waheed Uz Zaman Bajwa, Gil M. Raz and Robert D. Nowak  “Toeplitz Compressed Sensing Matrices With Applications to Sparse Channel Estimation”  In _Transactions on Information Theory_ 56.11 IEEE, 2010, pp. 5862–5875  DOI: 10.1109/TIT.2010.2070191
  * (86) Sariel Har-Peled and Piotr Indyk  “When Crossings Count — Approximating the Minimum Spanning Tree”  In _Proceedings of the 16th Symposium on Computational Geometry_ , SoCG ’00  ACM, 2000, pp. 166–175  DOI: 10.1145/336154.336197
  * (87) Sariel Har-Peled, Piotr Indyk and Rajeev Motwani  “Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality”  In _Theory of Computing_ 8.14, 2012, pp. 321–350  DOI: 10.4086/toc.2012.v008a014
  * (88) Christina Heinze, Brian McWilliams and Nicolai Meinshausen  “Dual-Loco: Distributing Statistical Estimation Using Random Projections”  In _Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS ’16)_ 51, Proceedings of Machine Learning Research (PMLR)  PMLR, 2016, pp. 875–883
  * (89) N. Halko, P.. Martinsson and Joel Aaron Tropp  “Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions”  In _SIAM Review_ 53.2 SIAM, 2011, pp. 217–288  DOI: 10.1137/090771806
  * (90) Harold Hotelling  “Analysis of a Complex of Statistical Variables into Principal Components”  In _Journal of Educational Psychology_ 24.6 APA, 1933, pp. 417–441  DOI: 10.1037/h0071325
  * (91) Reinhard Heckel, Michael Tschannen and Helmut Bölcskei  “Subspace clustering of dimensionality-reduced data”  In _Proceedings of the 47th International Symposium on Information Theory_ , ISIT ’14  IEEE, 2014, pp. 2997–3001  DOI: 10.1109/ISIT.2014.6875384
  * (92) Reinhard Heckel, Michael Tschannen and Helmut Bölcskei  “Dimensionality-reduced subspace clustering”  In _Information and Inference: A Journal of the IMA_ 6.3, 2017, pp. 246–283  DOI: 10.1093/imaiai/iaw021
  * (93) Trevor Hastie, Robert Tibshirani and Jerome Friedman  “The Elements of Statistical Learning: Data Mining, Inference, and Prediction” 12th printing, Springer Series in Statistics (SSS)  Springer, 2017  DOI: 10.1007/b94608
  * (94) Aicke Hinrichs and Jan Vybíral  “Johnson–Lindenstrauss lemma for circulant matrices”  In _Random Structures & Algorithms_ 39.3 Wiley, 2011, pp. 391–398  DOI: 10.1002/rsa.20360
  * (95) Piotr Indyk and Rajeev Motwani  “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality”  In _Proceedings of the 30th Symposium on Theory of Computing_ , STOC ’98  ACM, 1998, pp. 604–613  DOI: 10.1145/276698.276876
  * (96) Piotr Indyk and Assaf Naor  “Nearest-Neighbor-Preserving embeddings”  In _Transactions on Algorithms_ 3.3 ACM, 2007, pp. 31:1–31:12  DOI: 10.1145/1273340.1273347
  * (97) Piotr Indyk  “Algorithmic Applications of Low-Distortion Geometric Embeddings”  In _Proceedings of the 42nd Symposium on Foundations of Computer Science_ , FOCS ’01  IEEE, 2001, pp. 10–33  DOI: 10.1109/SFCS.2001.959878
  * (98) Meena Jagadeesan  “Understanding Sparse JL for Feature Hashing”  In _Advances in Neural Information Processing Systems 32_ , NeurIPS ’19  Curran Associates, Inc., 2019, pp. 15203–15213
  * (99) Vishesh Jain, Natesh S. Pillai, Ashwin Sah, Mehtaab Sawhney and Aaron Smith  “Fast and memory-optimal dimension reduction using Kac’s walk”  In _arXiv e-prints_ , 2020  arXiv:2003.10069 [cs.DS]
  * (100) Gareth James, Daniela Witten, Trevor Hastie and Robert Tibshirani  “An Introduction to Statistical Learning” 7th printing, Springer Texts in Statistics (STS)  Springer, 2013  DOI: 10.1007/978-1-4614-7138-7
  * (101) Gareth James, Daniela Witten, Trevor Hastie and Robert Tibshirani  “An Introduction to Statistical Learning” 7th printing, Springer Texts in Statistics (STS)  Springer, 2013  DOI: 10.1007/978-1-4614-7138-7
  * (102) Haotian Jiang, Yin Tat Lee, Zhao Song and Sam Chiu-wai Wong  “An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications”  In _Proceedings of the 52nd Symposium on Theory of Computing_ , STOC ’20  ACM, 2020, pp. 944–953  DOI: 10.1145/3357713.3384284
  * (103) William B Johnson and Joram Lindenstrauss  “Extensions of Lipschitz mappings into a Hilbert space”  In _Proceedings of the 1982 Conference in Modern Analysis and Probability_ 26, Contemporary Mathematics  AMS, 1984, pp. 189–206  DOI: 10.1090/conm/026/737400
  * (104) Ian T. Jolliffe  “Principal Component Analysis”, Springer Series in Statistics (SSS)  Springer, 2002  DOI: 10.1007/b98835
  * (105) Richard Jensen and Qiang Shen  “Computational Intelligence and Feature Selection - Rough and Fuzzy Approaches”, IEEE Press series on computational intelligence  IEEE, 2008  DOI: 10.1002/9780470377888
  * (106) T.. Jayram and David P. Woodruff  “Optimal Bounds for Johnson–Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error”  In _Proceedings of the 22nd Symposium on Discrete Algorithms_ , SODA ’11  SIAM, 2011, pp. 1–10  DOI: 10.1137/1.9781611973082.1
  * (107) T.. Jayram and David P. Woodruff  “Optimal Bounds for Johnson–Lindenstrauss Transforms and Streaming Problems with Subconstant Error”  In _Transactions on Algorithms_ 9.3 ACM, 2013, pp. 26:1–26:17  DOI: 10.1145/2483699.2483706
  * (108) Ata Kabán  “New Bounds on Compressive Linear Least Squares Regression”  In _Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, (AISTATS ’14)_ 33, Proceedings of Machine Learning Research (PMLR)  PMLR, 2014, pp. 448–456
  * (109) Mark Kac  “Foundations of Kinetic Theory”  In _Proceedings of the 3rd Berkeley Symposium on Mathematical Statistics and Probability_ 3 University of California Press, 1956, pp. 171–197
  * (110) Samuel Kaski  “Dimensionality Reduction by Random Mapping: Fast Similarity Computation for Clustering”  In _Proceedings of the 8th International Joint Conference on Neural Networks_ 1, IJCNN ’98  IEEE, 1998, pp. 413–418  DOI: 10.1109/IJCNN.1998.682302
  * (111) Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov and Nina Mishra  “Privacy via the Johnson–Lindenstrauss Transform”  In _Journal of Privacy and Confidentiality_ 5.1, 2013  DOI: 10.29012/jpc.v5i1.625
  * (112) Shiva Prasad Kasiviswanathan and Hongxia Jin  “Efficient Private Empirical Risk Minimization for High-dimensional Learning”  In _Proceedings of the 33st International Conference on Machine Learning (ICML ’16)_ 48, Proceedings of Machine Learning Research (PMLR)  PMLR, 2016, pp. 488–497
  * (113) Jon M. Kleinberg  “Two Algorithms for Nearest-Neighbor Search in High Dimensions”  In _Proceedings of the 29th Symposium on the Theory of Computing_ , STOC ’97  ACM, 1997, pp. 599–608  DOI: 10.1145/258533.258653
  * (114) Bo’Az B. Klartag and Shahar Mendelson  “Empirical processes and random projections”  In _Journal of Functional Analysis_ 225.1 Elsevier, 2005, pp. 229–245  DOI: 10.1016/j.jfa.2004.10.009
  * (115) Daniel M. Kane, Raghu Meka and Jelani Nelson  “Almost Optimal Explicit Johnson–Lindenstrauss Families”  In _Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX ’11) and the 15th International Workshop on Randomization and Computation (RANDOM ’11)_ 6845, Lecture Notes in Computer Science (LNCS)  Springer, 2011, pp. 628–639  DOI: 10.1007/978-3-642-22935-0_53
  * (116) Daniel M. Kane and Jelani Nelson  “A Derandomized Sparse Johnson–Lindenstrauss Transform”  In _arXiv e-prints_ , 2010  arXiv:1006.3585 [cs.DS]
  * (117) Daniel M. Kane and Jelani Nelson  “Sparser Johnson–Lindenstrauss Transforms”  In _Proceedings of the 23rd Symposium on Discrete Algorithms_ , SODA ’12  SIAM, 2012, pp. 1195–1206  DOI: 10.1137/1.9781611973099.94
  * (118) Daniel M. Kane and Jelani Nelson  “Sparser Johnson–Lindenstrauss Transforms”  In _Journal of the ACM_ 61.1 ACM, 2014, pp. 4:1–4:23  DOI: 10.1145/2559902
  * (119) Eyal Kushilevitz, Rafail Ostrovsky and Yuval Rabani  “Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces”  In _Journal on Computing_ 30.2 SIAM, 2000, pp. 457–474  DOI: 10.1137/S0097539798347177
  * (120) Eyal Kushilevitz, Rafail Ostrovsky and Yuval Rabani  “Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces”  In _Proceedings of the 30th Symposium on the Theory of Computing_ , STOC ’98  ACM, 1998, pp. 614–623  DOI: 10.1145/276698.276877
  * (121) Felix Krahmer and Rachel Ward  “New and improved Johnson–Lindenstrauss embeddings via the Restricted Isometry Property”  In _Journal on Mathematical Analysis_ 43.3 SIAM, 2011, pp. 1269–1281  DOI: 10.1137/100810447
  * (122) SeongYoon Kim and SeYoung Yun  “Accelerating Randomly Projected Gradient with Variance Reduction”  In _Proceedings of the 7th International Conference on Big Data and Smart Computing_ , BigComp ’20  IEEE, 2020, pp. 531–534  DOI: 10.1109/BigComp48618.2020.00-11
  * (123) Edo Liberty, Nir Ailon and Amit Singer  “Dense Fast Random Projections and Lean Walsh Transforms”  In _Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX ’08) and the 12th International Workshop on Randomization and Computation (RANDOM ’08)_ 5171, Lecture Notes in Computer Science (LNCS)  Springer, 2008, pp. 512–522  DOI: 10.1007/978-3-540-85363-3_40
  * (124) Edo Liberty, Nir Ailon and Amit Singer  “Dense Fast Random Projections and Lean Walsh Transforms”  In _Discrete & Computational Geometry_ 45.1 Springer, 2011, pp. 34–44  DOI: 10.1007/s00454-010-9309-5
  * (125) François Le Gall  “Powers of Tensors and Fast Matrix Multiplication”  In _Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation_ , ISSAC ’14  ACM, 2014, pp. 296–303  DOI: 10.1145/2608628.2608664
  * (126) Jie Li, Rongrong Ji, Hong Liu, Jianzhuang Liu, Bineng Zhong, Cheng Deng and Qi Tian  “Projection & Probability-Driven Black-Box Attack”  In _arXiv e-prints_ , 2020  arXiv:2005.03837 [cs.CV]
  * (127) Wenfen Liu, Mao Ye, Jianghong Wei and Xuexian Hu  “Fast Constrained Spectral Clustering and Cluster Ensemble with Random Projection”  In _Computational Intelligence and Neuroscience_ 2017 Hindawi, 2017  DOI: 10.1155/2017/2658707
  * (128) Kun Liu, Hillol Kargupta and Jessica Ryan  “Random Projection-Based Multiplicative Data Perturbation for Privacy Preserving Distributed Data Mining”  In _Transactions on Knowledge and Data Engineering_ 18.1 IEEE, 2006, pp. 92–106  DOI: 10.1109/TKDE.2006.14
  * (129) Zijian Lei and Liang Lan  “Improved Subsampled Randomized Hadamard Transform for Linear SVM”  In _Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI ’20) and the 32nd Conference on Innovative Applications of Artificial Intelligence (IAAI ’20) and the 10th Symposium on Educational Advances in Artificial Intelligence (EAAI ’20)_ 34.4 AAAI Press, 2020, pp. 4519–4526  DOI: 10.1609/aaai.v34i04.5880
  * (130) Stuart P. Lloyd  “Least squares quantization in PCM”  In _Transactions on Information Theory_ 28.2 IEEE, 1982, pp. 129–137  DOI: 10.1109/TIT.1982.1056489
  * (131) John Langford, Lihong Li and Alexander L. Strehl  “Vowpal Wabbit Code Release”, 2007  URL: https://hunch.net/?p=309
  * (132) Kasper Green Larsen and Jelani Nelson  “Optimality of the Johnson–Lindenstrauss Lemma”  In _Proceedings of the 58th Symposium on Foundations of Computer Science_ , FOCS ’17  IEEE, 2017, pp. 633–638  DOI: 10.1109/FOCS.2017.64
  * (133) Grazia Lotti and Francesco Romani  “On the asymptotic complexity of rectangular matrix multiplication”  In _Theoretical Computer Science_ 23.2 Elsevier, 1983, pp. 171–185  DOI: 10.1016/0304-3975(83)90054-3
  * (134) Jure Leskovec, Anand Rajaraman and Jeffrey David Ullman  “Mining of Massive Datasets”  Cambridge University Press, 2020
  * (135) Jure Leskovec, Anand Rajaraman and Jeffrey David Ullman  “Mining of Massive Datasets”  Cambridge University Press, 2020
  * (136) Michael W. Mahoney  “Randomized Algorithms for Matrices and Data”  In _Foundations and Trends® in Machine Learning_ 3.2 now publishers, 2011, pp. 123–224  DOI: 10.1561/2200000035
  * (137) Jiří Matoušek  “On variants of the Johnson-Lindenstrauss lemma”  In _Random Structures & Algorithms_ 33.2 Wiley, 2008, pp. 142–156  DOI: 10.1002/rsa.20218
  * (138) Mala Murthy, Ila Fiete and Gilles Laurent  “Testing Odor Response Stereotypy in the Drosophila Mushroom Body”  In _Neuron_ 59.6 Elsevier, 2008, pp. 1009–1023  DOI: 10.1016/j.neuron.2008.07.040
  * (139) Odalric-Ambrym Maillard and Rémi Munos  “Compressed Least-Squares Regression”  In _Advances in Neural Information Processing Systems 22_ , NIPS ’09  Curran Associates, Inc., 2009, pp. 1213–1221
  * (140) Xiangrui Meng and Michael W. Mahoney  “Low-Distortion Subspace Embeddings in Input-Sparsity Time and Applications to Robust Linear Regression”  In _Proceedings of the 45th Symposium on Theory of Computing_ , STOC ’13  ACM, 2013, pp. 91–100  DOI: 10.1145/2488608.2488621
  * (141) Cameron Musco and Christopher Musco  “Projection-Cost-Preserving Sketches: Proof Strategies and Constructions”  In _arXiv e-prints_ , 2020  arXiv:2004.08434 [cs.DS]
  * (142) Konstantin Makarychev, Yury Makarychev and Ilya Razenshteyn  “Performance of Johnson–Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering”  In _Proceedings of the 51st Symposium on Theory of Computing_ , STOC ’19  ACM, 2019, pp. 1027–1038  DOI: 10.1145/3313276.3316350
  * (143) Florence Jessie MacWilliams and Neil James Alexander Sloane  “The Theory of Error-Correcting Codes” 16, North-Holland Mathematical Library  Elsevier, 1977
  * (144) S. Muthukrishnan  “Data Streams: Algorithms and Applications”  In _Foundations and Trends® in Theoretical Computer Science_ 1.2 now Publishers, 2005, pp. 117–236  DOI: 10.1561/0400000002
  * (145) Paula Navarro-Esteban and Juan Antonio Cuesta-Albertos  “High-dimensional outlier detection using random projections”  In _arXiv e-prints_ , 2020  arXiv:2005.08923 [stat.ME]
  * (146) Jelani Nelson  “Sketching and Streaming High-Dimensional Vectors”, 2011
  * (147) Xuan Vinh Nguyen, Sarah M. Erfani, Sakrapee Paisitkriangkrai, James Bailey, Christopher Leckie and Kotagiri Ramamohanarao  “Training robust models using Random Projection”  In _Proceedings of the 23rd International Conference on Pattern Recognition_ , ICPR ’16  IEEE, 2016, pp. 531–536  DOI: 10.1109/ICPR.2016.7899688
  * (148) Tuan S. Nguyen  “Dimension Reduction Methods with Applications to High Dimensional Data with a Censored Response”, 2009
  * (149) Lama B. Niyazi, Abla Kammoun, Hayssam Dahrouj, Mohamed-Slim Alouini and Tareq Y. Al-Naffouri  “Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants”  In _arXiv e-prints_ , 2020  arXiv:2004.08217 [stat.ML]
  * (150) Jelani Nelson and Huy Lê Nguy[-5.5pt]ê~n  “OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings”  In _Proceedings of the 54th Symposium on Foundations of Computer Science_ , FOCS ’13  IEEE, 2013, pp. 117–126  DOI: 10.1109/FOCS.2013.21
  * (151) Jelani Nelson and Huy Lê Nguy[-5.5pt]ê~n  “Sparsity Lower Bounds for Dimensionality Reducing Maps”  In _Proceedings of the 45th Symposium on Theory of Computing_ , STOC ’13  ACM, 2013, pp. 101–110  DOI: 10.1145/2488608.2488622
  * (152) Saurabh Paul, Christos Boutsidis, Malik Magdon-Ismail and Petros Drineas  “Random Projections for Support Vector Machines”  In _Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS ’13)_ 31, Proceedings of Machine Learning Research (PMLR)  PMLR, 2013, pp. 498–506
  * (153) Saurabh Paul, Christos Boutsidis, Malik Magdon-Ismail and Petros Drineas  “Random Projections for Linear Support Vector Machines”  In _Transactions on Knowledge Discovery from Data_ 8.4 ACM, 2014, pp. 22:1–22:25  DOI: 10.1145/2641760
  * (154) Karl Pearson  “On lines and planes of closest fit to systems of points in space”  In _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ 2.11 Taylor & Francis, 1901, pp. 559–572  DOI: 10.1080/14786440109462720
  * (155) Panagiotis C. Petrantonakis and Panayiota Poirazi  “A compressed sensing perspective of hippocampal function”  In _Frontiers in Systems Neuroscience_ 8 Frontiers, 2014, pp. 141  DOI: 10.3389/fnsys.2014.00141
  * (156) Mert Pilanci and Martin J. Wainwright  “Randomized Sketches of Convex Programs with Sharp Guarantees”  In _Proceedings of the 47th International Symposium on Information Theory_ , ISIT ’14  IEEE, 2014, pp. 921–925  DOI: 10.1109/ISIT.2014.6874967
  * (157) Mert Pilanci and Martin J. Wainwright  “Randomized Sketches of Convex Programs with Sharp Guarantees”  In _Transactions on Information Theory_ 61.9 IEEE, 2015, pp. 5096–5115  DOI: 10.1109/TIT.2015.2450722
  * (158) Holger Rauhut  “Circulant and Toeplitz matrices in compressed sensing”  In _Proceedings of the 2nd Workshop on Signal Processing with Adaptive Sparse Structured Representations_ , SPARS ’09  CCSD, 2009, pp. 32:1–32:6