# Node Similarities under Random Projections: Limits and Pathological Cases

Tvrtko Tadić
Microsoft Search,
Assistant and Intelligence
<EMAIL_ADDRESS>&Cassiano Becker
Microsoft Search,
Assistant and Intelligence
<EMAIL_ADDRESS>&Jennifer Neville
Microsoft Research
<EMAIL_ADDRESS>
###### Abstract

Random Projections have been widely used to generate embeddings for various
graph tasks due to their computational efficiency. The majority of
applications have been justified through the Johnson-Lindenstrauss Lemma. In
this paper, we take a step further and investigate how well dot product and
cosine similarity are preserved by Random Projections. Our analysis provides
new theoretical results, identifies pathological cases, and tests them with
numerical experiments. We find that, for nodes of lower or higher degrees, the
method produces especially unreliable embeddings for the dot product,
regardless of whether the adjacency or the (normalized version) transition is
used. With respect to the statistical noise introduced by Random Projections,
we show that cosine similarity produces remarkably more precise
approximations.

##  1 Introduction

Random projections (RP) provide a simple and elegant approach to
dimensionality reduction [36]. Leveraging concentration of measure phenomena
in high-dimensional statistics [37], RP’s rely on the well-known Johnson-
Lindenstrauss (JL) Lemma [21, 12] to provide data-independent guarantees for
approximation quality. As originally developed, the JL showed that Euclidean
distances between any two points in a dataset are preserved with high
probability if their vectors are projected using appropriately constructed
random matrices. Remarkably, the JL Lemma shows that the required projection
dimension of the random matrix needs to grow only logarithmically with the
ambient dimension of the dataset. As such, the JL Lemma has found wide
application in diverse fields such as information retrieval [24, 19], machine
learning [14, 8, 6, 9, 27], privacy [26, 38], and numerical linear algebra
[17, 28].

In the context of graphs, the JL Lemma can be applied to generate low-
dimensional encodings of a node’s connectivity to other nodes in the graph. In
that case, nodes are usually represented as vectors extracted as the rows of a
connectivity matrix [18], which is obtained from the adjacency matrix (or some
function of it). For example, it is known that the entries of the power of an
adjacency matrix encode the number of walks of length of that prescribed power
between any two nodes [29]. Likewise, the transition matrix can be used to
compute the corresponding random-walk probability between any pair of nodes
[4]. This notion is key to algorithms such as PageRank [30], which computes
the steady-state random walk probability as the limit of a weighted sum over
all possible lengths. In these cases, although the adjacency matrix is
typically sparse –in that it registers only first-order immediate neighbors–
higher-order connectivity matrices will often become dense and pose
representation challenges in term of the storage space required. We recall
that the inherent dimensionality of such representations based on connectivity
matrices would otherwise grow quadratically with the number of nodes in the
graph, which in practical data applications is often of the order of millions
or higher [34]. To that end, random projections consists of a promising
dimensionality reduction approach. In the context of representation learning,
the use of random projections to generate node embeddings for graphs was
introduced in [39] and further developed in [10], becoming a popular and fast
way to produce embeddings.

Previous work on random projections has focused predominantly on proposing
alternative random projection matrix constructions and seeking sparser
configurations (e.g., based on Rademacher random variables) [15, 20, 1]. Other
works have been dedicated to obtaining tighter bounds for the preservation of
Euclidean distance [32, 25]. In the case of the dot product as a similarity
metric, a relevant study has obtained general guarantees with depending on the
angle between the vectors [22]. Other similar studies have focused on the
preservation of margin for as a quantity of interest in the formulation of
support vector machines [31]. Additional contributions have been achieved in
the analysis of clustering [3, 11, 7].

In this paper, we provide an in-depth analysis of the behavior of three types
of similarities used in Random Projections for graphs: _(i)_ inner product
with adjacency matrices, _(ii)_ inner product with transition matrices, and
_(iii)_ cosine similarity. We propose a rotation argument based on the Gram-
Schmidt orthogonalization procedure to achieve novel asymptotic and finite-
sample results for Gaussian random projection matrices. We show that, in case
of inner-product similarity, the JL Lemma becomes _data dependent_.
Specifically, it yields weaker guarantees in the important case of
similarities between nodes of low and high degrees. Contrary to intuition,
such guarantees fail not only for the inner product with adjacency matrix, but
also for the transition matrix (i.e., where the input data is row-normalized).
Although occurring particularly between nodes of high and low degrees, such
fail modes can be crucial in practical applications due to the influential
roles high-degree nodes exert in their graphs.

The structure of this paper is as follows. In Section 2, we introduce three
versions of the JL Lemma used in our analysis. In Section 3, we translate our
results in terms of graphs and identify key issues in dot product similarity
for nodes having low or high degrees. In Section 4, we develop results for the
specific use of random projection in ranking, and illustrate its consequences
with a real graph dataset from Wikipedia. Finally, we provide an extensive
appendix with detailed proofs of our results.

##  2 Three versions of Johnson-Lindenstrauss Lemma

In this section, we will recall the original version of the JL Lemma for the
norm (and Euclidean distance), to then expand it and state new results for the
dot product and the cosine similarity.

In general, a random matrix $R=[R_{ij}]\in\mathbb{R}^{q\times n}$ is used,
where $(R_{ij}:i=1,\ldots,n,j=1,\ldots,d)$ are i.i.d. normal random variables
with mean zero and variance $1/q$. The sequence of vectors
$p_{1},\ldots,p_{k}$ in $\mathbb{R}^{n}$ is then mapped to vectors
$Rp_{1},\ldots,Rp_{k}$ in $\mathbb{R}^{q}$.

We will also include an asymptotic result which will give us a better
understanding of the limitations Johnson-Lindenstrauss type results provide.
To clarify the notation $Y_{q}\stackrel{{\scriptstyle
a}}{{\sim}}\mathcal{N}(\mu,\frac{\sigma^{2}}{q})$ means
$\frac{Y_{q}-\mu}{\sigma}\sqrt{q}\stackrel{{\scriptstyle
d}}{{\to}}\mathcal{N}(0,1)$ as $q\to\infty$. The "$\stackrel{{\scriptstyle
a}}{{\sim}}$" is interpreted as meaning an approximate distribution for large
$q$.

###  2.1 Preserving the norm

######  Proposition 2.1.

(a) For every $i,j$ we have $\|Rp_{j}-Rp_{i}\|^{2}\stackrel{{\scriptstyle
a}}{{\sim}}\mathcal{N}\left(\|p_{j}-p_{i}\|^{2},\frac{2}{q}\|p_{j}-p_{i}\|^{4}\right).$
(b) Let $\varepsilon,\delta\in(0,1)$, and $p_{1},\ldots,p_{k}$ be non-zero
vectors in $\mathbb{R}^{n}$. For

$q\geq\frac{4}{\varepsilon^{2}}\log\left[\frac{k^{2}}{\delta}\right]$ (1)

the inequality

$(1-\varepsilon)\|p_{i}-p_{j}\|^{2}\leq\|R(p_{i}-p_{j})\|^{2}\leq(1+\varepsilon)\|p_{i}-p_{j}\|^{2}$
(2)

holds for all $i<j$ with probability at least $1-\delta$.

###### Proof.

(a) follows from Corollary C.4. if we set $u=v=p_{1}-p_{2}$. (b) is the
statement of the original Johnson-Lindestrauss Lemma. (See statement of
Theorem D.16 and discussion before.) ∎

If $P=p(A)$ or $P=p(T)$, the differences of rows are preserved with an
$\varepsilon$-relative error with high probability:

$-\varepsilon\leq\frac{\|X_{v*}-X_{u*}\|^{2}}{\|P_{v*}-P_{u*}\|^{2}}-1=\frac{\|RP_{v*}^{t}-RP_{u*}^{t}\|^{2}}{\|P_{v*}-P_{u*}\|^{2}}-1\leq\varepsilon.$

This result has been used to justify $(X_{v*}:v\in V)$ as the embedding for
the graph. Note that, we only have a relative error guarantees here and it is
difficult to control and interpret the value of $\|P_{v*}-P_{u*}\|$.

###  2.2 Preserving the dot product

In many cases, as in the case of large graphs the dot product is a better and
a more interpretable quantity. Many papers (see [22]) calculate bounds of the
dot product using formulas of the type:
$(Ry,Rz)=\frac{1}{4}(\|Ry+Rz\|^{2}-\|Rz-Ry\|^{2})$ and Johnson-Lindenstrauss
Lemma bounds for

$\|R(y+z)\|,\,\|R(y-z)\|.$ (3)

Using the rotation argument as described in §B we improve these results (for
more on improvement see §C.5). Similar as in Proposition 2.1 we are also
providing an asymptotic result.

######  Proposition 2.2.

(a) For every $i,j$ we have

$(Rp_{i},Rp_{j})\stackrel{{\scriptstyle
a}}{{\sim}}\mathcal{N}\left((p_{i},p_{j}),\frac{1}{q}[\|p_{j}\|^{2}\|p_{i}\|^{2}+(p_{j},p_{i})^{2}]\right).$
(4)

(b) Let $\varepsilon\in(0,1)$ and $\delta\in(0,1)$, then for $q\geq
4\cdot\frac{1+\varepsilon}{\varepsilon^{2}}\log\frac{k(k-1)}{\delta}$ we have
that
$\left|(Rp_{j},Rp_{i})-(p_{j},p_{i})\right|<\varepsilon\|p_{j}\|\|p_{i}\|$ for
$i<j$ with probability at least $1-\delta$.

###### Proof.

(a) is the statement of Corollary C.4. (b) the statement of Theorem C.11. ∎

We can notice, for example if $p_{i}$ and $p_{j}$ are orthogonal or
$(p_{i},p_{j})$ is small the $\|p_{i}\|\|p_{j}\|$ can be a large real number.
Hence by just knowing the dot product we have very little control on the size
of the error in both parts (a) and (b) of Proposition 2.2. In case of large
networks it is difficult to control the norm of the rows in the matrix
$P=p(A)$, so practitioners often use $P=p(T)$. We will discuss in §3.1 and
§3.2 how this can lead to problems, precisely because of the inability to
control the variance in (4).

###  2.3 Preserving the cosine similarity

Cosine similarity of two $x$ and $y$ vectors given by
$\cos(x,y)=\frac{(x,y)}{\|x\|\|y\|},$ is also a popular quantity to measure
similarity. Although random projections have been studied extensively, there
are not many papers that include consideration of the cosine similarity.
Furthermore, the mathematical and theoretical statistics literature on cosine
similarity alone is extremely rare. For example, the MathSciNet one of the
leading indexing services for mathematical sciences found only 34 papers
related to cosine similarity.

The following is again a consequence of the rotation argument presented in §B.

######  Proposition 2.3.

(a) For all $i,j$ such that $p_{i}\neq 0$ and $p_{j}\neq 0$ we have:

$\cos(Rp_{i},Rp_{i})\stackrel{{\scriptstyle
a}}{{\sim}}\mathcal{N}\left(\cos(p_{i},p_{j}),\frac{1}{q}(1-\cos^{2}(p_{i},p_{j}))^{2}\right).$
(5)

(b) Let $\varepsilon\in(0,0.05]$, $\delta\in(0,1)$ and $p_{1},\ldots,p_{k}$ be
non-zero vectors in $\mathbb{R}^{n}$. For

$q\geq\frac{2\ln\left[\frac{2k(k-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{\delta}\right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]}$
(6)

the inequality
$\left|\cos(Rp_{j},Rp_{i})-\cos(p_{j},p_{i})\right|\leq\varepsilon(1-\cos(p_{j},p_{i})^{2})$
holds for all $i<j$ with probability at least $1-\delta$.

###### Proof.

(a) is the statement of Theorem D.5. (b) is a modified statement of Theorem
D.13. ∎

Note that Proposition 2.3 give us guarantees that error between the projected
value and original value is absolute. Additionally the closer
$|\cos(p_{j},p_{i})|$ is to 1 the error is smaller.

Regarding the dimension value in (6) and other comparisons with known results
the reader can find more in §D.5.

##  3 Random projections for graphs

In this section, we will translate our results to graph terminology and show
their implication on the quality of the embeddings produced by random
projections. In the case of large graphs $G=(V,E)$, Random Projections have
been applied to polynomials of the adjacency matrix $A$ and transition matrix
$T$. If $R$ is a random matrix generated in a specific way, then $X=p(A)R^{t}$
or $X=p(T)R^{t}$ preserve many of the properties $p(A)$ and $p(T)$, for a
matrix polynomial $p(X)=\sum_{j=1}^{l}\alpha_{j}X^{j}$.

An additional benefit is that $p(A)R^{t}$ and $p(T)R^{t}$ can be calculated
faster than $p(A)$ and $p(T)$. Things get even more useful in the case of
heterogeneous graphs, where we have polynomials of several variables
associated with the so-called metapaths [33].

For $P=p(A)$ or $P=p(T)$, the interpretation is that for $u,v\in V$
$\mathrm{rel}_{uv}:=P_{v*}P_{u*}^{t}$ is the relevance between $u$ and $v$,
then

$\mathrm{rel}^{R}_{uv}:=X_{v*}X_{u*}^{t}\approx P_{v*}P_{u*}^{t}.$ (7)

In this case, a vertex $v$ in the graph is represented by the embedding
$X_{v*}$. We refer to this method as RP DotProduct. Due to the noise in the
system we will show that for the large sparse graph the assumption (7) will
fail in two important cases:

  * •

In case of $P=A$ for a low degree node $v$, $X_{v*}X_{u*}$ will overvalue
$P_{v*}P_{u*}^{t}$ for many high degree nodes $u$.

  * •

In case of $P=T$ for a high degree node $u$, $X_{v*}X_{u*}$ will overvalue
$P_{u*}P_{v*}^{t}$ for many low degree nodes $v$.

In contrast to the above, we will show that

$\frac{X_{v*}X_{u*}^{t}}{\|X_{v*}\|\|X_{u*}\|}\approx\frac{P_{v*}P_{u*}^{t}}{\|P_{v*}\|\|P_{u*}\|}.$
(8)

holds more consistently. This is why we propose to use
$\frac{X_{v*}}{\|X_{v*}\|}$ as the embedding for a vertex $v$. We will call
this method RP CosSimilarity.

To develop our specific results, we begin by denoting, for all $u,v\in V$:

  * •

$d_{u}:=\sum_{w\in V}A_{uw}$, the _degree_ of the vertex $u$,

  * •

$n_{uv}:=A_{u*}A_{v*}^{t}$, the _2-hop connectivity_ between $u$ and $v$,
corresponding to the number of paths of length two between those vertices.

The following lemma provides basic information about $n_{uv}$.

######  Lemma 3.1.

The following statements hold:

  1. (a)

For all $u\in V$ we have

$d_{u}\leq n_{uu}\leq d_{u}^{2}.$ (9)

  2. (b)

For all $u,v\in V$ we have

$\frac{n_{uv}}{d_{u}d_{v}}=T_{u*}T_{v*}^{t}.$ (10)

###### Proof.

Since all entries of the matrix $A$ are nonnegative integers:
$n_{uu}=\sum_{w\in V}A_{uw}^{2}\geq\sum_{w\in V}A_{uw}=d_{u}$. On the other
hand,

$d_{u}^{2}=\left(\sum_{w\in V}A_{uw}\right)^{2}\geq\sum_{w\in
V}A_{uw}^{2}=A_{u*}A_{u*}^{t}=n_{uu}.$

Note, $T_{u*}=\frac{1}{d_{u}}A_{u*}$ for all $u\in V$. Hence,
$T_{u*}T_{v*}^{t}=\frac{A_{u*}A_{v*}^{t}}{d_{u}d_{v}}=\frac{n_{uv}}{d_{u}d_{v}}$.
This shows (a) and (b). ∎

Further, we note that $d_{u}$ has a linear dependence on the entries of $A$,
while $n_{u,v}$ has a quadratic one. Thus, in order to relate $d_{u}$ to
$n_{uv}$, we define the following graph-wide property:

$M:=\max_{u,v\in V}\frac{n_{uv}}{d_{v}}.$ (11)

This property will enable our results to generalize to weighted adjacency
matrices $A\in(\mathbb{Z}^{+}_{0})^{n\times n}$. In particular, we observe
that if $A\in\\{0,1\\}^{n\times n}$, then $M=1$. Further, $M\leq\max_{u,v\in
V}A_{u,v}.$

Next, we will define what does it mean for the node to be of _high_ or _low_
degree in the context of this paper. Let

$L_{c}:=\\{v\in V:d_{v}\leq c\\}.$ (12)

These will be called the nodes of low degree. In particular, for a graph
following a power law distribution, $L_{c}$ will contain the majority of the
nodes. Conversely, let

$H^{M}_{c}:=\\{u\in V\,:\,d_{u}\geq M^{2}cq\\}.$ (13)

We will call this set nodes of the high degree. We are interested analysing
graphs where $n=|V|$ is large using Johnson-Lindenstrauss type of results. For
that, we consider $q=\mathcal{O}(\log n)$. Under the assumption of the power
law distribution, we have $\frac{|H^{M}_{c}|}{n}\sim C[\log n]^{-\alpha}$ for
some $\alpha>0$. Hence, for large $n$, the set $H^{M}_{c}$ should have a
number of nodes on the order of $\mathcal{O}(n[\log n]^{-\alpha})$.

###  3.1 RP Dot Product when $P=A$

We will now apply results discussed in §2.2 to show that inner-product
similarity for $P=A$ will produce especially poor approximations for vertices
$u\in H^{M}_{c}$ and $v\in L_{c}$.

######  Theorem 3.2.

Let $X=AR^{t}$. Then, the following claims hold:
(a) Asymptotic result. For $u,v\in V$

$X_{u*}X_{v*}^{t}\stackrel{{\scriptstyle
a}}{{\sim}}\mathcal{N}\left(n_{uv},\frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}\right),$
(14)

(b) Finite-sample result. For $\varepsilon\in(0,1)$ and $\delta\in(0,1)$ if
$q\geq\frac{1+\varepsilon}{\varepsilon}\log\left[\frac{n(n-1)}{\delta}\right]$
then

$\max_{u,v\in
V}\frac{|X_{u*}X_{v*}^{t}-n_{uv}|}{\sqrt{n_{uu}n_{vv}}}<\varepsilon$ (15)

holds with probability at least $1-\delta$.

###### Proof.

Since $X_{u*}=A_{u*}R^{t}$ and $X_{v*}=A_{v*}R^{t}$, the claim (a) follows
from (4) and parts (a) and (b) of Lemma 3.1. Since $n=k=\|V\|$, claim (b)
follows from part (b) of Proposition 2.2. ∎

Let us fix $v\in L_{c}$ and look at the set $\\{X_{u*}X_{v*}^{t}\,:\,u\in
H_{c}\\}$. We will show that these calculations can severely overvalue (or
undervalue) the relevance values $\\{A_{u*}A_{v*}^{t}\,:\,u\in H_{c}\\}$ they
approximate. This will be a consequence of the two following lemmas.

######  Lemma 3.3.

If $v\in L_{c}$ and $u\in H^{M}_{c}$, then the standard deviation in (14) is
greater than $Md_{v}$, i.e.:

$Md_{v}\leq\sqrt{\frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}}$ (16)

###### Proof.

We have

$\frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}\stackrel{{\scriptstyle\eqref{eq:degreeAT}}}{{\geq}}\frac{d_{u}d_{v}+n_{uv}^{2}}{q}\stackrel{{\scriptstyle
u\in H_{c}}}{{\geq}}\frac{M^{2}cqd_{v}+n_{uv}^{2}}{q}\geq
M^{2}cd_{v}\stackrel{{\scriptstyle v\in L_{c}}}{{\geq}}(Md_{v})^{2}.$

∎

######  Lemma 3.4.

If $v\in L_{c}$ such and $u\in H_{c}$, the standard deviation in
$\eqref{eq:dotANormalityPA}$ is greater than its expectation, i.e.:

$n_{uv}\leq\sqrt{\frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}}.$ (17)

###### Proof.

We have

$\sqrt{\frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}}\stackrel{{\scriptstyle\eqref{eq:STDGeDegree}}}{{\geq}}Md_{v}\stackrel{{\scriptstyle\eqref{eq:MConnection}}}{{\geq}}n_{uv}.$

∎

Using Lemmas 3.3 and 3.4, we can produce the one-sigma confidence interval

$[n_{uv}-Md_{v},n_{uv}+Md_{v}]$

in which we can expect $X_{u*}X_{v*}^{t}$ to take values with less than $69\%$
probability. This means that getting a value outside that interval is not
unlikely. In that case, from (11), we know such values will more than double
$n_{uv}$ or be less than $0$, a poor approximation. On the other hand, if we
look at the values $(X_{w*}X_{v*}^{t}\,:\,w\in L_{c})$, we can see that the
variance in (14) is bounded as

$\frac{n_{ww}n_{vv}+n_{wv}^{2}}{q}\stackrel{{\scriptstyle\eqref{eq:degreeAT}}}{{\leq}}\frac{d_{w}^{2}d_{v}^{2}+d_{w}^{2}d_{v}^{2}}{q}\stackrel{{\scriptstyle
w,v\in L_{c}}}{{\leq}}c^{4}\frac{2}{q}.$

Hence, in this case we can produce the three-sigma interval

$\left[n_{wv}-3c^{2}\sqrt{\frac{2}{q}},n_{wv}+3c^{2}\sqrt{\frac{2}{q}}\right],$

where $X_{w*}X_{v*}^{t}$ will take values with more than $99\%$ probability,
which is a small deviation.

Further, setting the random projection dimension $q$ according to (2.2), i.e.,

$q=\left\lceil\frac{1+\varepsilon}{\varepsilon}\log\left[\frac{n(n-1)}{\delta}\right]\right\rceil,$

we fulfill the finite-sample result in part (b) of Theorem 3.2. However, for
large values of $\sqrt{n_{uu}n_{vv}}$ (c.f., the denominator of 15), we note
that the bounds in (15) become looser, thus larger approximation errors ensue.
This will happen for vertices $u\in H^{M}_{c}$, since $n_{uu}\geq d_{u}$. As a
simple numerical illustration, assume $A\in\\{0,1\\}^{n\times n}$ such that
$n_{uu}=d_{u}$ and $n_{vv}=d_{v}$. Let $\varepsilon=10^{-2}$ , $d_{u}=10^{7}$,
$d_{v}=10$ and $n_{uv}=1$. Then, (15) yields
$X_{u*}X_{v*}^{t}\in(1-100,1+100)$.

###  3.2 RP Dot Product when $P=T$

To avoid problems arising from higher degree nodes or higher powers of $A$,
practitioners often consider the transition matrix $T$, since it consists of a
normalized version of $A$. We will show that even in this case (and similarly
to the previous section), random projections may yield especially poor
approximations for vertices $u\in H^{M}_{c}$ and $v\in L_{c}$.

######  Theorem 3.5.

Let $X=TR^{t}$. The following statements hold:
(a) Asymptotic result. For $u,v\in V$

$X_{u*}X_{v*}^{t}\stackrel{{\scriptstyle
a}}{{\sim}}\mathcal{N}\left(\frac{n_{uv}}{d_{u}d_{v}},\frac{1}{q}\left[\frac{n_{uu}n_{vv}}{d_{u}^{2}d_{v}^{2}}+\left(\frac{n_{uv}}{d_{u}d_{v}}\right)^{2}\right]\right),$
(18)

(b) Finite sample result. For $\varepsilon\in(0,1)$ and $\delta\in(0,1)$, if
$q\geq\frac{1+\varepsilon}{\varepsilon}\log\left[\frac{n(n-1)}{\delta}\right]$,
then

$\max_{u,v\in
V}\frac{|X_{u*}X_{v*}^{t}-\frac{n_{uv}}{d_{u}d_{v}}|}{\frac{\sqrt{n_{uu}n_{vv}}}{d_{u}d_{v}}}<\varepsilon$
(19)

holds with probability at least $1-\delta$.

###### Proof.

Since $X_{u*}=T_{u*}R^{t}$ and $X_{v*}=T_{v*}R^{t}$, claim (a) follows from
(4) and parts (a) and (b) of Lemma 3.1. Since $n=k=|V|$, claim (b) follows
from part (b) of Proposition 2.2. ∎

Similarly to §3.1, we will fix $u\in H_{c}$ and look at the values
$\\{X_{u*}X_{v*}^{t}\,:\,v\in L_{c}\\}$ that may misapproximate
$\\{\frac{n_{uv}}{d_{u}d_{v}}:v\in L_{c}\\}$.

######  Lemma 3.6.

  1. (a)

For $u,v\in V$ and $v$ satisfying (11) we have

$\frac{n_{uv}}{d_{u}d_{v}}\leq\frac{M}{d_{u}},$ (20)

and

$\frac{\sqrt{n_{vv}}}{d_{v}}\frac{1}{\sqrt{d_{u}}}\leq\frac{\sqrt{n_{uu}n_{vv}}}{d_{u}d_{v}}\leq\sqrt{\frac{M}{d_{v}}}\frac{1}{\sqrt{d_{u}}}.$
(21)

  2. (b)

For $u\in H^{M}_{c}$ and $v\in L_{c}$ we have

$\frac{M}{d_{u}}\leq\sqrt{\frac{1}{q}\left[\frac{n_{uu}n_{vv}}{d_{u}^{2}d_{v}^{2}}+\left(\frac{n_{u,v}}{d_{u}d_{v}}\right)^{2}\right]}.$

###### Proof.

For (20), we multiply the inequality (11) with $(d_{u})^{-1}$. Similarly, (b)
follows from (16) by multiplying this inequality with $(d_{u}d_{v})^{-1}$. We
have
$d_{v}\stackrel{{\scriptstyle\eqref{eq:degreeAT}}}{{\leq}}n_{vv}\stackrel{{\scriptstyle\eqref{eq:MConnection}}}{{\leq}}Md_{v}$.
Multiplying the last inequality by $\frac{n_{uu}}{d_{u}d_{v}}$ and taking
square roots the claim (21) follows. ∎

######  Corollary 3.7.

If $v\in L_{c}$ such that $v$ satisfies (11) and $u\in H^{M}_{c}$, then the
standard deviation in (18) is greater than its expectation, i.e.,

$\frac{n_{uv}}{d_{u}d_{v}}\leq\sqrt{\frac{1}{q}\left[\frac{n_{uu}n_{vv}}{d_{u}^{2}d_{v}^{2}}+\left(\frac{n_{u,v}}{d_{u}d_{v}}\right)^{2}\right]}.$
(22)

###### Proof.

From Lemma (3.6) we have (22) and the claim follows. ∎

Hence, if (11) is satisfied for all $v\in V$, when can generate the one-sigma
interval

$\left[\frac{n_{uv}}{d_{u}d_{v}}-\frac{M}{d_{u}},\frac{n_{uv}}{d_{u}d_{v}}+\frac{M}{d_{u}}\right],$

in which $(X_{u*}X_{v*}^{t}\,:\,v\in L_{c})$ will take values with probability
of less than $69\%$. This means that getting a value outside that interval is
not unlikely. In that case, similarly to §3.1, we know from (11) that such
values will either double $\frac{n_{uv}}{d_{u}d_{v}}$ or be less than $0$, a
poor approximation.

As in §3.1, we set
$q=\left\lceil\frac{1+\varepsilon}{\varepsilon}\log\left[\frac{n(n-1)}{\delta}\right]\right\rceil$
such that part (b) of Theorem 3.5 holds. We note that
$\frac{n_{uv}}{d_{u}d_{v}}$ in the numerator of (19) depends on $d_{u}$ with
order $(d_{u})^{-1}$, as can be seen from (20). Conversely, its denominator
has a lower-order dependence $(d_{u})^{-\frac{1}{2}}$, as can be seen from
(21). Thus, higher values of $d_{u}$ lead to an unfavorable regime in which
the guarantees from Theorem 3.5 become increasingly weaker. As a simple
numerical illustration, we assume $A\in\\{0,1\\}^{n\times n}$ so that
$n_{uu}=d_{u}$ and $n_{vv}=d_{v}$, and let $\varepsilon=10^{-2}$ ,
$d_{u}=10^{7}$, $d_{v}=10$ and $n_{uv}=1$. Then, (19) yields
$X_{u*}X_{v*}^{t}\in 10^{-8}(1-100,1+100)$.

###  3.3 RP Cosine Similarity

In this section, we build on our analysis of cosine similarity under random
projections introduced in §2.3 and §B. We show how its asymptotic and finite-
sample behaviors yield, for vertices $u\in H^{M}_{c}$ and $v\in L_{c}$,
significantly better approximations than those of RP Dot Product when $P=A$
and when $P=T$. We begin by showing that it will not matter for RP Cosine
Similarity if we take $P=A$ or $P=T$.

######  Lemma 3.8.

For all $u,v\in V$ we have

$\cos(T_{u*}R^{t},T_{v*}R^{t})=\cos(A_{u*}R^{t},A_{v*}R^{t})\quad\textrm{and}\quad\cos(T_{u*},T_{v*})=\cos(A_{u*},A_{v*})=\frac{n_{uv}}{\sqrt{n_{uu}n_{vv}}}.$

###### Proof.

First equality follows from

$\frac{T_{u*}RR^{t}T_{v*}^{t}}{\|T_{u*}R^{t}\|\|T_{v*}R^{t}\|}=\frac{(d_{u}^{-1}A_{u*})R^{t}R(d_{v}^{-1}A_{v*}^{t})}{\|d_{u}^{-1}A_{u*}R^{t}\|\|d_{v}^{-1}A_{v*}R^{t}\|}=\frac{A_{u*}R^{t}RA_{v*}^{t}}{\|A_{u*}R\|\|A_{v*}R\|}$

Using parts (a) and (b) of Lemma 3.1 we can calculate that
$\cos(A_{u*},A_{v*})=\frac{n_{uv}}{\sqrt{n_{uu}n_{vv}}}$ and
$\cos(T_{u*},T_{v*})=\frac{n_{uv}}{\sqrt{n_{uu}n_{vv}}}$. ∎

We will state our main result for this method now.

######  Theorem 3.9.

For $X=PR^{t}$ the following claims hold:
(a) Asymptotic result. For $u,v\in V$

$\cos(X_{u*},X_{v*})\sim\mathcal{N}\left(\frac{n_{uv}}{\sqrt{n_{uu}n_{vv}}},\frac{1}{q}\left(1-\frac{n_{uv}^{2}}{n_{uu}n_{vv}}\right)^{2}\right)$
(23)

(b) Finite-sample result. Let $\varepsilon\in(0,0.05]$ and $\delta\in(0,1)$.
If

$q\geq\frac{2\ln\left[\frac{2n(n-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{\delta}\right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]}.$

then

$\left|\cos(X_{u*},X_{v*})-\frac{n_{uv}}{\sqrt{n_{uu}n_{vv}}}\right|\leq\varepsilon\left(1-\frac{n_{uv}^{2}}{n_{uu}n_{vv}}\right)$

holds for all $u,v\in V$ with probability at least $1-\delta$.

###### Proof.

Claim (a) follows from Lemma 3.8 and part (a) of Proposition 2.3. Claim (b)
follows from Lemma 3.8 and setting $k=n=|V|$ in part (b) of Proposition 2.3. ∎

Let us compare the asymptotic result for cosine similarity with the previous
cases. From (23), we can produce a three-sigma interval

$\left[\cos(P_{u*},P_{v*})-\frac{3}{\sqrt{q}}(1-\cos^{2}(P_{u*},P_{v*})),\right.\left.\cos(P_{u*},P_{v*})+\frac{3}{\sqrt{q}}(1-\cos^{2}(P_{u*},P_{v*}))\right]$

where $\cos(X_{u*},X_{v*})$ is expected to take values with $99\%$
probability. Differently from the previous cases, we see that the interval
endpoints do not depend on the node degrees. Thus, for a reasonably large $q$,
the value of $\cos(P_{u*},P_{v*})$ will be well approximated. Further, the
closer $\cos(P_{u*},P_{v*})$ is to 1, the smaller the standard deviation, and
the narrower the confidence interval. The confidence interval is the widest
when $\cos(P_{u*},P_{v*})=0$ and in that case it can happen that it takes
negative values under random projections, but this is likely not to be lower
than $-\frac{3}{\sqrt{q}}$.

With Theorem 3.9, we can state the following additional properties.

######  Proposition 3.10.

  1. (a)

$\cos(X_{u*},X_{v*})\in[-1,1]$ for all $u,v\in V$.

  2. (b)

Almost surely $\cos(X_{u*},X_{v*})=\pm 1$ if and only if
$\cos(P_{u*},P_{v*})=\pm 1$.

  3. (c)

For $\varepsilon\in(0,0.05]$ and $\delta\in(0,1)$, if

$q\geq\frac{2\ln\left[\frac{2n(n-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{\delta}\right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]},$

then

$\cos(X_{u*},X_{v*})\in[\cos(P_{u*},P_{v*})-\varepsilon,\cos(P_{u*},P_{v*})+\varepsilon]$

for all $u,v\in V$ with probability $1-\delta$.

###### Proof.

Part (a) follows by definition of cosine similarity. Part (b) is the statement
of Corollary D.2. Part (c) follows from Theorem 3.9 part (b) since

$0\leq 1-\frac{n_{uv}^{2}}{n_{uu}n_{vv}}=1-\cos^{2}(P_{u*},P_{v*})\leq 1.$

∎

Part (b) of Proposition 3.10 tells us that random projection will preserve
values of exactly 1. Part (c) Proposition 3.10 provides the desired property
of _uniformity_ for the absolute error on the difference between the estimate
and the true value with respect to node degrees.

##  4 Application to ranking

Here, we specialize the results presented in the Section 3 to a ranking
application. We will see that the three aforementioned forms of approximating
relevance with random projections can lead to unexpected outcomes.

Recall that, for polynomials $P=p(A)$ or $P=p(T)$, the interpretation is that
for $u,v\in V$

$\mathrm{rel}_{uv}:=P_{v*}P_{u*}^{t}.$

For computational reasons, we apply the random projection $X=PR^{t}$ and work
with

$\mathrm{rel}^{R}_{uv}:=X_{v*}X_{u*}^{t},$ (24)

under the assumption that $\mathrm{rel}_{uv}^{R}\approx\mathrm{rel}_{uv}$.

We will next examine what happens if we fix $w\in V$ and use the approximate
$(\mathrm{rel}^{R}_{wh}~{}:~{}h\in V)$ for ranking. For this, we will use the
well-known NDCG
metric:$\mathrm{NDCG}_{w}@l:=\frac{\mathrm{DCG}^{R}_{w}@l}{\mathrm{DCG}_{w}@l}$
where

$\mathrm{DCG}^{R}_{w}@l:=\sum_{h:\mathrm{rank}_{w}^{R}(h)\leq
l}\frac{\mathrm{rel}_{wh}}{\log(\mathrm{rank}_{w}^{R}(h)+1)}\ \,\textrm{and}\
\,\mathrm{DCG}_{w}@l:=\sum_{h:\mathrm{rank}_{w}(h)\leq
l}\frac{\mathrm{rel}_{wh}}{\log(\mathrm{rank}_{w}(h)+1)}.$

The following Theorem will help us quantify how often can the approximation
$(\mathrm{rel}^{R}_{wh}$ flip the order of relevance between nodes $u$ and $v$
with respect to $w$.

######  Theorem 4.1.

Let $u,v\in V$ be such that $\mathrm{rel}_{wu}>\mathrm{rel}_{wv}$. Then,

$\mathbb{P}(\mathrm{rel}_{wu}^{R}<\mathrm{rel}_{wv}^{R})=\mathbb{P}\left(\mathcal{T}_{q}>\frac{\cos(P_{w*},P_{u*}-P_{v*})\sqrt{q}}{\sqrt{1-\cos^{2}(P_{w*},P_{u*}-P_{v*})}}\right)$
(25)

where $\mathcal{T}_{q}$ is the $t$-distribution with parameter $q$.

###### Proof.

From the assumption, we have that $(P_{w*},P_{u*}-P_{v*})>0$. Hence, using
Proposition C.1 the claim follows. ∎

The following lemma will help us in our considerations.

######  Lemma 4.2.

If $x$ and $y$ are orthogonal vectors in $\mathbb{R}^{n}$, we have

$\frac{\cos(x,x-y)}{\sqrt{1-\cos^{2}(x,x-y)}}\\\ =\frac{\|x\|}{\|y\|}.$ (26)

###### Proof.

Using $(x,y)=0$, we have

$\cos(x,x-y)=\frac{(x,x-y)}{\|x\|\|x-y\|}=\frac{\|x\|^{2}}{\|x\|\sqrt{\|x\|^{2}+\|y\|^{2}}}=\frac{\|x\|}{\sqrt{\|x\|^{2}+\|y\|^{2}}}.$

Now, it is not difficult to show
$\sqrt{1-\cos^{2}(x,x-y)}=\frac{\|y\|}{\sqrt{\|x\|^{2}+\|y\|^{2}}}$. Hence,
(26) follows.∎

###  4.1 Instability of Ranking for DotProduct with $P=A$

Let $w=v\in L_{c}$. The relevance value will have a bound.

######  Proposition 4.3.

For all $u\in V$:

$\mathrm{rel}_{vu}=n_{vu}\leq Md_{v}.$ (27)

###### Proof.

The result follows from definition of $n_{uv}$ and (11). ∎

For a node of low degree, the relevance has to be low. However, this might not
be the case for their approximation.

######  Corollary 4.4.

For $v\in L_{c}$ and $u\in H_{c}^{M}$, we have
$\mathrm{rel}_{vv}^{R}\stackrel{{\scriptstyle
a}}{{\sim}}\mathcal{N}\left(n_{vv},\frac{2n_{vv}^{2}}{q}\right)$ and
$\mathrm{rel}_{vu}^{R}$ will have a nonnegative expectation with the standard
deviation greater than $Md_{v}$.

###### Proof.

Follows from Theorem 3.2 and Lemma 3.3 ∎

The last result tells us that $\mathrm{rel}_{vv}^{R}$ will have values in

$\left[n_{vv}\left(1-3\sqrt{\frac{2}{q}}\right),n_{vv}\left(1+3\sqrt{\frac{2}{q}}\right)\right]$

with more than 99%. This means, for example if $q\geq 100$,
$r_{vu}^{R}\in[1.5Md_{v},\infty)\subset\left[n_{vv}\left(1+3\sqrt{\frac{2}{q}}\right),\infty\right)$
can happen with probability $\mathbb{P}(\mathcal{N}(0,1)>1.5)\approx 6.7\%$.
For higher $q$, this probability will be higher. Roughly, we can anticipate
that $\mathrm{rel}_{v}v^{R}<\mathrm{rel}_{vu}^{R}$ when
$\mathrm{rel}_{v}v>\mathrm{rel}_{vu}$ happens more frequently.

The following result will show that this can happen more often than we want.

######  Corollary 4.5.

Let $v\in L_{c}$ and $u\in H_{c}^{M}$ be two vertices with no common
neighbors, i.e. such that $\mathrm{rel}_{vv}>0$ and $\mathrm{rel}_{vu}=0$.
Then

$\mathbb{P}(\mathrm{rel}_{vv}^{R}<\mathrm{rel}_{vu}^{R})>\mathbb{P}(\mathcal{T}_{q}>1)\approx
15.8\%.$

######  Remark 4.6.

The previous estimate is based on the fact that for $q\geq 30$, in practice,
$\mathcal{N}(0,1)$ is taken as an approximation for $\mathcal{T}_{q}$.

###### Proof.

Since $P_{v*}P_{u*}^{t}=0$, we have, by (26),

$\frac{\cos(P_{w*},P_{u*}-P_{v*})}{\sqrt{1-\cos^{2}(P_{w*},P_{u*}-P_{v*})}}=\frac{\|P_{v*}\|}{\|P_{u*}\|}.$

Hence, Theorem 4.1 gives us

$\mathbb{P}(\mathrm{rel}_{vv}^{R}<\mathrm{rel}_{vu}^{R})=\mathbb{P}\left(\mathcal{T}_{q}>\frac{\|P_{v*}\|}{\|P_{u*}\|}\sqrt{q}\right).$
(28)

Further,

$\frac{\|P_{v*}\|}{\|P_{u*}\|}\sqrt{q}=\sqrt{\frac{n_{vv}q}{n_{uu}}}\stackrel{{\scriptstyle\eqref{eq:MConnection}}}{{\leq}}\sqrt{\frac{Md_{v}q}{n_{uu}}}\stackrel{{\scriptstyle
v\in
L_{c}}}{{\leq}}\sqrt{\frac{Mcq}{n_{uu}}}\stackrel{{\scriptstyle\eqref{eq:degreeAT}}}{{\leq}}\sqrt{\frac{Mcq}{d_{u}}}\stackrel{{\scriptstyle
u\in H_{c}^{M}}}{{\leq}}1.$

From the last estimate we have
$\mathbb{P}\left(\mathcal{T}_{q}>\frac{\|P_{v*}\|}{\|P_{u*}\|}\sqrt{q}\right)\geq\mathbb{P}\left(\mathcal{T}_{q}>1\right)$
and the claim follows from (28). ∎

Similar results would follow if we took two vertices $w,v$ of low degree with
many common neighbors and a high degree vertex $u$ that has no common
neighbors with $w$ and $v$. For simpler calculations, we took $w=v$.

###  4.2 Instability of Ranking for DotProduct with For $P=T$

Let $w=u\in H_{c}^{M}$. The relevance value will have a bound.

######  Proposition 4.7.

For all $v\in V$:

$\mathrm{rel}_{uv}=\frac{n_{uv}}{d_{u}d_{v}}\leq\frac{M}{d_{u}}$ (29)

###### Proof.

The result follows from (10) and Lemma 3.6 (a). ∎

Note that the value on the right in (29) can be particularly small for a high
degree $d_{u}$. However, the estimate might be larger than that.

######  Corollary 4.8.

For $u\in H_{c}^{M}$ and $v\in L_{c}$ we have
$\mathrm{rel}_{uu}^{R}\stackrel{{\scriptstyle
a}}{{\sim}}\mathcal{N}\left(\frac{n_{uu}}{d_{u}^{2}},\frac{2n_{uu}^{2}}{d_{u}^{4}q}\right)$
and $\mathrm{rel}_{uv}^{R}$ will have a nonnegative expectation with the
standard deviation greater than $\frac{M}{d_{u}}$.

###### Proof.

Follows from Theorem 3.5 and Lemma 3.6 (b). ∎

The last result tells us that $\mathrm{rel}_{uu}^{R}$ will have values in

$\left[\frac{n_{uu}}{d_{u}^{2}}\left(1-3\sqrt{\frac{2}{q}}\right),\frac{n_{uu}}{d_{u}^{2}}\left(1+3\sqrt{\frac{2}{q}}\right)\right]$

with more than 99%. This means, for example if $q\geq 100$,
$r_{uu}^{R}\in[1.5\frac{M}{d_{u}},\infty)\subset\left[\frac{n_{uu}}{d_{u}^{2}}\left(1+3\sqrt{\frac{2}{q}}\right),\infty\right)$
can happen with probability $\mathbb{P}(\mathcal{N}(0,1)>1.5)\approx 6.7\%$.

For higher $q$, this probability will be higher. Roughly, we can anticipate
that $\mathrm{rel}_{uu}^{R}<\mathrm{rel}_{uv}^{R}$ happens when
$\mathrm{rel}_{uu}>\mathrm{rel}_{uv}$ frequently. The following result will
show that this can happen more often than we want.

######  Corollary 4.9.

Let $u\in H_{c}^{M}$ and $v\in L_{c}$ be two vertices with no common
neighbors, i.e. such that $\mathrm{rel}_{uu}>0$ and $\mathrm{rel}_{uv}=0$.
Then

$\mathbb{P}(\mathrm{rel}_{uu}^{R}<\mathrm{rel}_{uv}^{R})>\mathbb{P}(\mathcal{T}_{q}>1)\approx
15.8\%.$

###### Proof.

Since $P_{u*}P_{v*}^{t}=0$, using the same arguments as in (28) we get

$\mathbb{P}(\mathrm{rel}_{uu}^{R}<\mathrm{rel}_{uv}^{R})=\mathbb{P}\left(\mathcal{T}_{q}>\frac{\|P_{u*}\|}{\|P_{v*}\|}\sqrt{q}\right).$
(30)

Further,

$\displaystyle\frac{\|P_{u*}\|}{\|P_{v*}\|}\sqrt{q}$
$\displaystyle=\frac{\sqrt{n_{uu}/d_{u}^{2}}}{\sqrt{n_{vv}/d_{v}^{2}}}\sqrt{p}=\frac{d_{v}\sqrt{n_{uu}}}{d_{u}\sqrt{n_{vv}}}\sqrt{q}\stackrel{{\scriptstyle\eqref{eq:degreeAT}}}{{\leq}}\frac{d_{v}\sqrt{n_{uu}}}{d_{u}\sqrt{d_{v}}}\sqrt{q}=\frac{\sqrt{d_{v}n_{uu}q}}{d_{u}}\stackrel{{\scriptstyle\eqref{eq:MConnection}}}{{\leq}}\frac{\sqrt{d_{v}Md_{u}q}}{d_{u}}$
$\displaystyle=\sqrt{\frac{d_{v}Mq}{d_{u}}}$
$\displaystyle\stackrel{{\scriptstyle v\in
L_{c}}}{{\leq}}\sqrt{\frac{Mcq}{d_{u}}}\stackrel{{\scriptstyle u\in
H_{c}^{M}}}{{\leq}}1.$

From the last estimate we have
$\mathbb{P}\left(\mathcal{T}_{q}>\frac{\|P_{v*}\|}{\|P_{u*}\|}\sqrt{q}\right)\geq\mathbb{P}\left(\mathcal{T}_{q}>1\right)$
and the claim follows from (30) and Remark 4.6. ∎

Similar results would follow if we took two vertices $w,u$ of high degree with
many common neighbors and a low degree vertex $v$ that has no common neighbors
with $w$ and $u$. For simpler calculations, we took $w=u$.

###  4.3 Stability of Ranking for Cosine similarity when $P=A$ or $P=T$

In both cases for the dot product, with respect to a given node, when using
random projection for relevance estimation, a node of low relevance can be
estimated with higher relevance than the node of low relevance. We will show
that with cosine similarity this is less likely to happen.

In the case of cosine similarity, for relevance we use
$\mathrm{rel}_{uv}=\cos(P_{u*},P_{v*})$ and
$\mathrm{rel}^{R}_{uv}=\cos(X_{u*},X_{v*})$. From Proposition 3.10, the next
result follows.

######  Proposition 4.10.

For all $u\in V$ $\mathrm{rel}_{uu}=\mathrm{rel}_{uu}^{R}=1$. Further, both
the relevance $(\mathrm{rel}_{uv}:u,v\in V)$ and the approximation
$(\mathrm{rel}^{R}_{uv}:u,v\in V)$ can be at most $1$.

This gives us a clear interpretation of the relevance: a value of $1$ implies
a strong connection between node, and one that is is preserved; a value of $0$
implies no neighbor overlap.

######  Corollary 4.11.

For $u,v,w,h\in V$, the following holds.

  1. (a)

If $r_{uv}=0$, then $\mathrm{rel}_{uu}=1>0=r_{uv}$ and
$\mathrm{rel}^{R}_{uu}>\mathrm{rel}^{R}_{uv}$ almost surely.

  2. (b)

Under the conditions of Proposition 3.10, if
$\mathrm{rel}_{uv}-\mathrm{rel}_{wh}>2\varepsilon$, then
$\mathbb{P}(\mathrm{rel}^{R}_{uv}>\mathrm{rel}^{R}_{wh})\geq 1-\delta$.

###### Proof.

(a) From Proposition 4.10 we have $\mathrm{rel}_{uu}=\mathrm{rel}^{R}_{uu}=1$.
Since $\mathrm{rel}^{R}_{uv}$ is a continuous random variable,
$\mathbb{P}(\mathrm{rel}^{R}_{uv}=1)=0$. Hence,

$1=\mathbb{P}(\mathrm{rel}^{R}_{uv}\leq
1)=\mathbb{P}(\mathrm{rel}^{R}_{uv}<1)+\mathbb{P}(\mathrm{rel}^{R}_{uv}=1)=\mathbb{P}(\mathrm{rel}^{R}_{uv}<1)+0=\mathbb{P}(\mathrm{rel}^{R}_{uv}<1).$

(b) With probability $1-\delta$, we have
$\mathrm{rel}^{R}_{uv}>\mathrm{rel}_{uv}-\varepsilon$ and
$\mathrm{rel}_{wh}+\varepsilon>\mathrm{rel}^{R}_{wh}$. Therefore,
$\mathrm{rel}^{R}_{uv}>\mathrm{rel}_{uv}-\varepsilon>(\mathrm{rel}_{wh}+2\varepsilon)-\varepsilon\mathrm{rel}_{wh}+\varepsilon>\mathrm{rel}^{R}_{wh}$.
∎

Part (a) of Corollary 4.11 shows that the phenomenon from Corollaries 4.5 and
4.9 does not happen in the case of cosine similarity. Part (b) of Corollary
4.11 shows stability, i.e., if two relevance values are not close, their
estimate will highly likely keep their order. Part (a) of Theorem 3.9 provides
similar asymptotic guarantees for stability.

The computational experiments in the next section will show, using real
graphs, that the standard measure for ranking NDCG will depend on node degrees
in the case of the dot product for both $P=A$ and $P=T$, while it will be
stable in case of the cosine similarity.

###  4.4 Computational Experiments

Figure 1: Distribution of
$\eta_{i}:=\mathrm{NDCG}(r_{i}^{K},\hat{r}_{i}^{K}),K=10,$ versus node degree
$d_{i}$. We consider RP Dot Product when $P=A$, denoted $\eta_{i}^{A}$, and RP
Cosine Similarity, denoted $\eta_{i}^{C}$, both with random projection
dimension $p=256$. The dotted line marks the lowest value observed for
$\eta_{i}^{C}$, of approximately 0.7. It can be seen that $\eta_{i}^{A}$ often
takes low values for lower degrees (region below dotted line), especially when
$\log_{2}(d_{i})\leq 6$. Figure 2: Distribution of
$\eta_{i}:=\mathrm{NDCG}(r_{i}^{K},\hat{r}_{i}^{K}),K=10,$ versus node degree
$d_{i}$. We consider RP Dot Product when $P=T$, denoted $\eta_{i}^{T}$, and RP
Cosine Similarity, denoted $\eta_{i}^{C}$, both with random projection
dimension $p=256$. The dotted line marks the lowest value observed for
$\eta_{i}^{C}$, of approximately 0.7. In contrast, it can be seen that
$\eta_{i}^{T}$ often takes low values for higher degrees (region below dotted
line), especially when $\log_{2}(d_{i})\geq 4$.

We illustrate the results developed in the previous section for a ranking
application over a real graph. We consider the Gleich/wikipedia-20060925
dataset111 https://www.cise.ufl.edu/research/sparse/
matrices/Gleich/wikipedia-20060925.html from the University of Florida Sparse
Matrix Collection [13]. It consists of a web crawling extraction of Wikipedia
with $2,983,494$ vertices (web pages) and $37,269,096$ edges (web links),
wherein $A(i,j)=1$ if page $i$ links to page $j$, and $0$ otherwise.

We wish to evaluate the effect of $R$ on the ranking of nodes induced by their
connectivity through common neighbors. The original relevance between nodes
$u$ and $v$, denoted $\mathrm{rel}_{u,v}$, is computed as a function of
vectors $P_{u},P_{v}\in\mathbb{R}^{n}$ obtained from their respective rows of
$A$ (or $T$). We denote the approximated relevance obtained through $R$ as
$\mathrm{rel}^{R}_{u,v}$, and consider the three variants of similarity
discussed in this paper: _(i)_ RP Dot Product when $P=A$, _(ii)_ RP Dot
Product when $P=T$, and _(iii)_ RP Cosine Similarity.

To compare the rankings induced the original and approximated relevances, we
proceed as follows. For a node $i$, we define a ranking vector
$r_{i}^{K}:=\left[\mathrm{rel}_{i,(\ell)}:\ell=1,\ldots,K\right]$, where the
parenthesized index $\ell$ denotes the $\ell$-th largest element according to
the relative order induced by the relevances. Likewise, we set
$\hat{r}_{i}^{K}:=\left[\mathrm{rel}^{R}_{i,(\ell)}:\ell=1,\ldots,K\right]$ to
consider the ranking from the approximated relevances. Then, we compare
$r_{i}^{K}$ with $\hat{r}_{i}^{K}$ by computing their normalized discounted
cumulative gain at $K=10$, which we define as
$\eta_{i}:=\mathrm{NDCG}(r_{i}^{K},\hat{r}_{i}^{K})$.

Because the number of possible pairwise node combinations is large, we
evaluate a representative sample of the nodes using a stratified sampling
strategy. To assure a meaningful mixture of node degrees, we split the set of
nodes into three segments of size $L=1\times 10^{6}$ (low, medium, and high)
based on their ordered degrees. Then, we select nodes into three subsets by
sampling $m=300$ out of $L$ nodes without replacement from each of these
segments, and take $\mathcal{S}$ =
$\mathcal{S}_{\mathrm{low}}\cup\mathcal{S}_{\mathrm{med}}\cup\mathcal{S}_{\mathrm{high}}$
as our evaluation sample. Finally, for each node $i$ in $S$ (and with respect
to every other node $j$ in $S$), we compute $\eta_{i}^{A}$, $\eta_{i}^{T}$,
and $\eta_{i}^{C}$ considering the three types of similarity defined
previously.

With the previous definitions, we can compute the empirical distributions of
$\eta_{i}$ over the node degrees $d_{i}$ for the three variants of similarity
considered, with $p=256$ for the random projection dimension.

In Figure 1, we compare RP Dot Product when $P=A$ with RP Cosine Similarity.
As expected (c.f., §4.1), we can see a strong disruption of NDCG for RP Dot
Product when $P=A$ when the degrees are low.

In Figure 2, we compare RP Dot Product when $P=T$ with RP Cosine Similarity.
As expected (c.f., §4.2), we can see a strong disruption of NDCG for RP Dot
Product when $P=A$ when the degrees are high.

RP Cosine Similarity is observed to be largely immune to both of the
aforementioned effects, and is able to preserve the quality of the rankings,
as anticipated in §4.3.

##  5 Conclusion

Based on the discussion in §3.3 this paper and the numerical results, we
propose that practitioners of random projection methods first use the
embeddings $u\mapsto\frac{X_{u*}}{\|X_{u*}\|}$, in which case cosine
similarity will be well preserved under the random projection both when
$X=AR^{t}$ and when $X=TR^{t}$.

If the practitioners do not have a need for embeddings of high degree nodes
(or those might not exist) they can use the embeddings $u\mapsto X_{u*}$ where
$X=TR^{t}$. The dot product for the lower degree nodes will be well preserved
as shown in §3.2.

Use of $u\mapsto X_{u*}$ where $X=AR^{t}$ is discouraged since it very
difficult to control the possible error as we shown in §3.1.

## Acknowledgments

The first author is grateful to the Department of Mathematics at the
University of Washington in Seattle, where part of the work took place, for
the hospitality.

## References

  * [1] Dimitris Achlioptas.  Database-friendly Random Projections: Johnson-Lindenstrauss with Binary Coins.  Journal of Computer and System Sciences, 66(4):671–687, 2003.
  * [2] Devansh Arpit, Ifeoma Nwogu, Gaurav Srivastava, and Venu Govindaraju.  An Analysis of Random Projections in Cancelable Biometrics.  arXiv preprint arXiv:1401.4489, 2014.
  * [3] 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 Annual ACM SIGACT Symposium on Theory of Computing, pages 1039–1050, 2019.
  * [4] Monica Bianchini, Marco Gori, and Franco Scarselli.  Inside PageRank.  ACM Transactions on Internet Technology (TOIT), 5(1):92–128, 2005.
  * [5] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  Concentration Inequalities.  Oxford University Press, Oxford, 2013.  A nonasymptotic theory of independence, With a foreword by Michel Ledoux.
  * [6] Christos Boutsidis, Anastasios Zouzias, and Petros Drineas.  Random projections for $k$-means clustering.  Advances in neural information processing systems, 23, 2010.
  * [7] Maria Sofia Bucarelli, Matilde Larsen, Chris Schwiegelshohn, and Mads Toftrup.  On Generalization Bounds for Projective Clustering.  Advances in Neural Information Processing Systems, 36, 2024.
  * [8] Timothy I Cannings and Richard J Samworth.  Random-projection ensemble classification.  Journal of the Royal Statistical Society Series B: Statistical Methodology, 79(4):959–1035, 2017.
  * [9] Ângelo Cardoso and Andreas Wichert.  Iterative random projections for high-dimensional data clustering.  Pattern Recognition Letters, 33(13):1749–1755, 2012.
  * [10] Haochen Chen, Syed Fahad Sultan, Yingtao Tian, Muhao Chen, and Steven Skiena.  Fast and Accurate Network Embeddings via Very Sparse Random Projection.  In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM ’19, page 399–408, New York, NY, USA, 2019. Association for Computing Machinery.
  * [11] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar.  Improved Coresets for Euclidean $k$-Means.  Advances in Neural Information Processing Systems, 35:2679–2694, 2022.
  * [12] Sanjoy Dasgupta and Anupam Gupta.  An elementary proof of a theorem of Johnson and Lindenstrauss.  Random Structures & Algorithms, 22(1):60–65, 2003.
  * [13] Timothy A Davis and Yifan Hu.  The University of Florida Sparse Matrix Collection.  ACM Transactions on Mathematical Software (TOMS), 38(1):1–25, 2011.
  * [14] Robert Durrant and Ata Kabán.  Sharp generalization error bounds for randomly-projected classifiers.  In International Conference on Machine Learning, pages 693–701. PMLR, 2013.
  * [15] Casper B Freksen, Lior Kamma, and Kasper Green Larsen.  Fully Understanding the Hashing Trick.  Advances in Neural Information Processing Systems, 31, 2018.
  * [16] Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, and Mark Crowley.  Johnson-Lindenstrauss lemma, linear and nonlinear random projections, random Fourier features, and random kitchen sinks: Tutorial and survey.  arXiv preprint arXiv:2108.04172, 2021.
  * [17] Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp.  Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.  SIAM review, 53(2):217–288, 2011.
  * [18] William L Hamilton.  Graph Representation Learning, volume 14 of Synthesis Lectures on Artifical Intelligence and Machine Learning.  Morgan & Claypool Publishers, 2020.
  * [19] Piotr Indyk and Rajeev Motwani.  Approximate nearest neighbors: towards removing the curse of dimensionality.  In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604–613, 1998.
  * [20] Meena Jagadeesan.  Understanding Sparse JL for Feature Hashing.  Advances in Neural Information Processing Systems, 32, 2019.
  * [21] William B Johnson, Joram Lindenstrauss, and Gideon Schechtman.  Extensions of Lipschitz maps into Banach spaces.  Israel Journal of Mathematics, 54(2):129–138, 1986.
  * [22] Ata Kaban.  Improved bounds on the dot product under random projection and random sign projection.  In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’15, page 487–496, New York, NY, USA, 2015. Association for Computing Machinery.
  * [23] Keegan Kang.  Correlations between random projections and the bivariate normal.  Data Min. Knowl. Discov., 35(4):1622–1653, 2021.
  * [24] Jon M Kleinberg.  Two algorithms for nearest-neighbor search in high dimensions.  In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 599–608, 1997.
  * [25] Ping Li, Trevor J Hastie, and Kenneth W Church.  Improving random projections using marginal information.  In Learning Theory: 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006. Proceedings 19, pages 635–649. Springer, 2006.
  * [26] Kun Liu.  Random projection-based multiplicative data perturbation for privacy preserving distributed data mining.  IEEE Transactions on knowledge and Data Engineering, 18(1):92–106, 2005.
  * [27] Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn.  Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1027–1038, 2019.
  * [28] Per-Gunnar Martinsson and Joel A Tropp.  Randomized Numerical Linear Algebra: Foundations and algorithms.  Acta Numerica, 29:403–572, 2020.
  * [29] Mark Newman.  Networks.  Oxford University Press, 2018.
  * [30] Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, et al.  The PageRank citation ranking: Bringing order to the web.  1999\.
  * [31] Qinfeng Shi, Chunhua Shen, Rhys Hill, and Anton Van Den Hengel.  Is Margin Preserved after Random Projection?  In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML’12, page 643–650, Madison, WI, USA, 2012. Omnipress.
  * [32] Aleksandros Sobczyk and Mathieu Luisier.  Approximate Euclidean lengths and distances beyond Johnson-Lindenstrauss.  Advances in Neural Information Processing Systems, 35:19357–19369, 2022.
  * [33] Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S Yu, and Tianyi Wu.  Pathsim: Meta path-based top-k similarity search in heterogeneous information networks.  Proceedings of the VLDB Endowment, 4(11):992–1003, 2011.
  * [34] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang.  Social influence analysis in large-scale networks.  In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 807–816, 2009.
  * [35] A. W. van der Vaart.  Asymptotic statistics, volume 3 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, Cambridge, 1998.
  * [36] Santosh S. Vempala.  The Random Projection Method, volume 65 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science.  American Mathematical Society, Providence, RI, 2004.  With a foreword by Christos H. Papadimitriou.
  * [37] Roman Vershynin.  High-dimensional Probability, volume 47 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, Cambridge, 2018.  An introduction with applications in data science, With a foreword by Sara van de Geer.
  * [38] Yongjin Wang and Konstantinos N Plataniotis.  An analysis of random projection for changeable and privacy-preserving biometric verification.  IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 40(5):1280–1293, 2010.
  * [39] Ziwei Zhang, Peng Cui, Haoyang Li, Xiao Wang, and Wenwu Zhu.  Billion-Scale Network Embedding with Iterative Random Projection.  In 2018 IEEE International Conference on Data Mining (ICDM), pages 787–796, 2018.

##  Appendix A General Results and Remarks

###  A.1 Vector Representation

For any vector $x$ in $\mathbb{R}^{n}$ we will denote $\tilde{x}:=x/\|x\|.$

Note that for non-zero vectors $x$ and $y$ in $\mathbb{R}^{n}$, cosine
similarity has the property

$\frac{(x,y)}{\|x\|\|y\|}=(x/\|x\|,y/\|y\|)=(\tilde{x},\tilde{y}).$ (31)

Also, for any matrix $Q\in\mathbb{R}^{q\times n}$

$\frac{(Qx,Qy)}{\|Qx\|\|Qy\|}=\frac{(Q(x/\|x\|),Q(y/\|y\|))}{\|Q(x/\|x\|)\|\|Q(y/\|y\|)\|}=\frac{(Q\tilde{x},Q\tilde{y})}{\|Q\tilde{x}\|\|Q\tilde{y}\|}$
(32)

For unit vectors $\tilde{x}$ and $\tilde{y}$, we know from the Gram-Schmidt
process that there exists a unique vector $r_{\tilde{x},\tilde{y}}$ such that

$\tilde{x}-(\tilde{x},\tilde{y})\tilde{y}=:r_{\tilde{x},\tilde{y}}.$

Recall that $r_{\tilde{x},\tilde{y}}$ is perpendicular to $\tilde{y}$. Hence,
we have $\|r_{\tilde{x},\tilde{y}}\|=\sqrt{1-(\tilde{x},\tilde{y})^{2}}$.
Hence, we can set
$\tilde{r}_{\tilde{x},\tilde{y}}=r_{\tilde{x},\tilde{y}}/\|r_{\tilde{x},\tilde{y}}\|$
and we have

$\tilde{x}=(\tilde{x},\tilde{y})\tilde{y}+\sqrt{1-(\tilde{x},\tilde{y})^{2}}\tilde{r}_{\tilde{x},\tilde{y}}.$
(33)

Note that $\tilde{y}$ and $\tilde{r}_{\tilde{x},\tilde{y}}$ are unit and
orthogonal vectors.

We will often use $\rho=\rho_{xy}=\frac{(x,y)}{\|x\|\|y\|}$ to denote the
cosine similarity of $x$ and $y$.

We can now summarize our findings.

######  Proposition A.1.

For any two non-zero vectors $x$ and $y$ in $\mathbb{R}^{n}$ there exists a
unique unit vector $r_{\tilde{x},\tilde{y}}$ orthogonal to $\tilde{y}$ such
that

$\tilde{x}=\rho\tilde{y}+\sqrt{1-\rho^{2}}r_{\tilde{x},\tilde{y}},$

where $\rho$ is the cosine similarity between $x$ and $y$.

###  A.2 Random Projection Properties

In this paper, $Q$ will denote a random $q\times n$ matrix whose entries
$Q_{ij}\sim\mathcal{N}(0,1)$ are i.i.d. Random vectors consisting of i.i.d.
$\mathcal{N}(0,1)$ random variables we will call standard normal random
vectors.

######  Lemma A.2.

Let $x$ and $y$ be two orthogonal unit vectors in $\mathbb{R}^{n}$, i.e.
$(x,y)=0$ and $\|x\|=\|y\|=1$. Then $Qx$ and $Qy$ are two independent
identically distributed standard normal random vectors of dimension $q$ .

###### Proof.

We can show that $(Qx)_{1}$, …, $(Qx)_{q}$, $(Qy)_{1}$, …, $(Qy)_{q}$ are
i.i.d and $\mathcal{N}(0,1)$.

Note that

$(Qx)_{k}=\sum_{j=1}^{n}Q_{kj}x_{j}\sim\mathcal{N}(0,\|x\|^{2}),$ (34)

and

$(Qy)_{k}=\sum_{j=1}^{n}Q_{kj}y_{j}\sim\mathcal{N}(0,\|y\|^{2}).$ (35)

Therefore, all of these random variables have the distribution
$\mathcal{N}(0,1)$. From the definition of $Q$, (34) and (35) we can conclude
that the sequences $(Qx)_{1},(Qx)_{2},\ldots,(Qx)_{q}$ and
$(Qy)_{1},(Qy)_{2},\ldots,(Qy)_{q}$ are i.i.d.

Finally, let us look at the covariance between $(Qx)_{k}$ and $(Qy)_{l}$.

$\displaystyle\mathbb{E}[(Qx)_{k}(Qy)_{l}]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{j=1}^{n}Q_{kj}x_{j}\right)\left(\sum_{j=1}^{n}Q_{lj}y_{j}\right)\right]$
(36)

If $l\neq k$ then two sums under the expectation are independent and hence

$\displaystyle\eqref{eq:prodExpectation}$
$\displaystyle=\mathbb{E}\left[\left(\sum_{j=1}^{n}Q_{kj}x_{j}\right)\right]\mathbb{E}\left[\left(\sum_{j=1}^{n}Q_{lj}y_{j}\right)\right]$
$\displaystyle=0\cdot 0.$

Else, if $l=k$ then:

$\displaystyle\eqref{eq:prodExpectation}$
$\displaystyle=\mathbb{E}\left[\sum_{j=1}^{n}Q_{kj}^{2}x_{j}y_{j}+2\sum_{i\neq
j}Q_{kj}Q_{ki}x_{j}y_{i}\right]$
$\displaystyle=\sum_{j=1}^{n}\underbrace{\mathbb{E}[Q_{kj}^{2}]}_{1}x_{j}y_{j}+2\sum_{i\neq
j}\underbrace{\mathbb{E}[Q_{kj}Q_{ki}]}_{0}x_{j}y_{i}$
$\displaystyle=\sum_{j=1}^{n}x_{j}y_{j}=(\tilde{x},\tilde{y})=0.$

The claim now follows. ∎

Recall from §2, that $R:=q^{-1/2}Q$ is a random $q\times n$ matrix whose
entries $R_{ij}\sim\mathcal{N}(0,1/q)$ are i.i.d. Note that, due to the
scaling properties,

$\frac{(Qx,Qy)}{\|Qx\|\|Qy\|}=\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}.$ (37)

We will state all the main results in the term of the matrix $R$, however $Q$
will let us simplify some proofs.

##  Appendix B Rotation argument and representation

Let $x$ and $y$ be vectors in $\mathbb{R}^{n}$ and
$\rho=\frac{(x,y)}{\|x\|\|y\|}$. We will show the following result.

######  Theorem B.1.

There exist $M,N$ independent standard normal random vectors of length $q$
such that, (a) For the dot product we have

$(Qx,Qy)=\|x\|\|y\|(\rho\|N\|^{2}+M_{1}\|N\|\sqrt{1-\rho^{2}}).$ (38)

(b) For the cosine similarity

$\frac{(Qx,Qy)}{\|Qx\|\|Qy\|}=\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}\\\
=\frac{\rho\|N\|+M_{1}\sqrt{1-\rho^{2}}}{\sqrt{(\rho\|N\|+M_{1}\sqrt{1-\rho^{2}})^{2}+(1-\rho^{2})\|M_{2\ldots
q}\|^{2}}},$ (39)

where $M_{j}$ is the $j$-th component of the vector $M$ and $M_{2\ldots
q}=(M_{2},\ldots,M_{q})$.

The rotation argument is powered by the the following well-known lemma that
describes relationship between normal and spherical distributions:

######  Lemma B.2.

For the standard normal random vector $N$ of dimension $q$ the following are
independent $\|N\|$ and $\tilde{x}=x/\|N\|$. Where $\|N\|^{2}\sim\chi^{2}(q)$
and $\tilde{y}$ is uniformly distributed on the unit sphere.

For the proof see [37, §3.3.3].

###### Proof of Theorem B.1.

Note that $Qx=\rho Qy+\sqrt{1-\rho^{2}}Q\tilde{r}_{\tilde{x},\tilde{y}}$.
Since, $(y,\tilde{r}_{\tilde{x},\tilde{y}})=0$, by Lemma A.2 we know that
$H=R\tilde{r}_{\tilde{x},\tilde{y}}$ and $N=Ry$ are independent standard
normal random variables. Hence, we have

$\displaystyle\frac{(Qx,Qy)}{\|Qx\|\|Qy\|}$ $\displaystyle=\frac{(\rho
N+\sqrt{1-\rho^{2}}H,N)}{\|\rho N+\sqrt{1-\rho^{2}}H\|\|N\|}$ (40)
$\displaystyle=\frac{(\rho N+\sqrt{1-\rho^{2}}H,\tilde{y})}{\|\rho
N+\sqrt{1-\rho^{2}}H\|}$ (41)

We now pick the orthogonal $q\times q$ matrix $U_{\tilde{N}}$ for which
$U_{\tilde{N}}\tilde{N}=e_{1}$. Applying the $U_{\tilde{N}}$-transformation to
all arguments in (41) we get

$\displaystyle\frac{(Qx,Qy)}{\|Qx\|\|Qy\|}$
$\displaystyle=\frac{(U_{\tilde{N}}(\rho\|N\|\tilde{N}+\sqrt{1-\rho^{2}}H),U_{\tilde{N}}(\tilde{N}))}{\|U_{\tilde{N}}(\rho\|N\|\tilde{N}+\sqrt{1-\rho^{2}}H)\|}$
$\displaystyle=\frac{(\rho\|N\|e_{1}+\sqrt{1-\rho^{2}}U_{\tilde{N}}H,e_{1})}{\|\rho\|N\|e_{1}+\sqrt{1-\rho^{2}}U_{\tilde{N}}H\|}$

Setting $M:=U_{\tilde{N}}H$. Since $U_{\tilde{N}}$ is orthogonal and
independent of $H$, $M$ remains independent of $N$.

We have can apply the same arguments to the dot product:

$\displaystyle(Qx,Qy)$ $\displaystyle=(\rho N+\sqrt{1-\rho^{2}}H,N)$
$\displaystyle=\|N\|(\rho N+\sqrt{1-\rho^{2}}H,\tilde{y})$
$\displaystyle=\|N\|(U_{\tilde{N}}(\rho\|N\|\tilde{N}+\sqrt{1-\rho^{2}}H),U_{\tilde{N}}(\tilde{N}))$
$\displaystyle=\|N\|(\rho\|N\|e_{1}+\sqrt{1-\rho^{2}}U_{\tilde{N}}H,e_{1})$
$\displaystyle=\rho\|N\|^{2}+\sqrt{1-\rho^{2}}(U_{\tilde{N}}H,e_{1})\|N\|$
$\displaystyle=\rho\|N\|^{2}+\sqrt{1-\rho^{2}}M_{1}\|N\|.$

∎

##  Appendix C Results on the dot product

In this section we analyze how the dot product changes under random
projection. Some of the results here are well known, but for completeness and
to demonstrate the power of the representation in Theorem B.1, we will prove
them.

###  C.1 Probability of sign change

One of the practical questions when doing the random projections is will the
dot product or cosine similarity change the sign. In some practical settings
vectors $u$ and $v$ can have all non-negative components and as such their dot
product is also non-negative. Can the projection change that? The
representation for the dot product gives us an exact answer to that question.

######  Proposition C.1.

(a) If $(u,v)=0$ and $\|u\|\|v\|\neq 0$ then
$\mathbb{P}((Ru,Rv)<0)=\mathbb{P}((Ru,Rv)>0)=\frac{1}{2}$.

(b) If $(u,v)\neq 0$ and $|\rho|\neq 1$ then

$\mathbb{P}\left(\frac{(Ru,Rv)}{(u,v)}<0\right)=\mathbb{P}\left(T_{q}>\frac{|\rho|\sqrt{q}}{\sqrt{1-\rho^{2}}}\right),$

where $T_{q}$ is the $t$-distribution with the parameter $q$.

###### Proof.

In the case (a) $\rho=0$ and the claim follows from the (38), since the sign
depends on the sign of $M_{1}$ which can be positive or negative with
probability $\frac{1}{2}$. In (b) we can assume $(u,v)>0$ and hence $\rho>0$.
Hence

$\displaystyle\mathbb{P}\left(\frac{(Ru,Rv)}{(u,v)}<0\right)=\mathbb{P}\left((Ru,Rv)<0\right)$
$\displaystyle=\mathbb{P}\left((q^{-1/2}Qu,q^{-1/2}Qv)<0\right)$
$\displaystyle=\mathbb{P}\left((Qu,Qv)<0\right)$
$\displaystyle=\mathbb{P}\left(\rho\|N\|^{2}+M_{1}\|N\|\sqrt{1-\rho^{2}}<0\right)$
$\displaystyle=\mathbb{P}\left(\frac{M_{1}}{\|N\|}<-\frac{\rho}{\sqrt{1-\rho^{2}}}\right)$
$\displaystyle=\mathbb{P}\left(\frac{M_{1}}{\sqrt{\|N\|^{2}/q}}<-\frac{\rho\sqrt{q}}{\sqrt{1-\rho^{2}}}\right).$

Since $\frac{M_{1}}{\sqrt{\|N\|^{2}/p}}\sim t(q)$ the claim follows from the
fact that $t(q)$ is symmetric random variable for the last expression we have

$\displaystyle=\mathbb{P}\left(T_{q}<-\frac{\rho\sqrt{q}}{\sqrt{1-\rho^{2}}}\right)$
$\displaystyle=\mathbb{P}\left(T_{q}>\frac{\rho\sqrt{q}}{\sqrt{1-\rho^{2}}}\right).$

∎

As we can see from the graph on Figure 3 the probability of changing a sign is
the highest - $\frac{1}{2}$ for $\rho=0$ and and quickly becomes really low.
In [22, Corollary 3.2.2.] that the
$\mathbb{P}\left(\frac{(Ru,Rv)}{(u,v)}<0\right)\leq\exp(-q\rho^{2}/8)$ and
this result gives the exact value of the probability.

Figure 3: Graphs of functions
$\rho\mapsto\mathbb{P}\left(\mathcal{T}_{q}>\frac{|\rho|\sqrt{q}}{\sqrt{1-\rho^{2}}}\right)$
and
$\rho\mapsto\log\mathbb{P}\left(T_{q}>\frac{|\rho|\sqrt{q}}{\sqrt{1-\rho^{2}}}\right)$
for $q=100$ on the interval $[-0.5,0.5]$.

This results tells us that the probability of the dot product sign change
under random projection is a function of $\rho$, which in practice we don’t
know. If we wanted to calculate a probability of a cosine similarity or dot
product changing signs in case of a large number of vectors it would be hard
to do so. However we can still conclude that if $\rho$ is close to zero we can
expect the sign to change, while if it is reasonably far from 0 it is unlikely
that the sign will change.

###  C.2 Central Limit Theorem

The representation given in (38) has many consequences. For example, we can
simply calculate the expectation and the variance of the dot product.

######  Proposition C.2.

We have $\mathbb{E}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}\right]=\rho$ and ${\rm
Var}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}\right]=\frac{1+\rho^{2}}{q}$.

###### Proof.

Recall that $\mathbb{E}[M_{1}]=1$ and $\mathbb{E}[M_{1}^{2}]=1$;
$\mathbb{E}[\|N\|^{2}]=q$ and $\mathbb{E}[\|N\|^{4}]=q(q+2)$. Using (38) we
have

$\displaystyle\mathbb{E}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}\right]$
$\displaystyle=q^{-1}(\rho\mathbb{E}[\|N\|^{2}]+\mathbb{E}[\|N\|]\mathbb{E}[M_{1}]\sqrt{1-\rho^{2}})$
$\displaystyle=q^{-1}\rho q+\mathbb{E}[\|N\|]\cdot
0\cdot\sqrt{1-\rho^{2}}=\rho,$

and

$\displaystyle\mathbb{E}\left[\left(\frac{(Rx,Ry)}{\|x\|\|y\|}\right)^{2}\right]$
$\displaystyle=q^{-2}\rho^{2}\mathbb{E}[\|N\|^{4}]+2q^{-2}\mathbb{E}[\|N\|^{3}]\mathbb{E}[M_{1}]\rho\sqrt{1-\rho^{2}}+q^{-2}\mathbb{E}[\|N\|^{2}]\mathbb{E}[M_{1}^{2}](1-\rho^{2})]$
$\displaystyle=q^{-2}\rho^{2}q(q+2)+0+q^{-2}\cdot q\cdot 1\cdot(1-\rho^{2})$
$\displaystyle=\rho^{2}+\frac{1+\rho^{2}}{q}.$

Now, since ${\rm
Var}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}\right]=\mathbb{E}\left[\left(\frac{(Rx,Ry)}{\|x\|\|y\|}\right)^{2}\right]-\left(\mathbb{E}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}\right]\right)^{2}$,
the claim follows. ∎

We can also get the following asymptotic result relatively easy.

######  Theorem C.3.

We have

$\sqrt{q}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho\right]\stackrel{{\scriptstyle
d}}{{\to}}\mathcal{N}(0,1+\rho^{2}),$

as $q\to\infty$.

###### Proof.

Form the Central Limit Theorem we have
$\frac{\|N\|^{2}-q}{\sqrt{q}}=q^{-1/2}\sum_{j=1}^{q}(N_{1}^{2}-1)\stackrel{{\scriptstyle
d}}{{\to}}\mathcal{N}(0,2)$ and by the Law of Large Numbers we have
$\frac{1}{\sqrt{q}}\|N\|=\sqrt{\frac{N_{1}^{2}+\ldots+N_{q}^{2}}{q}}\to 1$
almost surely. Since $M_{1}$ is independent, we have

$\displaystyle\sqrt{q}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho\right]$
$\displaystyle=\left[\rho\cdot\frac{\|N\|^{2}-q}{\sqrt{q}}+M_{1}\frac{\|N\|}{\sqrt{q}}\sqrt{1-\rho^{2}}\right]$
$\displaystyle\stackrel{{\scriptstyle
d}}{{\to}}\hat{\mathcal{N}}(0,2\rho^{2})+\mathcal{N}(0,1-\rho^{2})$
$\displaystyle\stackrel{{\scriptstyle d}}{{=}}\mathcal{N}(0,1+\rho^{2}).$

∎

We can write the last result in the following form, which we stated in part
(a) of Proposition 2.2.

######  Corollary C.4.

We have

$\sqrt{q}[(Rx,Ry)-(x,y)]\stackrel{{\scriptstyle
d}}{{\to}}N(0,\|x\|^{2}\|y\|^{2}+(x,y)^{2}),$

as $q\to\infty$.

######  Remark C.5.

Although, $(Rx,Ry)$ is an unbiased and asymptotically normal estimator for
$(x,y)$, the control of the standard deviation can be a problem. $(x,y)$ could
be small compared to the value of
$\sigma=\sqrt{\frac{\|x\|^{2}\|y\|^{2}+(x,y)^{2}}{q}}$. Let
$x=(1,0,1,0,\ldots)$ and $y=(0,1,0,1,\ldots)$, then $(x,y)=0$ and
$\sigma=\frac{n}{2\sqrt{q}}$. However, since $q<<n$ the random projection
might be nowhere near the value of $(x,y)$. Simulation in Figure 4 illustrates
this issue.

Figure 4: Simulated dot product $(R\tilde{x},R\tilde{y})$ for
$x=(1,0,1,0,\ldots)$ and $y=(0,1,0,1,\ldots)$ for $n=2000$ and $q=100$.

###  C.3 Concentration results

So far we have shown that $\frac{(Rx,Ry)}{\|x\|\|y\|}$ is an unbiased and
asymptotically normal estimator for $\rho$. However when we have many vectors
and we want to be sure that all of their similarities get randomly projected
to approximate values we will need to use concentration results.

First, using (38) we calculate the Laplace transform.

######  Proposition C.6.

We have

$\mathbb{E}[\exp(\lambda(Q\tilde{x},Q\tilde{y}))]=[(1-\lambda(1+\rho))(1-\lambda(\rho-1))]^{-q/2}$
(42)

for $\lambda\in(-(1-\rho)^{-1},(1+\rho)^{-1})$

###### Proof.

Recall that $\mathbb{E}(e^{\lambda M_{1}})=e^{\lambda^{2}/2}$ for all
$\lambda\in\mathbb{R}$ and
$\mathbb{E}(e^{\lambda\|N\|^{2}})=(1-2\lambda)^{-q/2}$ for $\lambda<1/2$. By
applying the Laplace transform first to $M_{1}$ and then to $\|N\|^{2}$ we get

$\displaystyle\mathbb{E}[\exp(\lambda(Q\tilde{x},Q\tilde{y}))]$
$\displaystyle=\mathbb{E}\left[e^{\lambda\rho\|N\|^{2}}\mathbb{E}\left[e^{\lambda\|N\|\sqrt{1-\rho^{2}}M_{1}}|\|N\|\right]\right]$
$\displaystyle=\mathbb{E}\left[e^{\lambda\rho\|N\|^{2}}e^{\lambda^{2}\|N\|^{2}(1-\rho^{2})/2}\right]$
$\displaystyle=\mathbb{E}\left[e^{(\lambda\rho+\lambda^{2}(1-\rho^{2})/2)\|N\|^{2}}\right]$
$\displaystyle=(1-(2\lambda\rho-\lambda^{2}(1-\rho^{2})))^{-q/2}$
$\displaystyle=[(1-\lambda(1+\rho))(1-\lambda(\rho-1))]^{-q/2}$

∎

We will now use the the Laplace Transform to obtain Chernhov bounds. The
following Lemma will be a useful estimate.

######  Lemma C.7.

For $\lambda\in(0,(1+\rho)^{-1})$ we have

$\log\mathbb{E}[\exp(\lambda[(Q\tilde{x},Q\tilde{y})-q\rho])]\leq\frac{\lambda^{2}q(1+\rho^{2})}{2(1-\lambda(1+\rho))},$
(43)

and $\lambda\in(0,(1-\rho)^{-1})$

$\log\mathbb{E}[\exp(-\lambda[(Q\tilde{x},Q\tilde{y})-q\rho)]]\\\
\leq\frac{\lambda^{2}q(1+\rho^{2})}{2(1-\lambda(1-\rho))}.$ (44)

###### Proof.

In case $\rho=1$ or $\rho=-1$ expression in (42) will simplify and we will be
able to use Proposition E.3 on $X$ and $-X$ respectively.

One can show that for $s\in(0,1)$ we have (see Lemma E.6 (a)):

$(-\log(1-s)-s)\leq\frac{s^{2}}{2(1-s)},$ (45)

and for $s<0$ (see Lemma E.6 (a)):

$(-\log(1-s)-s)\leq\frac{s^{2}}{2}.$ (46)

We will prove (43), (44) is shown in the same way.

$\displaystyle\log\mathbb{E}[\exp(\lambda(Q\tilde{x},Q\tilde{y})-q\rho)]$
$\displaystyle=-\lambda q\rho-\frac{q}{2}\log(1-\lambda(1+\rho))$
$\displaystyle-\frac{q}{2}\log(1-\lambda(\rho-1))$
$\displaystyle=\frac{q}{2}\left[-\log(1-\lambda(1+\rho))-\lambda(1+\rho)\right]$
$\displaystyle+\frac{q}{2}\left[-\log(1-\lambda(\rho-1))-\lambda(\rho-1)\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:HelpInequality},\eqref{eq:HelpInequality1}}}{{\leq}}\frac{q}{2}\left[\frac{\left(\lambda(1+\rho)\right)^{2}}{2(1-\lambda(1+\rho))}+\frac{\left(\lambda(\rho-1)\right)^{2}}{2}\right]$
$\displaystyle\leq\frac{q}{2}\left[\frac{(\lambda(1+\rho))^{2}}{2(1-\lambda(1+\rho))}+\frac{\left(\lambda(\rho-1)\right)^{2}}{2(1-\lambda(1+\rho))}\right]$
$\displaystyle=\frac{q}{2}\left[\frac{\left(\lambda(1+\rho)\right)^{2}+\left(\lambda(\rho-1)\right)^{2}}{2(1-\lambda(1+\rho))}\right]$
$\displaystyle=\frac{\lambda^{2}q(1+\rho^{2})}{2(1-\lambda(1+\rho))}$

This proves (43), the equation (44) can be proved in the same way. ∎

######  Theorem C.8.

For $t\geq 0$ we have

$\mathbb{P}((Q\tilde{x},Q\tilde{y})-q\rho>t)\\\
\leq\exp\left(\frac{-t^{2}}{2q(1+\rho^{2})+2(1+\rho)t}\right),$ (47)

and

$\mathbb{P}((Q\tilde{x},Q\tilde{y})-q\rho<-t)\\\
\leq\exp\left(\frac{-t^{2}}{2q(1+\rho^{2})+2(1-\rho)t}\right).$ (48)

###### Proof.

Note that $\mathbb{E}[(Q\tilde{x},Q\tilde{y})]=q\rho$.

Since (43) holds we can use Theorem E.1 by setting $X=(Q\tilde{x},Q\tilde{y})$
to obtain (47).

Since (44) holds we can use Theorem E.1 by setting by setting
$X=-(Q\tilde{x},Q\tilde{y})$ to obtain (48). ∎

######  Proposition C.9.

For any function $f:[-1,1]\to[0,\infty)$ we have:

$\mathbb{P}((Q\tilde{x},Q\tilde{y})-q\rho>q\varepsilon f(\rho))\\\
\leq\exp\left(\frac{-qf(\rho)^{2}}{2(1+\rho^{2})}\left[\varepsilon^{2}-\varepsilon^{3}\frac{1+\rho}{1+\rho^{2}}f(\rho)\right]\right)$
(49) $\mathbb{P}((Q\tilde{x},Q\tilde{y})-q\rho<-q\varepsilon f(\rho))\\\
\leq\exp\left(\frac{-qf(\rho)^{2}}{2(1+\rho^{2})}\left[\varepsilon^{2}-\varepsilon^{3}\frac{1-\rho}{1+\rho^{2}}f(\rho)\right]\right)$
(50)

######  Remark C.10.

Note that for $\rho=1$ and $f(\rho)=\varepsilon$ we get the usual bounds for
$\chi^{2}(q)$ used to prove Johnson -Lindenstrauss Lemma as given, for example
in, in [36, Lemma 1.3.] and [16].

###  C.4 Johnson-Lindenstrauss-type result

######  Theorem C.11.

Let $x_{1},\ldots x_{k}$ be a finite set of vectors in $\mathbb{R}^{n}$ and
let $\varepsilon\in(0,1)$ and $\delta\in(0,1)$, then for $q\geq
4\cdot\frac{1+\varepsilon}{\varepsilon^{2}}\log\frac{k(k-1)}{\delta}$

$\left|\frac{(Rx_{j},Rx_{i})}{\|x_{j}\|\|x_{i}\|}-\frac{(x_{j},x_{i})}{\|x_{j}\|\|x_{i}\|}\right|<\varepsilon$

for $i<j$ with probability at least $1-\delta$.

We have $\binom{k}{2}$ cosine similarities in the statement above and in
practice we will have no way of estimating222One exception is the case when
$x_{1},\ldots,x_{k}$ are all in $[0,\infty)^{n}$, i.e. have nonnegative
coordinates. In that case we know cosine similarities will be in interval
$[0,1]$. them. To prove this result we need a probablity estimate that doesn’t
depend on the value of the cosine similarity. The following Proposition will
help us in that by simplifying the statement of Theorem C.8.

######  Proposition C.12.

For $\varepsilon>0$ we have

$\mathbb{P}\left(\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho>\varepsilon\right)\leq\exp\left(\frac{-q\varepsilon^{2}}{4(1+\varepsilon)}\right),$
(51)

and

$\mathbb{P}\left(\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho<-\varepsilon\right)\leq\exp\left(\frac{-q\varepsilon^{2}}{4(1+\varepsilon)}\right).$
(52)

###### Proof.

By setting $t=q\varepsilon$ in (47) we get

$\mathbb{P}\left(\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho>\varepsilon\right)\leq\exp\left(\frac{-q\varepsilon^{2}}{2(1+\rho^{2})+2(1+\rho)\varepsilon}\right),$

Using the fact that $|\rho|\leq 1$ we get

$\frac{-q\varepsilon^{2}}{2(1+\rho^{2})+2(1+\rho)\varepsilon}\leq\frac{-q\varepsilon^{2}}{4(1+\varepsilon)}.$

This proves (51). Bound in (52) can be shown in a same way. ∎

###### Proof of Theorem C.11..

Define sets

$\displaystyle A_{ij}$
$\displaystyle=\left(\left|\frac{(Ry_{j},Rx_{i})}{\|x_{j}\|\|y_{i}\|}-\frac{(y_{j},x_{i})}{\|x_{j}\|\|y_{i}\|}\right|<\varepsilon\right)$
$\displaystyle A_{ij}^{c+}$
$\displaystyle=\left(\frac{(Ry_{j},Rx_{i})}{\|x_{j}\|\|y_{i}\|}-\frac{(y_{j},x_{i})}{\|x_{j}\|\|y_{i}\|}>\varepsilon\right)$
$\displaystyle A_{ij}^{c-}$
$\displaystyle=\left(\frac{(Ry_{j},Rx_{i})}{\|x_{j}\|\|y_{i}\|}-\frac{(y_{j},x_{i})}{\|x_{j}\|\|y_{i}\|}<-\varepsilon\right)$

Note that $A_{ij}^{c}=A_{ij}^{c+}\cup A_{ij}^{c-}$. Using the union bound
tehnicque we get

$\displaystyle P\left(\bigcap_{i<j}A_{ij}\right)$
$\displaystyle=1-P\left(\bigcup_{i<j}A_{ij}^{c}\right)$
$\displaystyle=1-P\left(\bigcup_{i<j}A_{ij}^{c+}\cup A_{ij}^{c-}\right)$
$\displaystyle\geq
1-\sum_{i<j}[\mathbb{P}(A_{ij}^{c+})+\mathbb{P}(A_{ij}^{c-})].$

From Proposition C.12 and bound on $q$ we have that

$\displaystyle\sum_{i<j}[\mathbb{P}(A_{ij}^{c+})+\mathbb{P}(A_{ij}^{c-})]$
$\displaystyle\leq
k(k-1)\exp\left(-q\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right)$
$\displaystyle\leq
k(k-1)\exp\left(-4\cdot\frac{1+\varepsilon}{\varepsilon^{2}}\log\frac{k(k-1)}{\delta}\cdot\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right)$
$\displaystyle=\delta.$

∎

###  C.5 Comparison with known results

Regarding known estimates for the dot product, Theorem 2.1. from [22] provides
the following bounds for $\varepsilon\in(0,1)$:

$\mathbb{P}\left(\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho>\varepsilon\right)\leq
e^{-\frac{q\varepsilon^{2}}{8}},$

and

$\mathbb{P}\left(\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho<-\varepsilon\right)\leq
e^{-\frac{q\varepsilon^{2}}{8}}.$

This a simple consequence of Proposition C.12.

Equation (4) in [23] provides the following estimate:

$\mathbb{P}\left(\left|\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho\right|\leq\varepsilon\right)\geq
1-4e^{-\frac{q(\varepsilon^{2}-\varepsilon^{3})}{4}}.$

Since
$\varepsilon^{2}-\varepsilon^{3}\leq\frac{\varepsilon^{2}}{1+\varepsilon}$,
again, from Propostion C.12 we can get a better estimate

$\mathbb{P}\left(\left|\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho\right|\leq\varepsilon\right)\geq
1-2e^{-\frac{q\varepsilon^{2}}{4(1+\varepsilon)}}.$

##  Appendix D Cosine similarity

In this section, we will examine the behavior of cosine similarity under
random projection. We will begin by examining some special cases and then
develop a general approach.

###  D.1 Some special cases

Recall that in the case of $\rho=\pm 1$, i.e.

$\frac{(x,y)}{\|x\|\|y\|}=\pm 1$

there exists $\alpha>0$ such that $x=\pm\alpha y$. This is a known consequence
of the Cauchy-Schwarz inequality.

In this case we have

$\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\frac{(R(\pm\alpha y),Qy)}{\|R(\pm\alpha
y)\|\|Ry\|}=\\\
=\frac{\pm\alpha(Ry,Ry)}{\alpha\|Ry\|\|Ry\|}=\pm\frac{\|Ry\|^{2}}{\|Ry\|^{2}}=\pm
1=\rho.$ (53)

It turns out the that this is preserved under random projections.

######  Proposition D.1.

If $\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\pm 1$ then there exists $\alpha>0$ such that
$x=\pm\alpha y$ (almost surely).

###### Proof.

Since the cosine similarity of $Rx$ and $Ry$ is $\pm 1$, then there is an
$\alpha>0$ such that $Rx=\pm\alpha Ry$. Hence, $w=R(x\mp\alpha y)=0$. Let us
assume $x\mp\alpha y\neq 0$ then $Q(x\mp\alpha y)$ is $q$-dimensional vector
with entries distributed as $N(0,\|x\mp\alpha y\|^{2}/q)$. The probability of
which being a zero vector is $0$. Hence, we have $x=\pm\alpha y$ almost
surely. ∎

Hence, the in the cosine similarity of $\pm 1$ will be preserved under random
projection $Q$.

######  Corollary D.2.

If $\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\pm 1$ almost surely if and only if
$\frac{(x,y)}{\|x\|\|y\|}=\pm 1$.

###### Proof.

$\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\pm 1$, by Proposition D.1, holds if and only if
$x=\pm\alpha y$ for some $\alpha>0$, and, Cauchy-Shcwarz inequality, this
holds if and only if $\frac{(x,y)}{\|x\|\|y\|}=\pm 1$. ∎

Another interesting case is $\rho=0$. The probability of cosine similarity of
two orthogonal vectors to be $0$ under random projections is equal to zero. In
practice, the case of orthogonal vectors might be frequent and we might want
to be able to identify if this was the case before the random projection.

We can provide an exact distribution for this case.

######  Theorem D.3.

If $\rho=0$, then

$\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}\stackrel{{\scriptstyle
d}}{{=}}\frac{T_{q-1}}{\sqrt{q+T_{q-1}^{2}}}$

where $T_{q-1}$ is the Student’s t-distribution with $q-1$ degrees of freedom.

###### Proof.

Using the representation given in Theorem B.1 in equation (39) for $\rho=0$,
we get

$\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\frac{M_{1}}{\sqrt{M_{1}^{2}+M_{2}^{2}+\ldots+M_{q}^{2}}}.$

Let $\phi(s)=\frac{s}{\sqrt{1-s^{2}}}$ and note that

$\displaystyle\phi\left(\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}\right)\sqrt{q}$
$\displaystyle=\frac{M_{1}}{\sqrt{(M_{2}^{2}+\ldots+M_{q}^{2})/q}}$
$\displaystyle=T_{q}.$

Since $\phi^{-1}(h)=\frac{h}{\sqrt{1+h^{2}}}$, we have

$\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\phi^{-1}\left(\frac{T_{q}}{\sqrt{q}}\right).$

∎

######  Corollary D.4.

If $\rho=0$, the random variable

$\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}$

has a $(100\%)(1-\alpha)$-confidence interval given by

$\left[\frac{t_{\alpha/2}(q)}{\sqrt{q+t_{\alpha/2}^{2}(q)}},\frac{t_{1-\alpha/2}(q)}{\sqrt{q+t_{1-\alpha/2}^{2}(q)}}\right].$

###### Proof.

Let $q_{\alpha/2}$ and $q_{1-\alpha/2}$ be the $\alpha/2$-quantile and the
$1-\alpha/2$-quantile of $\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}$, respectively. We have

$\displaystyle 1-\alpha$
$\displaystyle=\mathbb{P}\left(q_{\alpha/2}\leq\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}\leq
q_{1-\alpha/2}\right)$
$\displaystyle=\mathbb{P}\left(\phi(q_{\alpha/2})\sqrt{q-1}\leq\phi\left(\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}\right)\sqrt{q-1}\leq\phi(q_{1-\alpha/2})\sqrt{q}\right)$
$\displaystyle=\mathbb{P}\left(t_{\alpha/2}(q-1)<T_{q-1}<t_{1-\alpha/2}(q-1)\right).$

By setting $\phi(q_{\alpha/2})\sqrt{q-1}=t_{\alpha/2}(q-1)$ and
$\phi(q_{1-\alpha/2})\sqrt{q-1}=t_{1-\alpha/2}(q-1)$, the claim of the
corollary follows. ∎

###  D.2 Central Limit Theorem

In this section we will show that the value of $\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}$
is approximately normally distributed around $\rho$ with a variance
$\frac{(1-\rho^{2})^{2}}{q}$.

######  Theorem D.5.

For non-zero vectors $x$ and $y$ in $\mathbb{R}^{n}$ we have

$\sqrt{q}\left[\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\frac{(x,y)}{\|x\|\|y\|}\right]\stackrel{{\scriptstyle
d}}{{\to}}N\left(0,\left[1-\left(\frac{(x,y)}{\|x\|\|y\|}\right)^{2}\right]^{2}\right),$
(54)

as $q\to\infty$.

Theorem D.5 can be proven using the delta-method technique, but we will use
the representation given in Theorem B.1 to prove it and the following central
limit result.

######  Lemma D.6.

Define $T_{q}=\rho\|N\|+M_{1}\sqrt{1-\rho^{2}}$ and $B_{q}=\|M_{2\ldots q}\|$,
then from (39) we have:

$\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho=(1-\rho^{2})\cdot\frac{(T_{q})^{2}-\rho^{2}B_{q}^{2}}{\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}\cdot\frac{1}{T_{q}+\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}$
(55)

###### Proof.

We have:

$\displaystyle\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho$
$\displaystyle=\frac{T_{q}}{\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}-\rho$
$\displaystyle=\frac{T_{q}-\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}{\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}$
$\displaystyle=\frac{T_{q}-\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}{\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}$
$\displaystyle\cdot\frac{T_{q}+\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}{T_{q}+\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}$
$\displaystyle=\frac{(1-\rho^{2})(T_{q})^{2}-\rho^{2}(1-\rho^{2})B_{q}^{2}}{\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}$
$\displaystyle\cdot\frac{1}{T_{q}+\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}.$

∎

###### Proof of Theorem D.5..

We will use notation and results from Lemma D.6. From the Law of Large
Numbers, we have

$\displaystyle\frac{T_{q}}{\sqrt{q}}$
$\displaystyle=\rho\sqrt{\frac{1}{q}\sum_{j=1}^{q}N_{j}^{2}}+q^{-1/2}M_{1}\sqrt{1-\rho^{2}}$
$\displaystyle\to\rho\cdot 1+0\cdot\sqrt{1-\rho^{2}}=\rho$ (56)

almost surely, as $q\to\infty$. Using the same arguments, we have
$\frac{B_{q}}{\sqrt{q}}\to 1$ almost surely. Hence,

$\displaystyle q^{-1/2}\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}$ (57)
$\displaystyle=\sqrt{\left(\frac{T_{q}}{\sqrt{q}}\right)^{2}+(1-\rho^{2})\left(\frac{B_{q}}{\sqrt{q}}\right)^{2}}$
(58) $\displaystyle\to\sqrt{\rho^{2}+(1-\rho^{2})\cdot 1^{2}}=1$ (59)

almost surely as $q\to\infty$. (56) and (59) now imply

$q^{-1/2}(T_{q}+\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}})\to\rho+\rho=2\rho.$
(60)

Using the Central Limit Theorem, we get

$\frac{B_{q}^{2}-q}{\sqrt{q}}=\frac{1}{\sqrt{q}}\sum_{j=2}^{q}(M_{j}^{2}-1)-\frac{1}{\sqrt{q}}\stackrel{{\scriptstyle
d}}{{\to}}N(0,2),$ $\displaystyle\frac{T_{q}^{2}-q\rho^{2}}{\sqrt{q}}$
$\displaystyle=\rho^{2}\frac{\|N\|^{2}-q}{\sqrt{q}}+2\rho\sqrt{1-\rho^{2}}\frac{\|N\|}{\sqrt{q}}M_{1}$
$\displaystyle+(1-\rho^{2})\frac{M_{1}^{2}}{\sqrt{q}}$
$\displaystyle\stackrel{{\scriptstyle
d}}{{\to}}\rho^{2}N(0,2)+2\rho\sqrt{1-\rho^{2}}\mathcal{N}(0,1)+0$
$\displaystyle=N(0,4\rho^{2}-2\rho^{4}).$

Now, we have

$\displaystyle\sqrt{q}\left[\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\right]$
$\displaystyle=\frac{\frac{T_{q}^{2}-q\rho^{2}}{\sqrt{q}}-\rho^{2}\frac{B_{q}^{2}-q}{\sqrt{q}}}{q^{-1/2}\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}$
$\displaystyle\cdot\frac{(1-\rho^{2})}{q^{-1/2}(T_{q}+\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}})}$
$\displaystyle=\frac{\mathcal{N}(0,4\rho^{2}-2\rho^{4})-\rho^{2}\mathcal{N}(0,2)}{1}\cdot\frac{1-\rho^{2}}{2\rho}$
$\displaystyle=(1-\rho^{2})\frac{\mathcal{N}(0,4\rho^{2}-2\rho^{4})+\mathcal{N}(0,2\rho^{4})}{2\rho}$
$\displaystyle=(1-\rho^{2})\frac{\mathcal{N}(0,4\rho^{2})}{2\rho}=(1-\rho^{2})\mathcal{N}(0,1)$
$\displaystyle=\mathcal{N}(0,(1-\rho^{2})^{2}).$

∎

######  Remark D.7.

For practical purposes, we interpret the result as given in (5) - that for
large $q$ we have the normal distribution with small variance. Hence, it is
likely that the cosine similarity of randomly projected vectors will be close
to the one we would get without the random projection.

Figure 5: Simulated random projection for $n=q=100$, where
$(x,y)/\|x\|/\|y\|=\rho=0.154$

From simulations, see Figure 5, even for $q=100$ we have approximately normal
behavior, but the variance is large and the value might not be close to the
original similarity. The result of Theorem D.5 will be more useful for larger
values of $q$.

The same result holds for the empirical correlation coefficient in linear
regression and in this case it is known that this is not a practical result
(see [35, Example 3.6.]). However, we are in a different setting here and the
numerical simulations suggest that this result is stable and can be used in
practice even for moderately large values of $q$. For example, for values of
$q\geq 6400$ the error will be $\pm 0.05$ with the estimated probability of at
least $0.95$. Concentration results to follow will further confirm this.

###  D.3 Concentration result

Theorem D.5 guarantees that for large $q$ the cosine similarity random
projection will be almost preserved with high probability for any pair of
vectors in $\mathbb{R}^{n}$. However, this approach is not feasible to analyze
the behavior of all pairs of vectors in a given set $y_{1},\ldots,y_{k}$, as
the computation becomes intractable and hard even for small values of $k$. If
we want to get some guarantees that the similarity of all pairs of vectors is
preserved within a small error with high probability under random projection,
we need to use concentration inequalities.

The following theorem is the main result of this subsection.

######  Theorem D.8.

Let $x$ and $y$ be non-zero vectors in $\mathbb{R}^{n}$ and
$\varepsilon\in(0,0.055)$, then

$\mathbb{P}\left(\left|\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\right|\geq\varepsilon(1-\rho^{2})\right)\leq(4+\varepsilon^{2})\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}$

Recall the representation from Theorem B.1: For a given random $R$, for any
vectors $x$ and $y$ in $\mathbb{R}^{n}$ there exist standard $q$-dimensional
Gaussian vectors $N=N^{x,y}$ and $M=M^{x,y}$ such that

$\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\frac{\rho\|N\|+M_{1}\sqrt{1-\rho^{2}}}{\sqrt{(\rho\|N\|+M_{1}\sqrt{1-\rho^{2}})^{2}+(1-\rho^{2})\|M_{2\ldots
q}\|^{2}}}.$

####  D.3.1 Bounds on tails

We will first determine some tail bounds. We start with the following lemma.

######  Lemma D.9.

We have

$\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots
q}\|}>\varepsilon\right)=\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots
q}\|}<-\varepsilon\right)\leq\frac{1}{(1+\varepsilon^{2})^{\frac{q-1}{2}}}$

###### Proof.

Note that $M_{1}\sim\mathcal{N}(0,1)$ and $\|M_{2\ldots
q}\|^{2}\sim\chi^{2}(q-1)$ are independent. The equality
$\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots
q}\|}>\varepsilon\right)=\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots
q}\|}<-\varepsilon\right)$ follows from the fact that both $M_{1}$ and
$-M_{1}$ have the same distribution. Further, by Markov’s inequality we get

$\displaystyle\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots
q}\|}>\varepsilon\right)$
$\displaystyle=\mathbb{E}[\mathbb{P}\left(M_{1}>\varepsilon\|M_{2\ldots
q}\||\|M_{2\ldots q}\|\right)]$
$\displaystyle\leq\mathbb{E}[\exp\left(-\varepsilon^{2}\|M_{2\ldots
q}\|^{2}/2\right)]$
$\displaystyle=\frac{1}{(1+\varepsilon^{2})^{\frac{q-1}{2}}}.$

The last equality follows from the fact that $\|M_{2\ldots q}\|^{2}$ has the
$\chi^{2}(q-1)$ distribution and the Laplace transform for this distribution.
∎

######  Lemma D.10.

For $\varepsilon>0$ we have:

$\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots
q}\|}>\sqrt{1+\varepsilon}\right)\leq\sqrt{1+\frac{\varepsilon}{2}}\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right]^{-\frac{q}{2}}$
(61) $\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots
q}\|}<\sqrt{1-\varepsilon}\right)\leq\sqrt{1-\frac{\varepsilon}{2}}\left[1+\frac{\varepsilon^{2}}{4(1-\varepsilon)}\right]^{-\frac{q}{2}}$
(62)

###### Proof.

Using Markov inequality, we have for all $\lambda\in(0,1/2)$:

$\displaystyle\mathbb{P}\left(\frac{\|N\|^{2}}{\|M_{2\ldots
q}\|^{2}}>1+\varepsilon\right)$
$\displaystyle=\mathbb{P}(\lambda\|N\|^{2}>\lambda(1+\varepsilon)\|M_{2\ldots
q}\|^{2})$
$\displaystyle=\mathbb{P}(\lambda\|N\|^{2}-\lambda(1+\varepsilon)\|M_{2\ldots
q}\|^{2}>0)$
$\displaystyle=\mathbb{P}(\exp[\lambda\|N\|^{2}-\lambda(1+\varepsilon)\|M_{2\ldots
q}\|^{2}]>1)$
$\displaystyle\leq\mathbb{E}[e^{\lambda\|N\|^{2}-\lambda(1+\varepsilon)\|M_{2\ldots
q}\|^{2}}]$
$\displaystyle\leq\frac{1}{(1-2\lambda)^{\frac{q}{2}}}\cdot\frac{1}{(1+2(1+\varepsilon)\lambda)^{\frac{q-1}{2}}}.$

Note that,

$\displaystyle(1-2\lambda)(1+2(1+\varepsilon)\lambda)$
$\displaystyle=1+2\varepsilon\lambda-4(1+\varepsilon)\lambda^{2}$
$\displaystyle=1+\frac{\varepsilon^{2}}{4(1+\varepsilon)}-\left(\frac{\varepsilon}{2\sqrt{1+\varepsilon}}-2\sqrt{1+\varepsilon}\lambda\right)^{2}$

By setting $\lambda=\frac{\varepsilon}{4(1+\varepsilon)}$ we get

$\displaystyle\frac{1}{(1-2\lambda)^{\frac{q}{2}}}\cdot\frac{1}{(1+2(1+\varepsilon)\lambda)^{\frac{q-1}{2}}}$
$\displaystyle=(1+2(1+\varepsilon)\lambda)^{\frac{1}{2}}[(1-2\lambda)(1+2(1+\varepsilon)\lambda)]^{-\frac{q}{2}}$
$\displaystyle=\sqrt{1+\frac{\varepsilon}{2}}\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right]^{-\frac{q}{2}}$

This proves (61). In the similar way we prove (62):

$\displaystyle\mathbb{P}\left(\frac{\|N\|^{2}}{\|M_{2\ldots
q}\|^{2}}<1-\varepsilon\right)$
$\displaystyle=\mathbb{P}(\lambda\|N\|^{2}<\lambda(1-\varepsilon)\|M_{2\ldots
q}\|^{2})$ $\displaystyle=\mathbb{P}(\lambda(1-\varepsilon)\|M_{2\ldots
q}\|^{2}-\lambda\|N\|^{2}>0)$
$\displaystyle=\mathbb{P}(\exp[\lambda(1-\varepsilon)\|M_{2\ldots
q}\|^{2}-\lambda\|N\|^{2}]>1)$
$\displaystyle\leq\mathbb{E}[e^{\lambda(1-\varepsilon)\|M_{2\ldots
q}\|^{2}-\lambda\|N\|^{2}}]$
$\displaystyle\leq\frac{1}{(1+2\lambda)^{\frac{q}{2}}}\cdot\frac{1}{(1-2(1-\varepsilon)\lambda)^{\frac{q-1}{2}}}.$

Note that,

$\displaystyle(1+2\lambda)(1-2(1-\varepsilon)\lambda)$
$\displaystyle=1+2\varepsilon\lambda-4(1-\varepsilon)\lambda^{2}$
$\displaystyle=1+\frac{\varepsilon^{2}}{4(1-\varepsilon)}-\left(\frac{\varepsilon}{2\sqrt{1-\varepsilon}}-2\sqrt{1-\varepsilon}\lambda\right)^{2}$

By setting $\lambda=\frac{\varepsilon}{4(1-\varepsilon)}$ we get

$\displaystyle\frac{1}{(1+2\lambda)^{\frac{p}{2}}}\cdot\frac{1}{(1-2(1-\varepsilon)\lambda)^{\frac{q-1}{2}}}$
$\displaystyle=(1-2(1-\varepsilon)\lambda)^{\frac{1}{2}}[(1+2\lambda)(1-2(1-\varepsilon)\lambda)]^{-\frac{q}{2}}$
$\displaystyle=\sqrt{1-\frac{\varepsilon}{2}}\left[1+\frac{\varepsilon^{2}}{4(1-\varepsilon)}\right]^{-\frac{q}{2}}$

This completes the proof. ∎

######  Corollary D.11.

We have

$\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots
q}\|}>\sqrt{1+\varepsilon}\right)+\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots
q}\|}<\sqrt{1-\varepsilon}\right)\leq
2\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right]^{-\frac{q}{2}}$ (63)

###### Proof.

Using (61), (62) and the Cauchy-Schwarz inequality we have

$\displaystyle\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots
q}\|}>\sqrt{1+\varepsilon}\right)$
$\displaystyle+\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots
q}\|}<\sqrt{1-\varepsilon}\right)$
$\displaystyle\leq\sqrt{1+\frac{\varepsilon}{2}}\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right]^{-\frac{q}{2}}$
$\displaystyle+\sqrt{1-\frac{\varepsilon}{2}}\left[1+\frac{\varepsilon^{2}}{4(1-\varepsilon)}\right]^{-\frac{q}{2}}$
$\displaystyle\leq\sqrt{1+\frac{\varepsilon}{2}+1-\frac{\varepsilon}{2}}$
$\displaystyle\cdot\sqrt{\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right]^{-q}+\left[1+\frac{\varepsilon^{2}}{4(1-\varepsilon)}\right]^{-q}}$
$\displaystyle\leq\sqrt{2}\cdot\sqrt{2\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right]^{-q}}$
$\displaystyle=2\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right]^{-\frac{q}{2}}$

∎

####  D.3.2 Proof of concentration result

We need one more lemma to have everything for the proof.

######  Lemma D.12.

Given $\varepsilon\in(0,0.08]$, $\left|\frac{M_{1}}{\|M_{2\ldots
q}\|}\right|<\varepsilon/2$ and
$\sqrt{1-\varepsilon}<\frac{\|N\|}{\|M_{2\ldots q}\|}<\sqrt{1+\varepsilon}$,
then

$\left|\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\right|\leq\frac{\varepsilon}{\sqrt{2}}(1-\rho^{2}).$

###### Proof.

Recall, we used $\phi(s)=\frac{s}{\sqrt{1-s^{2}}}$ and let us define
$\psi(h):=\phi^{-1}(h)=\frac{h}{\sqrt{1+h^{2}}}$. Note that
$\psi^{\prime}(h)=\frac{1}{(1+h^{2})^{3/2}}>0$, hence $\psi$ is an increasing
function. We have

$\displaystyle\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}$
$\displaystyle=\psi\left(\frac{\rho\|N\|+M_{1}\sqrt{1-\rho^{2}}}{\|M_{2\ldots
q}\|\sqrt{1-\rho^{2}}}\right)$
$\displaystyle=\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\frac{\|N\|}{\|M_{2\ldots
q}\|}+\frac{M_{1}}{\|M_{2\ldots q}\|}\right).$

and

$\rho=\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right).$

We will prove the claim for the case when $\rho\geq 0$; the other case is
proven in a similar way. Using non-negativity of $\rho$ and the fact that
$\psi$ is increasing, we have

$\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\right)-\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right)\\\
\leq\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\leq\\\
\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1+\varepsilon}+\frac{\varepsilon}{2}\right)-\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right).$
(64)

Using Lemma E.10 (a) we can estimate the upper bound:

$\displaystyle\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1+\varepsilon}+\frac{\varepsilon}{2}\right)-\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right)$
$\displaystyle\leq\left(1+\frac{\rho^{2}}{1-\rho^{2}}\right)^{-3/2}$
$\displaystyle\cdot\left[\frac{\rho}{\sqrt{1-\rho^{2}}}(\sqrt{1+\varepsilon}-1)+\frac{\varepsilon}{2}\right]$
$\displaystyle\leq(1-\rho^{2})^{3/2}\left[\frac{\rho}{\sqrt{1-\rho^{2}}}\frac{\varepsilon}{2}+\frac{\varepsilon}{2}\right]$
$\displaystyle\leq(1-\rho^{2})\frac{\varepsilon(\rho+\sqrt{1-\rho^{2}})}{2}.$
(65)

Since $\rho+\sqrt{1-\rho^{2}}\leq\sqrt{2}$, we have

$\eqref{eq:ineq_cos_1a}\leq(1-\rho^{2})\frac{\varepsilon}{\sqrt{2}}.$ (66)

To prove the lower bound in (64), we first need to note that
$\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}$ can
be negative or very close to $0$. For that reason, we will have to consider
two cases: $\rho^{2}\leq\varepsilon$ or $\rho^{2}>\varepsilon$.

If $\rho^{2}>\varepsilon$,

$\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}\geq\sqrt{\varepsilon}>\varepsilon.$
(67)

we have

$\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\geq\frac{\varepsilon}{2}>0,$
(68)

and in particular

$\rho\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\sqrt{1-\rho^{2}}>0.$ (69)

Let

$A:=\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right)=\rho>0,$

and

$B:=\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\right)>0.$

From (68) we have $B\geq 0$, and hence since $\psi$ is an increasing function
we have $A>B>0$.

We obtain

$\displaystyle A-B=\rho$
$\displaystyle-\frac{\rho\sqrt{1-\varepsilon}-\varepsilon/2\sqrt{1-\rho^{2}}}{\sqrt{(\rho\sqrt{1-\varepsilon}-\varepsilon/2\sqrt{1-\rho^{2}})^{2}+(1-\rho^{2})}}$
$\displaystyle\stackrel{{\scriptstyle\textrm{Lemma}\
\ref{lemma:denominatorBounds}.}}{{\leq}}\rho-\frac{\rho\sqrt{1-\varepsilon}-\varepsilon/2\sqrt{1-\rho^{2}}}{\sqrt{1-\varepsilon\rho^{2}}}$
$\displaystyle=\rho\underbrace{\left(1-\frac{\sqrt{1-\varepsilon}}{\sqrt{1-\varepsilon\rho^{2}}}\right)}_{\leq
0}+\frac{\varepsilon\sqrt{1-\rho^{2}}}{2\sqrt{1-\varepsilon\rho^{2}}}$
$\displaystyle\leq\frac{\varepsilon\sqrt{1-\rho^{2}}}{2\sqrt{1-\varepsilon\rho^{2}}}\leq\frac{\varepsilon\sqrt{1-\rho^{2}}}{2\sqrt{1-\varepsilon\rho^{2}}}\cdot\frac{\sqrt{1-\rho^{2}}}{\sqrt{1-\varepsilon\rho^{2}}}$
$\displaystyle\leq\frac{\varepsilon(1-\rho^{2})}{2(1-\varepsilon\rho^{2})}\leq\frac{\varepsilon(1-\rho^{2})}{2(1-\varepsilon)}$
(70)

Since $\varepsilon\in(0,\frac{1}{4}]$, we have
$\frac{1}{2(1-\varepsilon)}\leq\frac{2}{3}<\frac{\sqrt{2}}{2}=\frac{1}{\sqrt{2}}$
and hence

$\eqref{eq:ineq_cos_2a}\leq\frac{\varepsilon(1-\rho^{2})}{\sqrt{2}}$ (71)

On the other hand, if $\rho^{2}\leq\varepsilon$, Lemma E.10 (b) implies:

$\displaystyle\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right)-\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\right)$
$\displaystyle\leq\left[\frac{\rho}{\sqrt{1-\rho^{2}}}(1-\sqrt{1-\varepsilon})+\frac{\varepsilon}{2}\right]$
$\displaystyle\leq\left[\frac{\rho}{\sqrt{1-\rho^{2}}}\cdot\frac{\varepsilon}{1+\sqrt{1-\varepsilon}}+\frac{\varepsilon}{2}\right]$
$\displaystyle\leq\varepsilon\left[\frac{\rho}{\sqrt{1-\rho^{2}}}\frac{1}{1+\sqrt{1-\varepsilon}}+\frac{1}{2}+\frac{\rho^{2}}{\sqrt{2}}\right]$
$\displaystyle-\frac{\varepsilon}{\sqrt{2}}\rho^{2}.$ (72)

Since $\rho^{2}\leq\varepsilon$, we have $\rho\in[0,\varepsilon]$ and

$\displaystyle\frac{\rho}{\sqrt{1-\rho^{2}}}\frac{1}{1+\sqrt{1-\varepsilon}}+\frac{1}{2}+\frac{\rho^{2}}{\sqrt{2}}$
$\displaystyle\leq\frac{\sqrt{\varepsilon}}{\sqrt{1-\varepsilon}+1-\varepsilon}+\frac{1}{2}+\frac{\varepsilon}{\sqrt{2}}.$

This expression is increasing for $\varepsilon\in(0,1)$, so

$\displaystyle\leq\left.\frac{\sqrt{\varepsilon}}{\sqrt{1-\varepsilon}+1-\varepsilon}+\frac{1}{2}+\frac{\varepsilon}{\sqrt{2}}\right|_{\varepsilon=0.08}$
$\displaystyle\approx 0.70708<\frac{1}{\sqrt{2}}.$

Therefore,

$\eqref{eq:ineq_cos_3a}\leq\frac{\varepsilon(1-\rho^{2})}{\sqrt{2}}$ (73)

Finally, the inequalities (66), (71) and (73) prove the claim. ∎

###### Proof of Theorem D.8.

Since $\varepsilon\in(0,0.055]$, we have $\varepsilon\sqrt{2}\in(0,0.08]$,
then by Lemma D.12 we have

$\displaystyle\mathbb{P}\left(\left|\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\right|\geq\varepsilon(1-\rho^{2})\right)$
$\displaystyle=\mathbb{P}\left(\left|\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\right|\geq\frac{\varepsilon\sqrt{2}}{\sqrt{2}}(1-\rho^{2})\right)$
$\displaystyle\leq\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots
q}\|}>\frac{\varepsilon\sqrt{2}}{2}\right)$
$\displaystyle+\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots
q}\|}<-\frac{\varepsilon\sqrt{2}}{2}\right)$
$\displaystyle+\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots
q}\|}>\sqrt{1+\varepsilon\sqrt{2}}\right)$
$\displaystyle+\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots
q}\|}<\sqrt{1-\varepsilon\sqrt{2}}\right).$

Using Lemma D.9 and Corollary 63 we have

$\displaystyle\leq
2\left[1+\frac{\varepsilon^{2}}{2}\right]^{-\frac{q-1}{2}}+2\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}$
$\displaystyle=(2+\varepsilon^{2})\left[1+\frac{\varepsilon^{2}}{2}\right]^{-\frac{q}{2}}$
$\displaystyle+2\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}$
$\displaystyle\leq(2+\varepsilon^{2})\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}$
$\displaystyle+2\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}$
$\displaystyle=(4+\varepsilon^{2})\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}.$

∎

###  D.4 Johnson-Lindenstrauss-type Result

######  Theorem D.13.

Let $\varepsilon\in(0,0.05]$, $\delta\in(0,1)$ and $y_{1},\ldots,y_{k}$ be
non-zero vectors in $\mathbb{R}^{n}$. If

$q\geq\frac{2\ln\left[\frac{2k(k-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{\delta}\right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]}$
(74)

then, with probability $1-\delta$, the inequality

$\left|\frac{(Ry_{j},Ry_{i})}{\|Ry_{j}\|\|Ry_{i}\|}-\frac{(y_{j},y_{i})}{\|y_{j}\|\|y_{i}\|}\right|\leq\varepsilon(1-\rho^{2})$

holds for all $i<j$.

###### Proof.

Define

$W_{ij}:=\left(\left|\frac{(Ry_{j},Ry_{i})}{\|Ry_{j}\|\|Ry_{i}\|}-\frac{(y_{j},y_{i})}{\|y_{j}\|\|y_{i}\|}\right|\leq\varepsilon(1-\rho^{2})\right).$

To prove the theorem, it suffices to show that
$\mathbb{P}\left(\bigcup_{i<j}W_{ij}^{c}\right)<\delta$.

By Theorem D.8, we have

$\displaystyle\mathbb{P}\left(\bigcup_{i<j}W_{ij}^{c}\right)$
$\displaystyle=\sum_{i<j}\mathbb{P}\left(W_{ij}^{c}\right)$
$\displaystyle=\frac{k(k-1)}{2}\cdot
4\left(1+\frac{\varepsilon^{2}}{4}\right)$
$\displaystyle\cdot\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}.$

This expression is less than $\delta$ by the choice of $q$ in (76). ∎

###  D.5 Result comparison analysis

In this section, we state Lemma 5 from [2], which gives a similar result to
Theorem D.8, and compare the two results.

######  Lemma D.14.

For $x$ and $y$ non-zero vectors in $\mathbb{R}^{n}$ and for every
$\eta\in(0,1/2)$, we have

$-\frac{\eta}{1-\eta}(1-\rho)\leq\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\leq\frac{\eta}{1+\eta}(1-\rho)$

if $\rho\leq-\varepsilon$,

$-\frac{\eta}{1-\eta}(1-\rho)\leq\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\leq\frac{\eta}{1-\eta}(1+\rho)$

if $-\varepsilon\leq\rho\leq\varepsilon$,

$-\frac{\eta}{1+\eta}(1+\rho)\leq\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\leq\frac{\eta}{1-\eta}(1+\rho)$

if $\rho\geq\varepsilon$. Moreover, the inequality holds true with probability
at least $1-8e^{-\frac{q}{4}(\eta^{2}-\eta^{2})}.$

######  Remark D.15.

We observe that Lemma D.14 does not capture the fact that when $\rho=\pm 1$,
the random projection preserves the cosine similarity, as discussed in §D.1.

Also, the role of $\eta$ is unclear. If we set
$\varepsilon=\max\\{\frac{\eta}{1-\eta},\frac{\eta}{1+\eta}\\}=\frac{\eta}{1-\eta}$,
the result can be rewritten as

$-\varepsilon(1+|\rho|)\leq\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\leq\varepsilon(1+|\rho|),$
(75)

with probability at least
$1-8e^{-\frac{q}{4}\cdot\frac{\varepsilon^{2}}{(1+\varepsilon)^{2}}}$.

We note that the inequality (75) is less precise than the one provided by
Theorem D.8.

Moreover, by Lemma E.9, we have
$\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}\leq
e^{-\frac{q}{4}\cdot\frac{\varepsilon^{2}}{(1+\varepsilon)^{2}}}$. Therefore,
the inequality in Theorem D.8 also holds with higher probability.

We remark that Theorem D.8 requires $\varepsilon\in(0,0.05]$, but this is a
reasonable absolute error for cosine similarity, which ranges from $0$ to $1$.

We will see how the dimension selection in Theorem D.13 for cosine similarity
compares with the similar result in original Johnson-Lindenstrauss Lemma. The
following version is based on Theorem 2.13 and Remark 2.11 from [5] and we
present it without proof.

######  Theorem D.16.

Let $\varepsilon,\delta\in(0,1)$, and $x_{1},\ldots,x_{k}$ be non-zero vectors
in $\mathbb{R}^{n}$. If

$q\geq\frac{4}{\varepsilon^{2}}\log\left[\frac{k^{2}}{\delta}\right]$ (76)

then, with probability at least $1-\delta$, the inequality

$(1-\varepsilon)\|x_{i}-x_{j}\|^{2}\leq\|R(x_{i}-x_{j})\|^{2}\leq(1+\varepsilon)\|x_{i}-x_{j}\|^{2}$
(77)

holds for all $i<j$.

In the following we will use the notation $f\sim g$ that will denote

$\lim_{\varepsilon\to 0^{+}}\frac{f(\varepsilon)}{g(\varepsilon)}=1.$

This is a standard tool to analyze asymptotic behavior.

######  Proposition D.17.

For a fixed, $\delta$ and $k$ we have

$\frac{2\ln\left[\frac{2k(k-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{\delta}\right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]}\sim\frac{4}{\varepsilon^{2}}\ln\left[\frac{2k(k-1)}{\delta}\right].$

###### Proof.

Using L’Hospital’s rule one can show $\lim_{x\to 0^{+}}\frac{\log(1+x)}{x}=1$,
hence

$\lim_{\varepsilon\to
0^{+}}\frac{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]}{\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}}=1.$
(78)

Simple limit calculus gives us

$\lim_{\varepsilon\to
0^{+}}\frac{\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}}{\frac{\varepsilon^{2}}{2}}=\lim_{\varepsilon\to
0^{+}}\frac{1}{1+\varepsilon\sqrt{2}}=1.$ (79)

Hence, multiplying expressions in (78) and (79) we get:

$\lim_{\varepsilon\to
0^{+}}\frac{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]}{\frac{\varepsilon^{2}}{2}}=1.$
(80)

Furthermore, by continuity of the function $\ln$ we have

$\lim_{\varepsilon\to
0^{+}}\ln\left[\frac{2k(k-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{\delta}\right]=\ln\left[\frac{2k(k-1)}{\delta}\right].$
(81)

The claim now follows from (80) and (81). ∎

The comparison in Proposition D.17 tells us that the dimension $q$ will be of
the same order but slightly higher. This is illustrated on Figure 6.

Figure 6: Simulated random projection for $k=10000000$, $\delta=0.05$ the
upper (Qed) curve represents the graph of
$\varepsilon\mapsto\frac{2\ln\left[\frac{2k(k-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{\delta}\right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]}$
(minimum value of $q$ for cosine similarity) and the lower (blue) curve
$\varepsilon\mapsto\frac{4}{\varepsilon^{2}}\ln\left[\frac{k^{2}}{\delta}\right]$
(minimum value of $q$ for Johnson-Lindenstrauss Lemma). We can see that the
two curves are very close.

##  Appendix E Technical inequalities and concentration results

In this appendix we placed some technical inequalities we used in other parts
of the text, so the reader can verify the that they hold.

###  E.1 Useful concentration inequalities

In this paper we will depend on the results from concentration inequality
theory. The approach in this paper is adapted based on the book [5]. In this
subsection we adpated results from Chapter 2 of the book.

######  Theorem E.1.

Let $X$ be a random variable such that $v>0$, $c>0$ we have

$\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{v\lambda^{2}}{2(1-c\lambda)}$
(82)

for every $\lambda\in(0,c^{-1})$. Then for $t\geq 0$ we have

$\mathbb{P}(X-\mathbb{E}X>t)\leq\exp\left(\frac{-t^{2}}{2(v+ct)}\right)$

###### Proof.

Using Markov inequality, for $\lambda\in(0,c^{-1})$ we have

$\displaystyle\mathbb{P}(X-\mathbb{E}X>t)$
$\displaystyle\leq\frac{\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]}{e^{\lambda
t}}$ $\displaystyle\leq\exp\left(\frac{v\lambda^{2}}{2(1-c\lambda)}-\lambda
t\right)$ $\displaystyle=\exp\left[-\sup_{\lambda\in(0,c^{-1})}\left(\lambda
t-\frac{v\lambda^{2}}{2(1-c\lambda)}\right)\right]$

Using usual calculus techniques we get (see Lemma E.7 for details)

$\sup_{\lambda\in(0,c^{-1})}\left(\lambda
t-\frac{v\lambda^{2}}{2(1-c\lambda)}\right)=\frac{v}{c^{2}}h\left(\frac{ct}{v}\right),$

where $h(s)=1+s-\sqrt{1+2s}$. By Lemma E.5 we have
$h(s)\geq\frac{s^{2}}{2(1+s)}$ for $s>0$ and the claim follows. ∎

The following Corollary explains what happens when $c=0$ in (82).

######  Theorem E.2.

Let $X$ be a random variable such that $v>0$ we have

$\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{v\lambda^{2}}{2}$ (83)

for every $\lambda\geq 0$. Then for $t\geq 0$ we have

$\mathbb{P}(X-\mathbb{E}X>t)\leq\exp\left(\frac{-t^{2}}{2v}\right).$

###### Proof.

Using Markov inequality, for $\lambda\geq 0$ we have

$\displaystyle\mathbb{P}(X-\mathbb{E}X>t)$
$\displaystyle\leq\frac{\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]}{e^{\lambda
t}}$ $\displaystyle\leq\exp\left(\frac{v\lambda^{2}}{2}-\lambda t\right)$
$\displaystyle=\exp\left(\frac{v\lambda^{2}}{2}-\lambda
t+\frac{t^{2}}{2v}-\frac{t^{2}}{2v}\right)$
$\displaystyle=\exp\left(\frac{1}{2}\left(\lambda
v^{1/2}-tv^{-1/2}\right)^{2}-\frac{t^{2}}{2v}\right).$

Setting $\lambda=t/v$ the claim follows. ∎

######  Proposition E.3.

If for a given $p>0$ and $c>0$ the inequality

$\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{e^{-\lambda
p}}{(1-c\lambda)^{p/c}}$ (84)

holds for all $\lambda<c^{-1}$, then the following claims hold:

(a) For all $\lambda\in(0,c^{-1})$

$\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{pc\lambda^{2}}{2(1-c\lambda)}.$
(85)

(b) For all $\lambda\leq 0$

$\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{pc\lambda^{2}}{2}.$ (86)

###### Proof.

(a) Using the inequality $-\log(1-s)-s\leq\frac{s^{2}}{2(1-s)}$ for
$s\in(0,1)$ (see Lemma E.6 (a)) we have:

$\displaystyle\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]$
$\displaystyle\leq-\lambda p-\frac{p}{c}\log(1-c\lambda)$
$\displaystyle=\frac{p}{c}(-\log(1-c\lambda)-c\lambda)$
$\displaystyle\leq\frac{p}{c}\cdot\frac{(c\lambda)^{2}}{2(1-c\lambda)}$
$\displaystyle=\frac{pc\lambda^{2}}{2(1-c\lambda)}.$

(b) Using inequality $-\log(1-s)-s\leq\frac{s^{2}}{2}$ for $s<0$ (see Lemma
E.6 (b)) we have:

$\displaystyle\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]$
$\displaystyle\leq-\lambda p-\frac{p}{c}\log(1-c\lambda)$
$\displaystyle=\frac{p}{c}(-\log(1-c\lambda)-c\lambda)$
$\displaystyle\leq\frac{p}{c}\cdot\frac{(c\lambda)^{2}}{2}$
$\displaystyle=\frac{pc\lambda^{2}}{2}.$

∎

######  Corollary E.4.

If for a given $p>0$ and $c>0$ we have

$\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{e^{-\lambda
p}}{(1-c\lambda)^{p/c}}$ (87)

for all $\lambda<c^{-1}$, then for all $t\geq 0$

$\mathbb{P}(X-\mathbb{E}X>t)\leq\exp\left(\frac{-t^{2}}{2(pc+ct)}\right),$
(88)

and

$\mathbb{P}(X-\mathbb{E}X<-t)\leq\exp\left(\frac{-t^{2}}{2pc}\right).$ (89)

###### Proof.

From Proposition E.3 we know that (85) holds. Now, by Theorem E.1, inequality
(88) holds.

From Proposition E.3 we know that (86) holds. If we substitute
$\lambda\mapsto-\lambda$ and $X\mapsto-X$ in (86) we have

$\log\mathbb{E}[e^{\lambda(-X+\mathbb{E}X)}]\leq\frac{pc\lambda^{2}}{2}$

for $\lambda\geq 0$. Hence, using Theorem E.3 we get (89). ∎

###  E.2 Technical inequalities

######  Lemma E.5.

For $s\geq 0$ we have

$1+s-\sqrt{1+2s}\geq\frac{s^{2}}{2(1+s)}.$

###### Proof.

For $s>0$ we have:

$\displaystyle 1+s-\sqrt{1+2s}$
$\displaystyle=(1+s-\sqrt{1+2s})\cdot\frac{1+s+\sqrt{1+2s}}{1+s+\sqrt{1+2s}}$
$\displaystyle=\frac{(1+s)^{2}-1+2s}{1+s+\sqrt{1+2s}}$
$\displaystyle=\frac{s^{2}}{1+s+\sqrt{1+2s}}$
$\displaystyle\geq\frac{s^{2}}{2(1+s)}.$

Tha last inequality follows from the fact that
$1+s=\sqrt{1+2s+s^{2}}>\sqrt{1+2s}$. ∎

######  Lemma E.6.

(a) For $s\in(0,1)$ we have $-\log(1-s)-s\leq\frac{s^{2}}{2(1-s)}$.

(b) For $s<0$ we have $-\log(1-s)-s\leq\frac{s^{2}}{2}$.

###### Proof.

Not that for $f(s)=-\log(1-s)-s$ we have
$f^{\prime}(s)=\frac{1}{1-s}-1=\frac{s}{1-s}$. Hence, in the case of (a), it
follows for $s\in(0,1)$

$\displaystyle-\log(1-s)-s$
$\displaystyle=f(s)-f(0)=\int_{0}^{s}f^{\prime}(t)\,dt$
$\displaystyle=\int_{0}^{s}\frac{t}{1-t}\,dt\leq\int_{0}^{s}\frac{t}{1-s}\,dt$
$\displaystyle=\frac{1}{1-s}\int_{0}^{s}t\,dt=\frac{s^{2}}{2(1-s)}.$

In the case of (b), for $s<0$ we can apply a similar argument:

$\displaystyle-\log(1-s)-s$
$\displaystyle=f(s)-f(0)=\int_{0}^{s}f^{\prime}(t)\,dt$
$\displaystyle=\int_{0}^{s}\frac{t}{1-t}\,dt\leq\int_{s}^{0}\frac{-t}{1-t}\,dt$
$\displaystyle\leq\int_{s}^{0}-t\,dt=\frac{s^{2}}{2}.$

∎

######  Lemma E.7.

For a given $t>0$, $v>0$ and $c>0$ the function

$f(\lambda)=\lambda t-\frac{v\lambda^{2}}{2(1-c\lambda)}$

has a maximum on interval $(0,c^{-1})$ at point
$\lambda_{max}=\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v+2tc}}.$ and it equals

$\frac{v}{c^{2}}\left(1+\frac{tc}{v}-\sqrt{1+2\cdot\frac{tc}{v}}\right).$

###### Proof.

When we take the first derivative we get

$f^{\prime}(\lambda)=t-\frac{v\lambda}{(1-c\lambda)}-\frac{vc\lambda^{2}}{2(1-c\lambda)^{2}}.$

Setting $f^{\prime}(\lambda)=0$ and using the substitution
$x=\frac{\lambda}{(1-c\lambda)}$, we get

$-\frac{vc}{2}\cdot x^{2}-vx+t=0.$

Solving thi quadratic equation by $x$ we get

$x_{1,2}=-\frac{1}{c}\pm\sqrt{\frac{1}{c^{2}}+\frac{2t}{vc}}.$

Since the solution needs to be non-negative,

$\displaystyle x$
$\displaystyle=-\frac{1}{c}+\sqrt{\frac{1}{c^{2}}+\frac{2t}{vc}}$
$\displaystyle=-\frac{1}{c}+\sqrt{\frac{v}{vc^{2}}+\frac{2tc}{vc^{2}}}$
$\displaystyle=\frac{-\sqrt{v}+\sqrt{v+2tc}}{c\sqrt{v}}$
$\displaystyle=\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v}}.$

Now, when we calcualte $\lambda$ from $x$, we get

$\lambda_{max}=\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v+2tc}}.$

Note that, $\lambda_{max}$ is the minimum since $f^{\prime}$ is a strictly
decreasing function on $(0,c^{-1})$. The value of the minimum is

$\displaystyle f^{\prime}(\lambda_{max})$
$\displaystyle=\lambda_{max}\left(t-\frac{v}{2}\cdot\frac{\lambda_{max}}{1-c\lambda_{max}}\right)$
$\displaystyle=\lambda_{max}\left(t-\frac{v}{2}\cdot x\right)$
$\displaystyle=\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v+2tc}}\left(t-\frac{v}{2}\cdot\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v}}\right)$
$\displaystyle=\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v+2tc}}\left(t-\frac{\sqrt{v}\sqrt{v+2tc}-v}{2c}\right)$
$\displaystyle=\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v+2tc}}\cdot\frac{2tc+v-\sqrt{v}\sqrt{v+2tc}}{2c}$
$\displaystyle=\frac{(\sqrt{v+2tc}-\sqrt{v})}{c}\cdot\frac{\sqrt{v+2tc}-\sqrt{v}}{2c}$
$\displaystyle=\frac{(\sqrt{v+2tc}-\sqrt{v})^{2}}{2c^{2}}$
$\displaystyle=\frac{2v+2tc-2\sqrt{v^{2}+2vtc}}{2c^{2}}$
$\displaystyle=\frac{v}{c^{2}}\left(1+\frac{tc}{v}-\sqrt{1+2\cdot\frac{tc}{v}}\right)$

∎

######  Lemma E.8.

For $\varepsilon\in(0,1)$ and $\rho^{2}\in[\varepsilon,1]$ we have

$(\rho\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\sqrt{1-\rho^{2}})^{2}+1-\rho^{2}\leq
1-\varepsilon\rho^{2}.$

###### Proof.

It is easy to show that $\rho\geq\varepsilon$ and $1-\varepsilon\geq
1-\rho^{2}$, hence

$0\leq\rho\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\sqrt{1-\rho^{2}}\leq\rho\sqrt{1-\varepsilon}.$
(90)

Now, we have:

$\displaystyle(\rho\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\sqrt{1-\rho^{2}})^{2}+1-\rho^{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:denominatorBounds1}}}{{\leq}}(\rho\sqrt{1-\varepsilon})^{2}+1-\rho^{2}$
$\displaystyle=1-\varepsilon\rho^{2}$

∎

######  Lemma E.9.

For $\varepsilon\in(0,1)$ we have

$\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]^{-\frac{p}{2}}\leq
e^{-\frac{p}{4}\cdot\frac{\varepsilon^{2}}{(1+\varepsilon)^{2}}}$

###### Proof.

Using Lemma E.6(b) we have

$\displaystyle\log\left(\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]^{-\frac{p}{2}}\right)$
$\displaystyle=-\frac{p}{2}\cdot\log\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]$
$\displaystyle\leq\frac{p}{2}\left[-\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}+\frac{1}{2}\left(\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right)^{2}\right]$
(91)

Looking at the difference:

$\displaystyle\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}-\frac{\varepsilon^{2}}{2(1+\varepsilon)^{2}}$
$\displaystyle=\frac{\varepsilon^{2}[(1+\varepsilon)^{2}-(1+\varepsilon\sqrt{2})]}{2(1+\varepsilon)^{2}(1+\varepsilon\sqrt{2})}$
$\displaystyle=\frac{\varepsilon^{2}[\varepsilon(2-\sqrt{2})+\varepsilon^{2}]}{2(1+\varepsilon)^{2}(1+\varepsilon\sqrt{2})}$
$\displaystyle\geq\frac{\varepsilon^{2}[\varepsilon(2-\sqrt{2})+\varepsilon^{2}]}{2(1+\varepsilon)^{2}(1+\varepsilon\sqrt{2})}$
$\displaystyle\geq\frac{\varepsilon^{3}(2-\sqrt{2})[1+\frac{\varepsilon}{2-\sqrt{2}}]}{2(1+\varepsilon)^{2}(1+\varepsilon\sqrt{2})}$
$\displaystyle\geq\frac{\varepsilon^{3}(2-\sqrt{2})[1+\varepsilon\sqrt{2}]}{2(1+\varepsilon)^{2}(1+\varepsilon\sqrt{2})}$
$\displaystyle\geq\frac{\varepsilon^{3}\cdot\frac{1}{2}}{2(1+\varepsilon)^{2}}=\frac{\varepsilon^{3}}{4(1+\varepsilon)^{2}}$
$\displaystyle\geq\frac{1}{2}\left(\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right)^{2}$

Hence, we have

$\eqref{eq:appLogLemma}\leq-\frac{p}{4}\cdot\frac{\varepsilon^{2}}{(1+\varepsilon)^{2}}.$

∎

###  E.3 Special Case of Mean Value Theorem

######  Lemma E.10.

Let $\psi(h)=\frac{h}{\sqrt{1+h^{2}}}$, then
$\psi^{\prime}(h)=\frac{1}{(1+h^{2})^{3/2}}$. Furthermore, we have the
following inequalities:

(a) For $0\leq a<b$ we have

$\psi(b)-\psi(a)\leq\psi^{\prime}(a)(b-a).$

(b) For $a<0<b$ we have

$\psi(b)-\psi(a)\leq b-a.$

###### Proof.

Using product rule for derivatives

$\displaystyle\psi^{\prime}(h)$
$\displaystyle=\frac{(h)^{\prime}\sqrt{1+h^{2}}-h(\sqrt{1+h^{2}})^{\prime}}{1+h^{2}}$
$\displaystyle=\frac{\sqrt{1+h^{2}}-h\cdot\frac{h}{\sqrt{1+h^{2}}}}{1+h^{2}}$
$\displaystyle=\frac{1+h^{2}-h^{2}}{(1+h^{2})^{3/2}}=\frac{1}{(1+h^{2})^{3/2}}.$

For $a<b$ we have

$\displaystyle\psi(b)-\psi(a)$
$\displaystyle=\int_{a}^{b}\psi^{\prime}(h)\,dh$
$\displaystyle\leq\max_{s\in[a,b]}\psi^{\prime}(s)\int_{a}^{b}\,du$
$\displaystyle=\max_{s\in[a,b]}\psi^{\prime}(s)(b-a).$

It is not hard to see

$\max_{h\in[a,b]}\psi^{\prime}(h)=\begin{cases}\psi^{\prime}(a)&0\leq a<b\\\
\psi^{\prime}(0)=1&a<0<b\end{cases}$

∎