Help with understanding a proof on angle preservation

Question

Let $R \in \mathbb{R}^{n,d}$ be a random Gaussian matrix comprised of independent $\operatorname{N}(0,\frac{1}{n})$ entries, let $\textbf{w}$ and $\textbf{x}$ be vectors in $\mathbb{R}^d$, and let $\epsilon \in (0,1)$. In Shi et al. 2012, it is claimed in Theorem 5 that if $\langle \textbf{w},\textbf{x} \rangle > 0$, then

$$\frac{1+\epsilon}{1-\epsilon}\frac{\langle \textbf{w},\textbf{x} \rangle}{\| \textbf{w} \| \| \textbf{x} \|} - \frac{2\epsilon}{1-\epsilon} \leq \frac{\langle R\textbf{w}, R\textbf{x}\rangle}{\| R\textbf{w} \| \| R\textbf{x} \|} \leq 1 - \frac{\sqrt{1-\epsilon^2}}{1+\epsilon} + \frac{\epsilon}{1+\epsilon} + \frac{1-\epsilon}{1+\epsilon}\frac{\langle \textbf{w}, \textbf{x} \rangle}{\| \textbf{w} \| \| \textbf{x} \|}$$ with probability at least $1 - 6\exp(-\frac{n}{2}(\frac{\epsilon^2}{2}-\frac{\epsilon^3}{3}))$.

An auxiliary lemma (which they call Lemma 10) that they use to help prove the theorem states that for any $\textbf{x} \in \mathbb{R^d}$, any random matrix $R \in \mathbb{R}^{n,d}$ comprised of independent $\operatorname{N}(0,\frac{1}{n})$ entries, and any $\epsilon \in (0,1)$: $$\operatorname{Pr}(1-\epsilon \leq \frac{\|R\textbf{x}\|^2}{\|\textbf{x}\|^2} \leq 1 + \epsilon) \geq 1 - 2\exp(-\frac{n}{2}(\frac{\epsilon^2}{2}-\frac{\epsilon^3}{3}))$$

The authors use the union bound in conjunction with Lemma 10 to establish Theorem 5, but their explanation of how to do so isn't clear to me. In particular, I'd like to know why they apply the union bound to the vectors $\textbf{w}$, $\textbf{x}$, and $\frac{\textbf{x}}{\|\textbf{x}\|} - \frac{\textbf{w}}{\|\textbf{w}\|}$ in order to obtain the probability lower bound of $1 - 6\exp(-\frac{n}{2}(\frac{\epsilon^2}{2}-\frac{\epsilon^3}{3}))$ from Theorem 5.

Answer 1

Disclaimer. I am unable to follow the proof of Theorem 5 in Shi et al. 2012.

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