参考了 https://spaces.ac.cn/archives/8679/comment-page-1，有一些增删。
JL 引理
首先下面需要应用马尔可夫不等式的另一个形式：
\[\newcommand \E{\mathbb E} P(x\ge a)=P(e^{\lambda x}\ge e^{\lambda a})(\lambda >0)\le \min_{\lambda >0}e^{\lambda a}\E[e^{\lambda x}] \]单位模引理
单位模引理：对于 \(u\in \R^n\)，每一维从 \(N(0,1/n)\) 随机采样，则
\[\newcommand\eps{\epsilon}\newcommand\la{\lambda}\newcommand\par{\parallel} \forall \eps \in (0,1)\\ P(\big|\par u\par^2-1\big|>\eps)\le 2\exp(-\eps^2n/8) \]绝对值两边大概是差不多的（？），先看看 \(\par u\par ^2-1>\eps\)。
套用上述结论有：
\[P(\par u\par ^2-1>\eps)\le \min_{\la >0}e^{-\la (\eps+1)}\E[e^{\la\par u\par^2}]\\ \]化简 \(\E[e^{\la\par u\par^2}]\)，将 \(u\) 正交分解为 \(u_{1:n}\)。
\[\E[e^{\la\par u\par^2}]=\prod_{i=1}^n \E[e^{\la u_i^2}]=\E[e^{\la u_i^2}]^n\\ =\left(\int_{-\infty}^{\infty}P(u_i=t)e^{\la t^2}dt\right)^n\\ =\left(\int _{-\infty}^{\infty}\frac{1}{\sqrt{2n\pi}}e^{-\frac{nt^2}{2}}e^{\la t^2}dt\right)^n=\left(\int _{-\infty}^{\infty}\frac{1}{\sqrt{2n\pi}}e^{-(\frac n2-\la)\frac{t^2}2}dt\right)^n \]考虑正态分布 \(N(0,\sigma^2)\) 满足 \(\frac{1}{2\sigma^2}=\frac{n-2\la}{2}\)，即 \(\sigma=\sqrt{\dfrac{1}{n-2\la}}\)。比较
\[\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2\sigma^2}}dt=1 \]上式的系数，得到：
\[\E[e^{\la u_i^2}]=\int _{-\infty}^{\infty}\frac{1}{\sqrt{2n\pi}}e^{-(\frac n2-\la)\frac{t^2}2}dt=\frac{\sqrt{n}}{\sqrt{n-2\la}}=\sqrt{\frac{n}{n-2\la}} \]那么
\[P(\par u\par ^2-1>\eps)\le \min_{\la >0}e^{-\la (\eps+1)}\left(\frac n{n-2\la}\right)^{n/2}\\ \]设 \(f(\la)=e^{-\la (\eps+1)}\left(\dfrac n{n-2\la}\right)^{n/2}\)。则
\[f'(\la)=e^{-\la(\eps+1)}\left(\dfrac n{n-2\la}\right)^{n/2-1}\left(\frac{n^2}{(n-2\la)^2}-\frac{n(\eps+1)}{n-2\la}{}\right) \]所以不妨取
\[\la=\frac{n\eps}{2(\eps+1)} \]所以：
\[P(\par u\par ^2-1>\eps)\le e^{-n\eps/2}e^{n\ln(\eps+1)/2}=e^{n(\ln(1+\eps)-\eps)/2}\\ \]而设 \(g(\eps)=\ln(\eps+1)-\eps+\eps^2/4\)。
\[g'(\eps)=\frac1{1+\eps}-1+\frac\eps2\le 0(0<\eps<1) \]所以 \(g(\eps)\le g(0)=0\)，所以：
\[P(\par u\par ^2-1>\eps)\le \exp(-n\eps^2/8) \]JL 引理
对于 \(N\) 个向量 \(v_{1:N}\in \R^m,n>\frac{24\ln N}{\eps^2}\)，随机矩阵 \(A\in R^{n\times m}\) 采样于 \(N(0,1/n)\)，\(\eps\in (0,1)\)，则至少有 \(\frac{N-1}{N}\) 的概率满足：
\[\forall i\neq j,\\ (1-\eps)\par v_i-v_j\par ^2\le \par Av_i-Av_j\par ^2 \le(1+\eps)\par v_i-v_j\par \]证明：
容易发现，\(\forall u\in \R^m\)，\((Au)_i\) 服从 \(N(0,1/n)\)。
使用 Union Bound，带入 \(u=\frac{v_i-v_j}{\par v_i-v_j\par}\)。那么：
\[P\left(\exists i\neq j,\left| \frac{A(v_i-v_j)}{\par v_i-v_j\par}-1\right|\ge \eps\right)\le 2\binom N2\exp(-\eps^2n/8) \]若 \(n>\dfrac{24\ln N}{\eps^2}\)，有：
\[1-N(N-1)\exp(-\eps^2n/8)>1-\frac{N(N-1)}{N^3}>\frac{N-1}{N} \]结束。
但是在计算中，\(24\ln N/\eps^2\) 并不是非常小的值，如果不使用一些更加高级的降维算法的话，差不多只有在 \(\eps>0.5\) 的时候才能发挥作用了（悲）。
标签：infty,par,le,frac,la,eps,JL,6.30,引理 From： https://www.cnblogs.com/british-union/p/18276712/JL