Cramér-Chernoff 方法

$\text{Pr}[X\geq a]\leq\min_{\lambda > 0}e^{-\lambda a}\mathbb{E}[e^{\lambda x}]$

$\square$

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

\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}

\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}$

$\square$

$\text{Pr}[|\langle u,v\rangle|\geq\varepsilon]\leq 4e^{-\varepsilon^2n/8}$

$\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$

Johnson-Lindenstrauss Lemma: 给定$N$ 个向量$v_1,v_2,...,v_N\in\mathbb{R}^m$$n>\frac{24\log N}{\varepsilon^2}$，而随机矩阵$A\in\mathbb{R}^{n\times m}$ 独立重复采样自$\mathcal{N}(0,\frac{1}{n})$。那么对于给定常数$\varepsilon\in(0,1)$，至少有$\frac{N-1}{N}$ 的概率，使得对于所有的$i\neq j$ 都有：

$(1-\varepsilon)\|v_i-v_j\|^2\leq\|Av_i-Av_j\|^2\leq(1+\varepsilon)\|v_i-v_j\|^2$

$\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$

Edited on Views times