Return to Answer

Makes the definition of the Gaussian matrix precise

Source Link

edited Mar 19, 2018 at 12:31

7.9k
2
30
51

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.

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

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.

Source Link

created Mar 18, 2018 at 21:52

Luc Guyot

7.9k
2
30
51

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