3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.