Johnson-Lindenstrauss Lemma

虽为小禽，尚能解艺道之奥妙，汝等生而为人竟不及鸟类。

证明：根据 Markov Inequality，$\text{Pr}[X\geq a]=\text{Pr}[e^{\lambda x}\geq e^{\lambda a}]\leq e^{-\lambda a}\mathbb{E}[e^{\lambda a}]$ 对任意$\lambda>0$ 都成立。指数变化就是因为要求随机变量是非负的，就可以使用 Markov Inequality。

$\square$

证明：根据 Cramér-Chernoff 方法：

$$\begin{aligned} \text{Pr}[\|u\|^2-1\geq \varepsilon]&\leq\min_{\lambda>0}e^{-\lambda\varepsilon}\mathbb{E}[e^{\lambda(\|u\|^2-1)}]\\ &=\min_{\lambda>0}e^{-\lambda(\varepsilon+1)}\mathbb{E}[e^{\lambda\|u\|^2}]\\ &=\min_{\lambda>0}e^{-\lambda(\varepsilon+1)}\mathbb{E}[e^{\lambda\sum_{i=1}^nu_i^2}]\\ &=\min_{\lambda>0}e^{-\lambda(\varepsilon+1)}\mathbb{E}[\prod_{i=1}^ne^{\lambda u_i^2}]\\ \end{aligned}$$

因为$u$ 的每个分量都是独立选取，所以：

$$\begin{aligned} \text{Pr}[\|u\|^2-1\geq \varepsilon]&\leq\min_{\lambda>0}e^{-\lambda(\varepsilon+1)}\mathbb{E}[\prod_{i=1}^ne^{\lambda u_i^2}]\\ &=\min_{\lambda>0}e^{-\lambda(\varepsilon+1)}\prod_{i=1}^n\mathbb{E}[e^{\lambda u_i^2}] \end{aligned}$$

其中

$$\begin{aligned} \mathbb{E}[e^{\lambda u_i^2}]&=\int_{-\infty}^\infty\sqrt{\frac{n}{2\pi}}e^{-nu_i^2/2}e^{\lambda u_i^2}du_i\\ &=\sqrt{\frac{n}{n-2\lambda}} \end{aligned}$$

故

$$\begin{aligned} \text{Pr}[\|u\|^2-1\geq \varepsilon] &\leq\min_{\lambda>0}e^{-\lambda(\varepsilon+1)}\left(\frac{n}{n-2\lambda}\right)^{n/2} \end{aligned}$$

当$\lambda=\frac{n\varepsilon}{2(1+\varepsilon)}$ 时右侧取到最小值。此时有：

$$\text{Pr}[\|u\|^2-1\geq \varepsilon]\leq e^{n(\log(1+\varepsilon)-\varepsilon)/2}\leq e^{-n\varepsilon^2/8}$$

另一侧$\text{Pr}[\|u\|^2-1\leq-\varepsilon]$ 也类似可以得到证明。

$\square$

证明：若$u,v\sim\mathcal{N}(0,\frac{1}{n})$，那么$\frac{u+v}{\sqrt{2}}\sim\mathcal{N}(0,\frac{1}{n})$。那么根据单位摸引理，有：

$$\begin{cases} \text{Pr}\left [\left \|\frac{u+v}{\sqrt{2}}\right \|^2-1\geq\varepsilon\right ]\leq e^{-n\varepsilon^2/8}\\ \text{Pr}\left [\left \|\frac{u+v}{\sqrt{2}}\right \|^2-1\leq-\varepsilon\right ]\leq e^{-n\varepsilon^2/8} \end{cases}$$

而$\langle u,v\rangle\geq \varepsilon\Leftrightarrow \left \|\frac{u+v}{\sqrt{2}}\right\|^2-\left \|\frac{u-v}{\sqrt{2}}\right\|^2\geq 2\varepsilon$，故：

$$\begin{aligned} \text{Pr}[\langle u,v\rangle\geq \varepsilon]&=\text{Pr}\left [\left \|\frac{u+v}{\sqrt{2}}\right\|^2-1+1-\left \|\frac{u-v}{\sqrt{2}}\right\|^2\geq 2\varepsilon\right ]\\ &\leq\text{Pr}\left [\left \|\frac{u+v}{\sqrt{2}}\right\|^2-1\geq\varepsilon\vee1-\left \|\frac{u-v}{\sqrt{2}}\right\|^2\geq \varepsilon\right ]\\ &\leq \text{Pr}\left [\left \|\frac{u+v}{\sqrt{2}}\right\|^2-1\geq\varepsilon\right ]+\text{Pr}\left [1-\left \|\frac{u-v}{\sqrt{2}}\right\|^2\geq \varepsilon\right ]\\ &\leq 2e^{-n\varepsilon^2/8} \end{aligned}$$

其中，第一个小于等于号是因为：

$$\left \|\frac{u+v}{\sqrt{2}}\right\|^2-1+1-\left \|\frac{u-v}{\sqrt{2}}\right\|^2\geq 2\varepsilon\\ \Rightarrow \left \|\frac{u+v}{\sqrt{2}}\right\|^2-1\geq\varepsilon\vee1-\left \|\frac{u-v}{\sqrt{2}}\right\|^2\geq \varepsilon$$

$\square$

这个定理其实是说，不管原来向量是多少维数，只需要$\frac{24\log N}{\varepsilon^2}$ 维度，我们就可以容纳下$N$ 个向量，而且使得变换后的向量直接的距离和原来的距离只有$1\pm \varepsilon$ 的误差。这个变换也很简单，就是随机采样一个$n\times m$ 的矩阵。

证明：对于单位一个单位向量$u$ 的话，$Au$ 就是每个分量都独立服从于$\mathcal{N}(0,\frac{1}{n})$ 的随机变量。那么令$u=\frac{v_i-v_j}{\|v_i-v_j\|}$，那么$\frac{A(v_i-v_j)}{\|v_i-v_j|}$ 就是一个每个分量都独立服从于$\mathcal{N}(0,\frac{1}{n})$ 的向量。利用单位根引理，有：

$$\text{Pr}\left [\left |\left \|\frac{A(v_i-v_j)}{\|v_i-v_j\|}\right \|^2-1\right |\geq\varepsilon\right ]\leq 2e^{-\varepsilon^2n/8}$$

故：

$$\text{Pr}\left [\exists (i,j),\left |\left \|\frac{A(v_i-v_j)}{\|v_i-v_j\|}\right \|^2-1\right |\geq\varepsilon\right ]\leq 2\begin{pmatrix}N\\2\end{pmatrix}e^{-\varepsilon^2n/8}$$

所以：

$$\text{Pr}\left [\forall (i,j),\left |\left \|\frac{A(v_i-v_j)}{\|v_i-v_j\|}\right \|^2-1\right |\leq\varepsilon\right ]\geq 1-2\begin{pmatrix}N\\2\end{pmatrix}e^{-\varepsilon^2n/8}$$

当$n>\frac{24\log N}{\varepsilon^2}$ 时，右侧值为$\frac{N-1}{N}$。

$\square$