Return to 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}{\| \textbf{w} \| \| \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.

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.

Let $R \in \mathbb{R}^{n,d}$ be a random matrix comprised of independent $\operatorname{N}(0,1)$ 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}{\| \textbf{w} \| \| \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,1)$ 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.

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}{\| \textbf{w} \| \| \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.

Let $R \in \mathbb{R}^{n,d}$ be a random matrix comprised of independent $\operatorname{N}(0,1)$ 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}{\| \textbf{w} \| \| \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,1)$ entries, and any $\epsilon \in (0,1)$: $$\operatorname{Pr}(1-\epsilon \leq \frac{\|R\textbf{x}\|}{\|\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.

Let $R \in \mathbb{R}^{n,d}$ be a random matrix comprised of independent $\operatorname{N}(0,1)$ 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}{\| \textbf{w} \| \| \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,1)$ 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.