Proving tail bound of a random projection

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 Lemma 10 that $$\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}))$$

I don't understand how this lower bound was obtained. It seems to me that when you want to find a lower bound on a probability in a situation like this, you should try to minimize $$\operatorname{Pr}\bigg(\frac{\|R\textbf{x}\|^2}{\|\textbf{x}\|^2} \leq 1 + \epsilon \bigg)$$ and maximize $$\operatorname{Pr}\bigg(\frac{\|R\textbf{x}\|^2}{\|\textbf{x}\|^2} \leq 1 - \epsilon \bigg)$$

If that's what Shi et al. did in this situation, I don't understand how they did it.

Answer 1

This follows from the proof of the Johnson-Lindestrauss Lemma in Dasgupta & Gupta "An elementary proof of a theorem of johnson and lindenstrauss." I will reference the tech report version available at https://pdfs.semanticscholar.org/038e/c2f6d7098c7d039bb142c04fcd5854107b54.pdf .

In the proof of Theorem 2.1 on p.2 of the linked tech report, make the correspondence k (in theorem 2.1) to n in your quoted Lemma 10; the remaining correspondences can be seen more clearly in section 3.1 of https://cs.stanford.edu/people/mmahoney/cs369m/Lectures/lecture1.pdf. Then we can see, per the 2nd to last lines in each direction of the proof of Theorem 2.1, $$\operatorname{Pr}(\frac{\|R\textbf{x}\|^2}{\|\textbf{x}\|^2} \geq 1 + \epsilon) \leq \exp(-\frac{n}{2}(\frac{\epsilon^2}{2}-\frac{\epsilon^3}{3}))$$ $$\operatorname{Pr}(1-\epsilon \geq \frac{\|R\textbf{x}\|^2}{\|\textbf{x}\|^2}) \leq \exp(-\frac{n}{4}\epsilon^2))$$ Taking complements, we have by Boole's Inequality, $$\operatorname{Pr}(1-\epsilon \leq \frac{\|R\textbf{x}\|^2}{\|\textbf{x}\|^2} \leq 1 + \epsilon) \geq 1 - \exp(-\frac{n}{2}(\frac{\epsilon^2}{2}-\frac{\epsilon^3}{3})) - \exp(-\frac{n}{4}\epsilon^2))$$ which is sharper than the result to be shown.