文献分享: Muvera多向量到单向量的转化方法(Part3——引理证明的补充)

原文章

由于$\text{CSDN}$字数严格的限制，很多详细过程腰斩了，完整版见标题的超链接

$\text{1. }$事实$\text{A.2}$的证明

$\text{1.0. }$定理的内容

👉前提：设随机矩阵$\mathbf{S}=(s_{ij})\in {\mathbb{R}}^{d_{\text{proj}}\times d}$

1. 每元素$s_{ij}$独立且同分布于$\mathcal{D}$，其中$\mathcal{D}$关于竖轴对称且$\forall s_{ij}\sim \mathcal{D}$有$\mathbb{E}[s_{ij}^2]=1$
2. 对任意固定向量$u\in {\mathbb{R}}^{d\times 1}$(即每个分量$u_j$不随机)，定义$\psi (u)=\frac{1}{\sqrt{t}}(\mathbf{S}u)$

👉结论$1$：${\Vert \psi (u)\Vert }^2$与$\Vert u{\Vert }^2$逼近

1. 负半边：令$\mathbb{E}[s_{ij}^4]=B<\infty$，对$\forall \epsilon >0$有$\mathrm{Pr}\left[{\Vert u^{\prime }\Vert }^2\le (1–\epsilon )\Vert u{\Vert }^2\right]\le e^{–\frac{\left({\epsilon }^2–{\epsilon }^3\right)t}{2(B+1)}}$
2. 正半边：若$\text{∃}L>0$对$\forall m>0$满足矩$\mathbb{E}\left[s^{2m}\right]\le \frac{(2m)!}{2^{m}m!}{L}^{2m}$，对$\forall \epsilon >0$有$\mathrm{Pr}\left[{\Vert u^{\prime }\Vert }^2\ge (1+\epsilon )L^2\Vert u{\Vert }^2\right]\le {\left((1+\epsilon )e^{–\epsilon }\right)}^{\frac{t}{2}}\le e^{–\frac{\left({\epsilon }^2–{\epsilon }^3\right)t}{4}}$

$\text{1.1. }$矩分析

➡️设$X_i=\sum _{j=1}^d{s}_{ij}{u}_j={\mathbf{S}}_{i\cdot }u$，则${\psi }_i(u)=\frac{1}{\sqrt{d_{\text{proj}}}}\left({\mathbf{S}}_{i\cdot }u\right)=\frac{1}{\sqrt{d_{\text{proj}}}}{X}_i$

➡️分析$X_i$的$\text{1/2/4}$阶矩

1. 一阶矩：$\mathbb{E}\left[X_i\right]=\mathbb{E}\left[\sum _{j=1}^d{s}_{ij}{u}_j\right]\stackrel{由于每个u_j固定}{\Rightarrow }\mathbb{E}\left[X_i\right]=\sum _{j=1}^d{u}_j\mathbb{E}\left[s_{ij}\right]\stackrel{s_{ij}的分布关于竖轴对称}{\Rightarrow }\mathbb{E}\left[X_i\right]=0$
2. 二阶矩：$\mathbb{E}\left[X_i^2\right]=\mathbb{E}\left[{\left(\sum _{j=1}^d{s}_{ij}{u}_j\right)}^2\right]=\mathbb{E}\left[\sum _{j=1}^d{\left(s_{ij}{u}_j\right)}^2\right]+\mathbb{E}\left[2\sum _{j_1<j_2}\left(s_{i{j}_1}{u}_{j_1}\right)\left(s_{i{j}_2}{u}_{j_2}\right)\right]=1$
3. 四阶矩：$\mathbb{E}\left[X_i^4\right]=\sum _{j_{1,2,3,4}}\mathbb{E}\left[s_{i{j}_1}{s}_{i{j}_2}{s}_{i{j}_3}{s}_{i{j}_4}\right]$
   • $s_{ij}$相互独立且关于竖轴对称，故$\mathbb{E}\left[s_{ij}^{2n\text{+1}}\right]=\mathbb{E}\left[s_{ij}^{2n}\right]\mathbb{E}\left[s_{ij}\right]=0$及$\mathbb{E}\left[s_{ij}^{2n}\right]\ne 0$
   • $\mathbb{E}\left[s_{i{j}_1}{s}_{i{j}_2}{s}_{i{j}_3}{s}_{i{j}_4}\right]$四种情况

     情形	次数	$\mathbb{E}\left[{\mathbf{s}}_{\mathbf{i}{\mathbf{j}}_1}{\mathbf{s}}_{\mathbf{i}{\mathbf{j}}_2}{\mathbf{s}}_{\mathbf{i}{\mathbf{j}}_3}{\mathbf{s}}_{\mathbf{i}{\mathbf{j}}_4}\right]$值
     $j_1=j_2=j_3=j_4$	$1$	$B$
     $j_1=j_2\ne j_3=j_4$	$C_4^2/2\text{=3}$	$1$
     $j_1=j_2\ne j_3\ne j_4$	$\text{N/A}$	$0$
     $j_1\ne j_2\ne j_3\ne j_4$	$\text{N/A}$	$0$

   • $\mathbb{E}\left[X_i^4\right]$的情况

     索引情形	次数	$\mathbb{E}\left[{\mathbf{X}}_{\mathbf{i}}^4\right]$
     $j_1=j_2=j_3=j_4$	$1$	$\sum _{j=1}^d{u}_j^4\mathbb{E}\left[s_{ij}^4\right]=B\sum _{j=1}^d{u}_j^4$
     $j_1=j_2\ne j_3=j_4$	$3$	$\sum _{j_{\alpha }\text{,}{j}_{\beta }}{u}_{j_{\alpha }}^2{u}_{j_{\beta }}^2–\sum _{j_{\alpha }=j_{\beta }}{u}_{j_{\alpha }}^2{u}_{j_{\beta }}^2=1-\sum _{j=1}^d{u}_j^4$

   • 合并得$\mathbb{E}\left[X_i^4\right]=(B–3)\sum _{j=1}^d{u}_j^4+3$，而$\sum _{j=1}^d{u}_j^4\le \sum _{j=1}^d{u}_j^2\text{=1}$故$\mathbb{E}\left[X_i^4\right]\le B$

➡️分析$X_i$的类二阶矩母函数：$\mathbb{E}\left[e^{\alpha X_i^2}\right]\le \frac{1}{\sqrt{1–2\alpha L^2}}$

1. 构造变量$s_{ij}^{\prime }\sim N(0,L)$，定义其线性变换$Z_i=\sum _{j=1}^d{s}_{ij}^{\prime }{u}_j$
2. 正态分布性质中有$\mathbb{E}\left[s_{ij}^{\prime 2m}\right]=(2m–1)!!{\sigma }^{2m}=\frac{(2m)!}{2^{m}m!}{\sigma }^{2m}$，结合条件$\mathbb{E}\left[s_{ij}^{2m}\right]\le \frac{(2m)!}{2^{m}m!}{L}^{2m}$故$\mathbb{E}\left[s_{ij}^{2m}\right]\le \mathbb{E}\left[s_{ij}^{\prime 2m}\right]$
3. 由$\mathbb{E}\left[s_{ij}^{2m}\right]\le \mathbb{E}\left[s_{ij}^{\prime 2m}\right]$可得$\mathbb{E}\left[X_i^{2m}\right]\le \mathbb{E}\left[Z_i^{2m}\right]$
   • 因$\mathcal{D}$及$N(0,L)$皆关于竖轴对称，则$\mathbb{E}\left[s_{ij}^{2m+1}\right]=\mathbb{E}\left[s_{ij}^{\prime 2m+1}\right]=0$，故在$\mathbb{E}\left[X_i^{2m}\right]$和$\mathbb{E}\left[Z_i^{2m}\right]$展开直接忽略奇数项(如下)
     • $\mathbb{E}\left[X_i^{2m}\right]=\sum _{\begin{array}{c}\sum \alpha =2m\\ \forall \alpha =2k\end{array}}\frac{(2m)!}{{\prod }_{i\text{=1}}^d{\alpha }_i\text{!}}\left(\prod _{j=1}^d{u}_j^{{\alpha }_j}\right)\prod _{j=1}^d\mathbb{E}\left[s_{ij}^{{\alpha }_j}\right]$
     • $\mathbb{E}\left[Z_i^{2m}\right]$将上式$s_{ij}$换成$s_{ij}^{\prime }$即可
   • 两式$\mathbb{E}\left[s_{ij}^{{\alpha }_j}\right]$与$\mathbb{E}\left[s_{ij}^{\prime {\alpha }_j}\right]$中${\alpha }_j$为偶数，故$\mathbb{E}\left[s_{ij}^{{\alpha }_j}\right]\le \mathbb{E}\left[s_{ij}^{\prime {\alpha }_j}\right]$，故$\mathbb{E}\left[X_i^{2m}\right]\le \mathbb{E}\left[Z_i^{2m}\right]$
4. 由$\mathbb{E}\left[X_i^{2m}\right]\le \mathbb{E}\left[Z_i^{2m}\right]$得$\mathbb{E}\left[e^{\alpha X_i^2}\right]\le \mathbb{E}\left[e^{\alpha Z_i^2}\right]$，有正态分布性质知当$\alpha <\frac{1}{2L^2}$时$\mathbb{E}\left[e^{\alpha X_i^2}\right]\le \mathbb{E}\left[e^{\alpha Z_i^2}\right]=\frac{1}{\sqrt{1–2\alpha L^2}}$

$\text{1.2. }$负半边的证明

➡️设$Y=\sum _{i=1}^{d_{\text{proj}}}{X}_i^2$，默认$\Vert u\Vert =1$

1. 则$\mathbb{E}[Y]=\mathbb{E}\left[\sum _{i=1}^{d_{\text{proj}}}{X}_i^2\right]=\sum _{i=1}^{d_{\text{proj}}}\mathbb{E}\left[X_i^2\right]=d_{\text{proj}}$
2. 及$Y=\sum _{i=1}^{d_{\text{proj}}}{\left({\psi }_i(u)\sqrt{d_{\text{proj}}}\right)}^2=d_{\text{proj}}{\Vert \psi (u)\Vert }^2$，故$\mathrm{Pr}\left[{\Vert \psi (u)\Vert }^2\le (1–\epsilon )\Vert u{\Vert }^2\right]=\mathrm{Pr}[Y\le (1–\epsilon )d_{\text{proj}}]$

➡️马可夫不等式$\mathrm{Pr}[Y\le (1–\epsilon )d_{\text{proj}}]=\mathrm{Pr}\left[e^{–\alpha Y}\ge e^{–\alpha (1–\epsilon )d_{\text{proj}}}\right]\le \frac{\mathbb{E}\left[e^{–\alpha Y}\right]}{e^{–\alpha (1–\epsilon )d_{\text{proj}}}}$

1. 分子$\mathbb{E}\left[e^{–\alpha Y}\right]=\mathbb{E}\left[e^{–\alpha \left(X_1^2+\cdot \cdot \cdot +X_{d_{\text{proj}}}^2\right)}\right]=\prod _{i=1}^{d_{\text{proj}}}\mathbb{E}\left[e^{–\alpha X_i^2}\right]={\mathbb{E}}^{d_{\text{proj}}}\left[e^{–\alpha X_i^2}\right]$
2. 已证$\mathbb{E}\left[X_i^4\right]\le B+1$，故泰勒展开得$\mathbb{E}\left[e^{–\alpha X_i^2}\right]\le 1–\alpha +\frac{{\alpha }^2}{2}\mathbb{E}\left[X_i^4\right]\le 1–\alpha +\frac{{\alpha }^2}{2}(B+1)$
3. 代回得$\mathrm{Pr}\left[{\Vert \psi (u)\Vert }^2<(1–\epsilon )\Vert u{\Vert }^2\right]\le {\left(\left(1–\alpha +\frac{{\alpha }^2}{2}(B+1)\right)e^{\alpha (1–\epsilon )}\right)}^{d_{\text{proj}}}$
4. 又有$1+\left(–\alpha +\frac{{\alpha }^2}{2}(B+1)\right)\le e^{\left(–\alpha +\frac{{\alpha }^2}{2}(B+1)\right)}$，故令$\alpha =\frac{\epsilon }{1+B}$则$\mathrm{Pr}\left[{\Vert \psi (u)\Vert }^2<(1–\epsilon )\Vert u{\Vert }^2\right]\le e^{\left(–\frac{{\epsilon }^2}{2(B+1)}\right)d_{\text{proj}}}$
5. 而$\text{1≤}{e}^{–\frac{–{\epsilon }^3}{2(B+1)}}$($\epsilon >0$)，所以$\mathrm{Pr}\left[{\Vert \psi (u)\Vert }^2<(1–\epsilon )\Vert u{\Vert }^2\right]\le e^{\left(–\frac{{\epsilon }^2}{2(B+1)}\right)t}\le e^{\left(–\frac{{\epsilon }^2–{\epsilon }^3}{2(B+1)}\right)t}$，证毕

$\text{1.3. }$正半边的证明

➡️设$Y=\sum _{i=1}^{d_{\text{proj}}}{X}_i^2$，默认$\Vert u\Vert =1$

1. 则$\mathbb{E}[Y]=\mathbb{E}\left[\sum _{i=1}^{d_{\text{proj}}}{X}_i^2\right]=\sum _{i=1}^{d_{\text{proj}}}\mathbb{E}\left[X_i^2\right]=d_{\text{proj}}$
2. 及$Y=\sum _{i=1}^{d_{\text{proj}}}{\left({\psi }_i(u)\sqrt{d_{\text{proj}}}\right)}^2=d_{\text{proj}}\sum _{i=1}^{d_{\text{proj}}}{\psi }_i^2(u)=d_{\text{proj}}{\Vert \psi (u)\Vert }^2$，故$\mathrm{Pr}\left[{\Vert \psi (u)\Vert }^2\ge (1+\epsilon )L^2\Vert u{\Vert }^2\right]=\mathrm{Pr}[Y\ge (1+\epsilon )L^2{d}_{\text{proj}}]$

➡️马可夫不等式$\mathrm{Pr}[Y\ge (1+\epsilon )L^2{d}_{\text{proj}}]=\mathrm{Pr}\left[e^{\alpha Y}\ge e^{\alpha (1+\epsilon )L^2{d}_{\text{proj}}}\right]\le \frac{\mathbb{E}\left[e^{\alpha Y}\right]}{e^{\alpha (1+\epsilon )L^2{d}_{\text{proj}}}}$

1. 对$\mathbb{E}\left[e^{\alpha Y}\right]=\mathbb{E}\left[e^{\alpha \left(X_1^2+X_2^2+\cdot \cdot \cdot +X_{d_{\text{proj}}}^2\right)}\right]=\mathbb{E}\left[e^{\alpha X_1^2}\cdot \cdot \cdot e^{\alpha X_{d_{\text{proj}}}^2}\right]=\prod _{i=1}^{d_{\text{proj}}}\mathbb{E}\left[e^{\alpha X_i^2}\right]={\mathbb{E}}^{d_{\text{proj}}}\left[e^{\alpha X_i^2}\right]$
2. 其中$\mathbb{E}\left[e^{\alpha Y}\right]={\mathbb{E}}^{d_{\text{proj}}}\left[e^{\alpha X_i^2}\right]\le {\left(\frac{1}{1–2\alpha L^2}\right)}^{\frac{d_{\text{proj}}}{2}}$，即$\mathrm{Pr}\left[{\Vert \psi (u)\Vert }^2\ge (1+\epsilon )L^2\Vert u{\Vert }^2\right]\le {\left(\frac{e^{–2\alpha L^2(1+\epsilon )}}{1–2\alpha L^2}\right)}^{\frac{d_{\text{proj}}}{2}}$
3. 分析$\varphi (\alpha ,\epsilon )={\left(\frac{e^{–2\alpha L^2(1+\epsilon )}}{1–2\alpha L^2}\right)}^{\frac{d_{\text{proj}}}{2}}$界
   • 令$\alpha =\frac{\epsilon }{2L^2(1+\epsilon )}$，得$\varphi (\alpha ,\epsilon )=\varphi (\epsilon )={\left((1+\epsilon )e^{–\epsilon }\right)}^{\frac{d_{\text{proj}}}{2}}$
   • 泰勒展开$\varphi (\epsilon )={\left((1+\epsilon )e^{–\epsilon }\right)}^{\frac{d_{\text{proj}}}{2}}=e^{\frac{d_{\text{proj}}}{2}(\ln (1+\epsilon )–\epsilon )}\le e^{\frac{d_{\text{proj}}}{2}\left(–\frac{e^2}{2}+\frac{s^3}{2}\right)}$
   • 故$\mathrm{Pr}\left[{\Vert \psi (u)\Vert }^2\ge (1+\epsilon )L^2\Vert u{\Vert }^2\right]\le {\left((1+\epsilon )e^{–\epsilon }\right)}^{\frac{d_{\text{proj}}}{2}}\le e^{–\frac{\left({\epsilon }^2–{\epsilon }^3\right)t}{4}}$，证毕

$\text{1.4. }$事实$\text{A.2}$的推论

➡️推论一：让 s i j ∼ U { – 1 , 1 } s_{ij}{∼}U\{–1,1\} sij​∼U{–1,1}，则$\mathrm{Pr}\left[{\Vert \psi (u)\Vert }^2\le (1–\epsilon )\Vert u{\Vert }^2\right]\le e^{–\frac{\left({\epsilon }^2–{\epsilon }^3\right)t}{4}}$及$\mathrm{Pr}\left[{\Vert \psi (u)\Vert }^2\ge (1+\epsilon )\Vert u{\Vert }^2\right]\le e^{–\frac{\left({\epsilon }^2–{\epsilon }^3\right)t}{4}}$

1. 对 s i j ∼ U { – 1 , 1 } s_{ij}{∼}U\{–1,1\} sij​∼U{–1,1}，有$\mathbb{E}\left[s_{ij}^{2m}\right]=\frac{1}{2}(-1{)}^{2m}+\frac{1}{2}{1}^{2m}=1$和$\mathbb{E}[s_{ij}]=0$(符合前提)，且$\mathbb{E}\left[s_{ij}^4\right]=B=1$
2. 再取$L\text{=1}$代入套定理，推论得证

➡️推论二：对$\forall \epsilon \delta >0/\forall d\ge 1/\forall xy\in {\mathbb{R}}^d$及$t=O\left(\frac{1}{{\epsilon }^2}\log \frac{1}{\delta }\right)$，让 s i j ∼ U { – 1 , 1 } s_{ij}{∼}U\{–1,1\} sij​∼U{–1,1}则$\text{Pr}\left[|⟨\psi (u),\psi (v)⟩–⟨u,v⟩|\le \epsilon \right]\ge 1–\delta$

1. 极化恒等式
   • 有$⟨\psi (u),\psi (v)⟩=\frac{1}{d_{\text{proj}}}⟨\mathbf{S}u,\mathbf{S}v⟩=\frac{1}{4}\left(\frac{\Vert \mathbf{S}(u+v){\Vert }^2}{d_{\text{proj}}}–\frac{\Vert \mathbf{S}(u–v){\Vert }^2}{d_{\text{proj}}}\right)$，及$⟨u,v⟩=\frac{1}{4}\left(\Vert u+v{\Vert }^2–\Vert u–v{\Vert }^2\right)$
   • 二者偏差为$\left|\frac{1}{d_{\text{proj}}}⟨\mathbf{S}u,\mathbf{S}v⟩–⟨u,v⟩\right|=\frac{1}{4}\left(\left(\frac{1}{d_{\text{proj}}}\Vert \mathbf{S}(u+v){\Vert }^2–\Vert u+v{\Vert }^2\right)–\left(\frac{1}{d_{\text{proj}}}\Vert \mathbf{S}(u–v){\Vert }^2–\Vert u–v{\Vert }^2\right)\right)$
2. 对$u+v$及$u–v$应用推论一
   • 对$u\pm v$有$\mathrm{Pr}\left[\frac{1}{d_{\text{proj}}}\Vert \mathbf{S}(u\pm v){\Vert }^2\le (1-\epsilon )\Vert u\pm v{\Vert }^2\right]\le e^{–\frac{\left({\epsilon }^2–{\epsilon }^3\right)t}{4}}$，$1-\epsilon$换成$1+\epsilon$也成立
   • 合并后$\mathrm{Pr}\left[\frac{1}{d_{\text{proj}}}{\Vert \mathbf{S}(u+v)\Vert }^2\in (1\pm \epsilon )\Vert u+v{\Vert }^2\right]\ge 1–2e^{–\frac{\left({\epsilon }^2–{\epsilon }^3\right)t}{4}}$，$u+v$换成$u-v$也成立
   • 进而$\max \left\{\frac{1}{d_{\text{proj}}}\Vert \mathbf{S}(u+v){\Vert }^2-\Vert u+v{\Vert }^2\right\}=\epsilon \Vert u+v{\Vert }^2$和$\min \left\{\frac{1}{d_{\text{proj}}}\Vert \mathbf{S}(u-v){\Vert }^2-\Vert u-v{\Vert }^2\right\}=–\epsilon \Vert u–v{\Vert }^2$
   • 代回$\left|\frac{1}{d_{\text{proj}}}⟨\mathbf{S}u,\mathbf{S}v⟩–⟨u,v⟩\right|\le \frac{\epsilon }{4}\left(\Vert u+v{\Vert }^2+\Vert u–v{\Vert }^2\right)=\epsilon$
3. 概率修正：
   • 由$t=O\left(\frac{1}{{\epsilon }^2}\log \frac{1}{\delta }\right)$假设$t\ge \frac{4}{{\epsilon }^2–{\epsilon }^3}\ln \frac{4}{\delta }$，即$2e^{–\frac{\left({\epsilon }^2–{\epsilon }^3\right)t}{4}}\le \frac{\delta }{2}$
   • 故$\mathrm{Pr}\left[\frac{1}{d_{\text{proj}}}{\Vert \mathbf{S}(u+v)\Vert }^2\in (1\pm \epsilon )\Vert u+v{\Vert }^2\right]\ge 1–\frac{\delta }{2}$，$u+v$换成$u-v$也成立
   • 故$\text{Pr}\left[|⟨\psi (u),\psi (v)⟩–⟨u,v⟩|\le \epsilon \right]\ge 1–\delta$

$\text{2. }$事实$\text{A.4}$的证明

$\text{2.1. Muvera}$前两步

1️⃣文本嵌入：得到查询和段落文本各自的多向量嵌入

1. 查询嵌入$Q$： { q 1 , . . . , q m } \{q_1,...,q_m\} {q1​,...,qm​}，其中$q_i\subseteq {\mathbb{R}}^d$即为固定$d$维
2. 段落嵌入$P$： { p 1 , . . . , p n } \{p_1,...,p_n\} {p1​,...,pn​}，其中$p_i\subseteq {\mathbb{R}}^d$即为固定$d$维

2️⃣向量分桶：用$\text{SimHash}$将原有空间分为$2^{k_{\text{sim}}}$个桶，每个桶用长为$k_{\text{sim}}$的二进制向量编码

1. 法向抽取：从高斯分布中抽取$k_{\text{sim}}\ge 1$个向量$g_1,\dots ,g_{k_{\text{sim}}}\in {\mathbb{R}}^d$，作为$k_{\text{sim}}$个超平面的法向量
2. 空间划分：$\phi (x)=(1(⟨g_1,x⟩>0),\dots ,1(⟨g_{k_{\text{sim}}},x⟩>0))$
   • $1(⟨g_i,x⟩>0)$：当$⟨g_i,x⟩>0$成立(即$x$投影在超平面$g_i$的正侧)时，将该位设为$1$
3. 向量分桶：让所有的$m+n$个嵌入通过$\phi (\cdot )$得到长$k_{\text{sim}}$的二进制编码，相同编码者放入同一桶

$\text{2.2. }$声明的内容

👉记号：记$\forall x,y\in {\mathbb{R}}^b$夹角为$\theta (x,y)\in [0,\pi ]$，二进制编码$x,y$的海明距离为$\Vert x–y{\Vert }_0$

👉前提$1$：对$\forall q_i\in Q$以及$\forall p_j\in P$，给定$\forall \epsilon \text{≤}\frac{1}{2}$(与定理$\text{2.1}$统一)与$\forall \delta \le \epsilon$

👉前提$2$：令$k_{\text{sim}}=O\left(\frac{1}{\epsilon }\log \frac{m}{\delta }\right)$，其中$m=|Q|+|P|$

👉结论：$\left|\Vert \phi (q_i)–\phi (p_j){\Vert }_0-\frac{k_{\mathrm{sim}}\theta (q_i,p_j)}{\pi }\right|\text{≤}\sqrt{\epsilon }{k}_{\mathrm{sim}}$以$\mathrm{Pr}\ge 1–\left(\frac{\epsilon \delta }{m^2}\right)$的概率成立

$\text{2.3. }$声明的证明

➡️由以下分析可得$\mathrm{Pr}[1(⟨g_k,q_i⟩>0)\ne 1(⟨g_k,p_j⟩>0)]=\frac{\theta (q_i,p_j)}{\pi }$

1. 通过$\text{Gram-Schmidt}$过程，对$q_i,p_j$进行$\mathbf{R}$旋转
   • 令$d$维空间基为 B = { e ⃗ 1 , e ⃗ 2 , . . . , e ⃗ d } B{=}\{\vec{e}_1,\vec{e}_2,...,\vec{e}_d\} B={e 1​,e 2​,...,e d​}满足$\forall {\vec{e}}_i,{\vec{e}}_j\in B$有${\vec{e}}_i\text{⊥}{\vec{e}}_j$，让旋转矩阵$\mathbf{R}$将$q_i$旋转到${\vec{e}}_1$方向即$\mathbf{R}{q}_i=(1,0,...,0{)}^d$
   • 只考虑${\vec{e}}_1$及${\vec{e}}_2$组成的二维平面，则$\mathbf{R}{p}_j={\vec{e}}_1\cos (\mathbf{R}{q}_i,\mathbf{R}{p}_j)+{\vec{e}}_2\sin (\mathbf{R}{q}_i,\mathbf{R}{p}_j)$
     
   • 因$\theta (\mathbf{R}{q}_i,\mathbf{R}{p}_j)=\theta (q_i,p_j)$，则$\mathbf{R}{p}_j=e_1\cos \theta (q_i,p_j)+e_2\sin \theta (q_i,p_j)=(\cos \theta (q_i,p_j),\sin \theta (q_i,p_j),0,...,0{)}^d$
2. 对$g_k$进行$\mathbf{R}$旋转
   • (旋转不变性)对高斯向量$g_k\in {\mathbb{R}}^{d\text{×}1}\text{∼}\mathcal{N}(\text{0},{\text{I}}_{\mathbf{d}})$及旋转矩阵$\mathbf{R}\in {\mathbb{R}}^{d\text{×}d}$，有$\mathbf{R}{g}_k\text{∼}\mathcal{N}(\text{0},{\text{I}}_{\mathbf{d}})$
   • 故$\mathbf{R}{g}_k=(g_{k_1},...,g_{k_d})\text{∼}\mathcal{N}(\text{0},{\mathbf{I}}_{\mathbf{d}})$，其中$g_{k_1}\text{∼}\mathcal{N}(0,1)$和$g_{k_2}\text{∼}\mathcal{N}(0,1)$
   • 而$\mathbf{R}$在对$x,y$旋转时仅前两位起作用，故可令$\mathbf{R}{g}_k=(g_{k_1},g_{k_2},0,...,0{)}^d$，或$\mathbf{R}g=(\cos \varphi ,\sin \varphi ,0,...,0{)}^d$
3. 求相应内积
   • $⟨g_k,q_i⟩=⟨\mathbf{R}{g}_k,\mathbf{R}{q}_i⟩=(g_{k_1},g_{k_2},...,g_{k_d})(1,0,...,0{)}^{dT}=\cos \varphi$
   • $⟨g_k,p_j⟩=⟨\mathbf{R}{g}_k,\mathbf{R}{p}_j⟩=(\cos \varphi ,\sin \varphi ,0,...,0{)}^d(\cos \theta (q_i,p_j),\sin \theta (q_i,p_j),0,...,0{)}^{dT}=\cos (\varphi –\theta (q_i,p_j))$
4. 整理$\mathrm{Pr}[1(⟨g_k,q_i⟩>0)\ne 1(⟨g_k,p_j⟩>0)]$，变为$\mathrm{Pr}\left[1\left(\cos \varphi >0\right)\ne 1\left(\cos (\varphi –\theta (q_i,p_j))>0\right)\right]$
   • 情形$1$：$\cos \varphi >0$且$\cos (\varphi –\theta (q_i,p_j))\text{≤}0$，则$\varphi \in \left(–\frac{\pi }{2},\frac{\pi }{2}\right)$及$\varphi \in \left(\theta (q_i,p_j)+\frac{\pi }{2},\theta (q_i,p_j)+\frac{3\pi }{2}\right)$，交集长$|\varphi |=\theta (q_i,p_j)$
   • 情形$2$：$\cos \varphi \text{<}0$且$\cos (\varphi –\theta (q_i,p_j))\ge 0$，则$\varphi \in \left(\frac{\pi }{2},\frac{3\pi }{2}\right)$及$\varphi \in \left(\theta (q_i,p_j)\text{–}\frac{\pi }{2},\theta (q_i,p_j)+\frac{\pi }{2}\right)$，交集长$|\varphi |=\theta (q_i,p_j)$
   • 而$\varphi$总范围为$|\varphi {|}_{\max }=2\pi$，故$\mathrm{Pr}[1(⟨g_k,q_i⟩>0)\ne 1(⟨g_k,p_j⟩>0)]=\frac{2\theta (q_i,p_j)}{2\pi }$

➡️构造变量$Z_k$

1. 对每个 k ∈ { 1 , 2 , . . . , k sim } k{∈}\{1,2,...,k_{\text{sim}}\} k∈{1,2,...,ksim​}及对应的高斯向量$g_k$，定义$Z_k=1(⟨g_k,q_i⟩>0)\oplus 1(⟨g_k,p_j⟩>0)$，即二者不相等时$Z_k=1$
   
2. 由海明距离的定义(两二进制编码上下对齐后有多少对应位不同)，则有$\Vert \phi (q_i)–\phi (p_j){\Vert }_0=\sum _{k=1}^{k_{\text{sim}}}{Z}_k$
3. 而$\mathrm{Pr}[1(⟨g_k,q_i⟩>0)\ne 1(⟨g_k,p_j⟩>0)]=\frac{\theta (q_i,p_j)}{\pi }$故$\mathbb{E}\left[Z_k\right]=1\left(\frac{\theta (q_i,p_j)}{\pi }\right)+0\left(1–\frac{\theta (q_i,p_j)}{\pi }\right)=\frac{\theta (q_i,p_j)}{\pi }$
4. 故$\left|\Vert \phi (q_i)–\phi (p_j){\Vert }_0-\frac{k_{\mathrm{sim}}\theta (q_i,p_j)}{\pi }\right|=\left|\sum _{k=1}^{k_{\text{sim}}}{Z}_k-\mathbb{E}\left[\sum _{k=1}^{k_{\text{sim}}}{Z}_k\right]\right|$，故需证$\mathrm{Pr}\left[\left|\sum _{k=1}^{k_{\text{sim}}}{Z}_k-\mathbb{E}\left[\sum _{k=1}^{k_{\text{sim}}}{Z}_k\right]\right|\ge \sqrt{\epsilon }{k}_{\text{sim}}\right]\text{≤}\left(\frac{\epsilon \delta }{m^2}\right)$

➡️进一步转换

1. 由$\text{Hoeffding}$不等式，则$Z_k\in [0,1]$有$\mathrm{Pr}\left[\left|\sum _{k=1}^n{Z}_k-\mathbb{E}\left[\sum _{k=1}^n{Z}_k\right]\right|\ge t\right]\text{≤}2e^{–\frac{2t^2}{n}}$
2. 令$t=\sqrt{\epsilon }{k}_{\text{sim}}$与$n=k_{\text{sim}}$，则$\mathrm{Pr}\left[\left|\sum _{k=1}^{k_{\text{sim}}}{Z}_k-\mathbb{E}\left[\sum _{k=1}^{k_{\text{sim}}}{Z}_k\right]\right|\ge \sqrt{\epsilon }{k}_{\text{sim}}\right]\text{≤}2e^{–2\epsilon k_{\text{sim}}}$，需证$2e^{–2\epsilon k_{\text{sim}}}\text{≤}\frac{\epsilon \delta }{m^2}$即$k_{\mathrm{sim}}\ge \frac{1}{2\epsilon }\ln \frac{2m^2}{\epsilon \delta }$
3. 只需验证$k_{\text{sim}}=O\left(\frac{1}{\epsilon }\log \frac{m}{\delta }\right)\ge \frac{1}{2\epsilon }\ln \frac{2m^2}{\epsilon \delta }$
   • 令$\frac{C}{\epsilon }\ln \frac{m}{\delta }\ge k_{\text{sim}}\ge \frac{1}{2\epsilon }\ln \frac{2m^2}{\epsilon \delta }$，需验证$\frac{C}{\epsilon }\ln \frac{m}{\delta }\ge \frac{1}{2\epsilon }\ln \frac{2m^2}{\epsilon \delta }$，即上界足以覆盖下界
   • 故$(2C–2)\ln m–(2C–1)\ln \delta \ge \ln 2–\ln \epsilon$
   • 令$\{\begin{array}{l}2C–2\ge 1\\ 2C–1\ge 1\end{array}$及$\{\begin{array}{l}2\le m\\ \delta \le \epsilon \end{array}$则上式成立，解得$C\ge \frac{3}{2}$及$m\ge 2,\delta \le \epsilon$，其中$m=|Q|+|P|\ge 2$隐性成立
   • 只需让$\delta \le \epsilon$结论$O\left(\frac{1}{\epsilon }\log \frac{m}{\delta }\right)\ge \frac{1}{2\epsilon }\ln \frac{2m^2}{\epsilon \delta }$就成立，证毕