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

$\endgroup$
1
  • $\begingroup$ One step I don't understand is the following quote from the paper's proof of Theorem 5: "Plugging (11) and (12) into the two side bounds, we get (4)." It's not clear to me what the side bounds are. $\endgroup$
    – Taliant
    Mar 17, 2018 at 22:20

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ How did you derive the third to last inequality? $\endgroup$
    – Taliant
    Mar 19, 2018 at 17:06
  • $\begingroup$ @Taliant By squaring the two sides of the right-most inequality in $(d)$, followed by some simple manipulations (getting rid of the denominator, expanding the squared Euclidean norms, etc.). $\endgroup$
    – Luc Guyot
    Mar 19, 2018 at 17:49
  • $\begingroup$ This is a very basic question, but could you tell me the inequality you got when you squared (d)? I got $\frac{\| R\textbf{x} \|^2}{\| \textbf{x}\|^2} + \frac{\| R\textbf{w} \|^2}{\| \textbf{w} \|^2} - 2 \frac{\langle R\textbf{x}, R\textbf{w} \rangle}{\| x \| \| w \|}$, which doesn't look like it can be re-written as the third to last inequality. $\endgroup$
    – Taliant
    Mar 20, 2018 at 20:15
  • $\begingroup$ What you wrote is the numerator of the square of the left-hand side of the right-most part of $(d)$, which matches the left-hand side of the third to last inequality in my proof. The right-hand side of the latter inequality is the square of the denominator times $1 + \varepsilon$. $\endgroup$
    – Luc Guyot
    Mar 20, 2018 at 22:41
  • $\begingroup$ Ah okay, thanks so much for the clarification. $\endgroup$
    – Taliant
    Mar 22, 2018 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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