原论文中的引理$\text{2}$

引理$\text{2}$的内容​​

👉前提$1$：设一个随机矩阵$S\text{=}(s_{ij})\text{∈}{\mathbb{R}}^{t\text{×}d}$，每个元素$s_{ij}$独立同分布于$N(0,1)$

👉前提$2$：对任意固定向量$u\text{∈}{\mathbb{R}}^{d\text{×}1}$(即$u_{ij}$不随机)，定义$u^{\prime }\text{=}\frac{1}{\sqrt{t}}(Su)$

👉结论$1$：$\mathbb{E}\left[{\Vert u^{\prime }\Vert }^2\right]\text{=}\Vert u{\Vert }^2$，即${\Vert u^{\prime }\Vert }^2$和$\Vert u{\Vert }^2$在统计学上是相等的

👉结论$2$：$\text{Pr}\left[{\Vert u^{\prime }\Vert }^2\notin (1\text{±}\epsilon )\Vert u{\Vert }^2\right]\text{≤}2e^{–\left(\epsilon {}^2–\epsilon {}^3\right)\frac{t}{4}}$，即${\Vert u^{\prime }\Vert }^2$和$\Vert u{\Vert }^2$在实际值上偏差极小且可控

引理$\text{1}$的内容

👉前提：$X\sim N(0,\sigma )$即$f(x)\text{=}\frac{1}{\sqrt{2\pi }\sigma }{e}^{–\frac{x^2}{2{\sigma }^2}}$，且$\forall \alpha \text{<}\frac{1}{2{\sigma }^2}$

👉结论：$\mathbb{E}\left[e^{\alpha X^2}\right]\text{=}\frac{1}{\sqrt{1–2\alpha {\sigma }^2}}$

对结论$\text{1}$的证明

➡️对于$s_{ij}\sim N(0,1)$，则有$S_{\cdot j}u\text{=}\sum _{i=1}^d{s}_{ij}{u}_i\sim N(0,\Vert u{\Vert }^2)$

1. 均值$\mathbb{E}\left[S_{\cdot j}u\right]\text{=}\mathbb{E}\left[\sum _{i=1}^d{s}_{ij}{u}_i\right]\text{=}\sum _{i=1}^d{u}_i\mathbb{E}\left[s_{ij}\right]\text{=}0$
2. 方差$\text{Var}\left[S_{\cdot j}u\right]\text{=}\text{Var}\left[\sum _{i=1}^d{s}_{ij}{u}_i\right]\text{=}\sum _{i=1}^d\text{Var}[s_{ij}{u}_i]\text{=}\sum _{i=1}^d{u}_i^2\text{Var}[s_{ij}]\text{=}\sum _{i=1}^d{u}_i^2\text{=}\Vert u{\Vert }^2$

➡️正态分布性质$\mathbb{E}[X^2]\text{=}\sigma {}^2$，所以$\mathbb{E}\left[{\left(S_{\cdot j}u\right)}^2\right]\text{=}\Vert u{\Vert }^2$

➡️所以$\mathbb{E}\left[\Vert Su{\Vert }^2\right]\text{=}\mathbb{E}\left[\sum _{j\text{=}1}^t{\left(S_{\cdot j}u\right)}^2\right]\text{=}\sum _{j=1}^t\mathbb{E}\left[{\left(S_{\cdot j}u\right)}^2\right]\text{=}t\Vert u{\Vert }^2$

➡️根据$u^{\prime }\text{=}\frac{1}{\sqrt{t}}(Su)$，得到${\Vert u^{\prime }\Vert }^2\text{=}\frac{1}{t}\Vert Su{\Vert }^2$

➡️所以$\mathbb{E}\left[{\Vert u^{\prime }\Vert }^2\right]\text{=}\mathbb{E}\left[\frac{1}{t}\Vert Su{\Vert }^2\right]\text{=}\frac{1}{t}\mathbb{E}\left[\Vert Su{\Vert }^2\right]\text{=}\frac{1}{t}\left(t\Vert u{\Vert }^2\right)\text{=}\Vert u{\Vert }^2$

对结论$\text{2}$的证明(正半边)

➡️考虑到$S_{\cdot j}u\sim N(0,\Vert u{\Vert }^2)$，故将其归一化为$X_j\text{=}\frac{S_{\cdot j}u}{\Vert u\Vert }\sim N(0,1)$

➡️由此定义$X\text{=}\sum _{j=1}^t{X}_j^2$(自由度为$t$的${\chi }^2$分布)，由此${\Vert u^{\prime }\Vert }^2\text{=}\frac{1}{t}\Vert Su{\Vert }^2\text{=}\frac{1}{t}\sum _{j=1}^t{\left(S_{\cdot j}u\right)}^2\text{=}\Vert u{\Vert }^2\frac{1}{t}\sum _{j=1}^t{X}_j^2\text{=}\frac{1}{t}\Vert u{\Vert }^{2}X$

➡️由此$\text{Pr}\left[{\Vert u^{\prime }\Vert }^2\text{≥}(1\text{+}\epsilon )\Vert u{\Vert }^2\right]\text{=}\text{Pr}\left[X\text{≥}(1\text{+}\epsilon )t\right]$

➡️考虑马可夫不等式的指数形式：$\text{Pr}\left[X\text{≥}(1\text{+}\epsilon )t\right]\text{=}\text{Pr}\left[e^{\alpha X}\text{≥}{e}^{\alpha (1\text{+}\epsilon )t}\right]\text{≤}\frac{\mathbb{E}\left[e^{\alpha X}\right]}{e^{\alpha (1\text{+}\epsilon )t}}$

1. 考虑到$X\text{=}\sum _{j=1}^t{X}_j^2$，所以$\mathbb{E}\left[e^{\alpha X}\right]\text{=}\mathbb{E}\left[e^{\alpha (X_1^2\text{+}{X}_2^2\text{+}\cdots \text{+}{X}_t^2)}\right]\text{=}\mathbb{E}\left[e^{\alpha X_1^2}{e}^{\alpha X_2^2}\cdots e^{\alpha X_t^2}\right]\text{=}\mathbb{E}\left[\prod _{j=1}^t{e}^{\alpha X_j^2}\right]\text{=}\prod _{j=1}^t\mathbb{E}\left[e^{\alpha X_j^2}\right]$
2. 在引理$1$中已经证明$\mathbb{E}\left[e^{\alpha X_j^2}\right]\text{=}\frac{1}{\sqrt{1–2\alpha {\sigma }^2}}(\alpha \text{<}\frac{1}{2{\sigma }^2})$，考虑到此处$\sigma (X_j)\text{=}1$所以$\mathbb{E}\left[e^{\alpha X_j^2}\right]\text{=}\frac{1}{\sqrt{1–2\alpha }}(\alpha \text{<}\frac{1}{2})$
3. 所以$\mathbb{E}\left[e^{\alpha X}\right]\text{=}\prod _{j=1}^t\left(\frac{1}{\sqrt{1–2\alpha }}\right)\text{=}{\left(\frac{1}{\sqrt{1–2\alpha }}\right)}^t\text{=}\frac{1}{(1–2\alpha {)}^{\frac{t}{2}}}$
4. 代入原式得$\text{Pr}\left[X\text{≥}(1\text{+}\epsilon )t\right]\text{≤}\frac{\mathbb{E}\left[e^{\alpha X}\right]}{e^{\alpha (1\text{+}\epsilon )t}}\text{=}\frac{(1–2\alpha {)}^{–\frac{t}{2}}}{e^{\alpha (1\text{+}\epsilon )t}}\text{=}{\left(\frac{e^{–2(1\text{+}\epsilon )\alpha }}{1–2\alpha }\right)}^{\frac{t}{2}}$

➡️对于$\text{Pr}\left[X\text{≥}(1\text{+}\epsilon )t\right]\text{≤}{\left(\frac{e^{–2(1\text{+}\epsilon )\alpha }}{1–2\alpha }\right)}^{\frac{t}{2}}$，有必要在$0\text{<}\alpha \text{<}\frac{1}{2}$的范围内确定$f(\alpha )\text{=}{\left(\frac{e^{–2(1\text{+}\epsilon )\alpha }}{1–2\alpha }\right)}^{\frac{t}{2}}$的最小值

1. 对于$\ln (f(\alpha ))\text{=}\frac{t}{2}[–2(1\text{+}\epsilon )\alpha –\ln (1–2\alpha )]$，令$g(\alpha )\text{=}–2(1\text{+}\epsilon )\alpha –\ln (1–2\alpha )$，如下图($\epsilon \text{=}3$)
   
2. 一阶导$\frac{\text{d}g(\alpha )}{\text{d}\alpha }\text{=}\frac{2}{1–2\alpha }–2(1\text{+}\epsilon )$，具有临界点${\alpha }^{\ast }\text{=}\frac{\epsilon }{2(1\text{+}\epsilon )}\text{∈}\left(0,\frac{1}{2}\right)$，故$\epsilon \text{>}0$
3. 代入原式即得$\text{Pr}\left[X\text{≥}(1\text{+}\epsilon )t\right]\text{≤}{\left(\frac{e^{–2(1\text{+}\epsilon )\alpha }}{1–2\alpha }\right)}^{\frac{t}{2}}\text{≤}{\left((1\text{+}\epsilon )e^{–\epsilon }\right)}^{\frac{t}{2}}$

➡️进一步对$h(\epsilon )\text{=}{\left((1\text{+}\epsilon )e^{–\epsilon }\right)}^{\frac{t}{2}}$的分析

1. 泰勒展开$\ln (1\text{+}\epsilon )\text{=}\epsilon –\frac{{\epsilon }^2}{2}\text{+}\frac{{\epsilon }^3}{3}\text{+}O\left({\epsilon }^4\right)$，则$\ln (1\text{+}\epsilon )–\epsilon \text{≤}–\frac{{\epsilon }^2}{2}\text{+}\frac{{\epsilon }^3}{3}\text{≤}–\frac{1}{2}\left({\epsilon }^2–{\epsilon }^3\right)$
2. 故在$\ln (h(\epsilon ))\text{=}\frac{t}{2}(\ln (1\text{+}\epsilon )–\epsilon )\text{≤}–\frac{t}{4}\left({\epsilon }^2–{\epsilon }^3\right)$，即$h(\epsilon )\text{≤}{e}^{–\frac{t}{4}\left({\epsilon }^2–{\epsilon }^3\right)}$

➡️最后$\text{Pr}\left[{\Vert u^{\prime }\Vert }^2\text{≥}(1\text{+}\epsilon )\Vert u{\Vert }^2\right]\text{=}\text{Pr}\left[X\text{≥}(1\text{+}\epsilon )t\right]\text{≤}{\left(\frac{e^{–2(1\text{+}\epsilon )\alpha }}{1–2\alpha }\right)}^{\frac{t}{2}}\text{≤}{\left((1\text{+}\epsilon )e^{–\epsilon }\right)}^{\frac{t}{2}}\text{≤}{e}^{–\frac{t}{4}\left({\epsilon }^2–{\epsilon }^3\right)}$

对结论$2$的证明(负半边)

➡️考虑到$S_{\cdot j}u\sim N(0,\Vert u{\Vert }^2)$，故将其归一化为$X_j\text{=}\frac{S_{\cdot j}u}{\Vert u\Vert }\sim N(0,1)$

➡️由此定义$X\text{=}\sum _{j=1}^t{X}_j^2$(自由度为$t$的${\chi }^2$分布)，由此${\Vert u^{\prime }\Vert }^2\text{=}\frac{1}{t}\Vert Su{\Vert }^2\text{=}\frac{1}{t}\sum _{j=1}^t{\left(S_{\cdot j}u\right)}^2\text{=}\Vert u{\Vert }^2\frac{1}{t}\sum _{j=1}^t{X}_j^2\text{=}\frac{1}{t}\Vert u{\Vert }^{2}X$

➡️由此$\text{Pr}\left[{\Vert u^{\prime }\Vert }^2\text{≤}(1\text{–}\epsilon )\Vert u{\Vert }^2\right]\text{=}\text{Pr}\left[X\text{≤}(1\text{–}\epsilon )t\right]\text{=}\text{Pr}\left[–X\text{≥}–(1\text{–}\epsilon )t\right]$

➡️考虑马可夫不等式的指数形式：$\text{Pr}\left[–X\text{≥}–(1\text{–}\epsilon )t\right]\text{=}\text{Pr}\left[e^{\alpha (–X)}\text{≥}{e}^{–\alpha (1\text{–}\epsilon )t}\right]\text{≤}\frac{\mathbb{E}\left[e^{–\alpha X}\right]}{e^{–\alpha (1\text{–}\epsilon )t}}$

1. 而$X\text{=}\sum _{j=1}^t{X}_j^2$，所以$\mathbb{E}\left[e^{–\alpha X}\right]\text{=}\mathbb{E}\left[e^{–\alpha (X_1^2\text{+}{X}_2^2\text{+}\cdots \text{+}{X}_t^2)}\right]\text{=}\mathbb{E}\left[e^{–\alpha X_1^2}{e}^{–\alpha X_2^2}\cdots e^{–\alpha X_t^2}\right]\text{=}\mathbb{E}\left[\prod _{j=1}^t{e}^{–\alpha X_j^2}\right]\text{=}\prod _{j=1}^t\mathbb{E}\left[e^{–\alpha X_j^2}\right]$
2. 在引理$1$中已经证明$\mathbb{E}\left[e^{–\alpha X_j^2}\right]\text{=}\frac{1}{\sqrt{1\text{+}2\alpha {\sigma }^2}}(\alpha \text{>}–\frac{1}{2{\sigma }^2})$，考虑到此处$\sigma (X_j)\text{=}1$所以$\mathbb{E}\left[e^{–\alpha X_j^2}\right]\text{=}\frac{1}{\sqrt{1\text{+}2\alpha }}(\alpha \text{>}–\frac{1}{2})$
3. 所以$\mathbb{E}\left[e^{–\alpha X}\right]\text{=}\prod _{j=1}^t\left(\frac{1}{\sqrt{1\text{+}2\alpha }}\right)\text{=}{\left(\frac{1}{\sqrt{1\text{+}2\alpha }}\right)}^t\text{=}\frac{1}{(1\text{+}2\alpha {)}^{\frac{t}{2}}}$
4. 代入原式得$\text{Pr}\left[–X\text{≥}–(1\text{–}\epsilon )t\right]\text{≤}\frac{\mathbb{E}\left[e^{–\alpha X}\right]}{e^{–\alpha (1–\epsilon )t}}\text{=}\frac{(1\text{+}2\alpha {)}^{–\frac{t}{2}}}{e^{–\alpha (1–\epsilon )t}}\text{=}{\left(\frac{e^{2(1–\epsilon )\alpha }}{1\text{+}2\alpha }\right)}^{\frac{t}{2}}$

➡️对于$\text{Pr}\left[–X\text{≥}–(1\text{–}\epsilon )t\right]\text{≤}{\left(\frac{e^{2(1–\epsilon )\alpha }}{1\text{+}2\alpha }\right)}^{\frac{t}{2}}$，有必要在$\alpha \text{>}–\frac{1}{2}$的范围内确定$f(\alpha )\text{=}{\left(\frac{e^{2(1–\epsilon )\alpha }}{1\text{+}2\alpha }\right)}^{\frac{t}{2}}$的最小值

1. 对于$\ln (f(\alpha ))\text{=}\frac{t}{2}[2(1–\epsilon )\alpha –\ln (1\text{+}2\alpha )]$，令$g(\alpha )\text{=}[2(1–\epsilon )\alpha –\ln (1\text{+}2\alpha )]$，如下图($\epsilon \text{=}–\frac{1}{3}$)
   
2. 一阶导$\frac{\text{d}g(\alpha )}{\text{d}\alpha }\text{=}–\frac{2}{1\text{+}2\alpha }\text{+}2(1\text{+}\epsilon )$，具有临界点${\alpha }^{\ast }\text{=}\frac{\epsilon }{2(1–\epsilon )}\text{∈}\left(–\frac{1}{2},\text{+∞}\right)$，故$–1\text{<}\epsilon \text{<}1$(由于前提限制故截取为$0\text{<}\epsilon \text{<}1$)
3. 代入原式即得$\text{Pr}\left[–X\text{≥}–(1\text{–}\epsilon )t\right]\text{≤}{\left(\frac{e^{2(1–\epsilon )\alpha }}{1\text{+}2\alpha }\right)}^{\frac{t}{2}}\text{≤}{\left((1–\epsilon )e^{\epsilon }\right)}^{\frac{t}{2}}$

➡️进一步对$h(\epsilon )\text{=}{\left((1–\epsilon )e^{\epsilon }\right)}^{\frac{t}{2}}$的分析

1. 泰勒展开$\ln (1–\epsilon )\text{=}–\epsilon –\frac{{\epsilon }^2}{2}–\frac{{\epsilon }^3}{3}\text{+}O\left({\epsilon }^4\right)$，则$\ln (1–\epsilon )\text{+}\epsilon \text{≤}–\frac{{\epsilon }^2}{2}–\frac{{\epsilon }^3}{3}\text{≤}–\frac{1}{2}\left({\epsilon }^2–{\epsilon }^3\right)$
2. 故在$\ln (h(\epsilon ))\text{=}\frac{t}{2}(\ln (1–\epsilon )\text{+}\epsilon )\text{≤}–\frac{t}{4}\left({\epsilon }^2–{\epsilon }^3\right)$，即$h(\epsilon )\text{≤}{e}^{–\frac{t}{4}\left({\epsilon }^2–{\epsilon }^3\right)}$

➡️最后$\text{Pr}\left[{\Vert u^{\prime }\Vert }^2\text{≤}(1\text{–}\epsilon )\Vert u{\Vert }^2\right]\text{=}\text{Pr}\left[–X\text{≥}–(1\text{–}\epsilon )t\right]\text{≤}{\left(\frac{e^{2(1–\epsilon )\alpha }}{1\text{+}2\alpha }\right)}^{\frac{t}{2}}\text{≤}{\left((1–\epsilon )e^{\epsilon }\right)}^{\frac{t}{2}}\text{≤}{e}^{–\frac{t}{4}\left({\epsilon }^2–{\epsilon }^3\right)}$