*Disclaimer.* I am unable to follow the proof of Theorem 5 in [Shi et al. 2012](https://icml.cc/2012/papers/327.pdf). 

But it is not difficult to show the following *angle preservation* statement based on the **Tail Bound Lemma**, that is, Lemma 10 of the article.

>> **Claim.** Let $\mathbf{x}, \mathbf{w} \in \mathbb{R}^d \setminus \{0\}$  and let $\mathbf{R} \in \mathbb{R}^{n, d}$ be a random Gaussian matrix as in Lemma 4 and let $\varepsilon \in (0, 1)$. Set $\cos(\beta) \Doteq \frac{\langle \mathbf{x}, \mathbf{w} \rangle}{\| \mathbf{x}\| \| \mathbf{w} \| }$ and $\cos(\beta') \Doteq \frac{\langle \mathbf{Rx}, \mathbf{Rw} \rangle}{\| \mathbf{Rx}\| \| \mathbf{Rw} \| }$.
Then the following inequalities hold 
$$
 \cos(\beta) - \frac{2 \varepsilon}{1 + \epsilon} \le \cos(\beta') \le \cos(\beta) + \frac{2 \varepsilon}{1 - \varepsilon}
$$
with probability at least $1 - 6 \exp \left(-\frac{n}{2}(\frac{\varepsilon^2}{2} - \frac{\varepsilon^3}{3})\right)$.

>> *Proof.* Let $x = \|\mathbf{x}\|, w = \|\mathbf{w}\|, x' = \|\mathbf{Rx}\|$ and $w' = \|\mathbf{Rw}\|$. Set also 
$p_{n, \varepsilon} \Doteq 1 - 6 \exp \left(-\frac{n}{2}(\frac{\varepsilon^2}{2} - \frac{\varepsilon^3}{3})\right)$.
By Lemma 10 and the [union bound](https://en.wikipedia.org/wiki/Boole%27s_inequality), the following inequalities

> $(x)$ $\sqrt{1 -\varepsilon} \le \frac{x'}{x} \le \sqrt{1 + \varepsilon}$,   
 
> $(w)$ $\sqrt{1 -\varepsilon} \le \frac{w'}{w} \le \sqrt{1 + \varepsilon}$,

> $(d)$ $\sqrt{1 -\varepsilon} \le \frac{\|\mathbf{R}\frac{\mathbf{x}}{x} - \mathbf{R}\frac{\mathbf{w}}{w} \|}{\| \frac{\mathbf{x}}{x} - \frac{\mathbf{w}}{w}\|} \le \sqrt{1 + \varepsilon}$,
>>simultaneously hold with probability at least $p_{n, \varepsilon}$.
The right-most inequality in $(d)$ is equivalent to 
$$\left(\frac{x'}{x}\right)^2 + \left(\frac{w'}{w}\right)^2 - 2 \frac{x'w'}{xw}\cos(\beta') \le
2(1 + \varepsilon)(1 - \cos(\beta)).$$ Using then $(x)$ and $(w)$, we deduce from the above inequality that 
$$2(1 - \varepsilon) - 2(1 + \varepsilon)\cos(\beta') \le 2(1 + \varepsilon)(1 - \cos(\beta))$$ and hence
$$\cos(\beta') \ge \cos(\beta) - \frac{2 \varepsilon}{1 + \varepsilon}$$ holds with probability at least $p_{n, \varepsilon}$.
A similar reasoning with the left-most inequality in $(d)$ yields the result.