High dimension geometry is surprisingly different from low dimensional geometry
-
Example 1: Volume concentrates on shell.
-
Example 2: As \(d\rightarrow \infty\), the area and the volumn of \(d\)-dimensional unit ball \(\rightarrow \infty\).
-
Example 3：Volume (of ball) concentrates on equator.
Thm 2.7. Let \(A\) denote the portion of the ball with \(x_1\ge \frac{c}{\sqrt{d-1}}\) and let \(H\) denote the upper hemisphere. Then
-
Example 4:
Thm 2.8. Consider drawing \(n\) iid samples \(x_1,...,x_n\) from a unit ball. Then with probability \(1-O(\frac{1}{n})\) we have
- \(\Vert x_i\Vert\ge 1-\frac{2\ln n}{d}\) for all \(i\).
- \(\Vert x_i^Tx_j\Vert\le\frac{\sqrt{6\ln n}}{\sqrt{d-1}}\) for all \(i\neq j\).
Gaussians in High Dimension
Def (Sub-gaussian variable). For some \(k>0\),
\[\mathbb{P}\{|X|>t\}\le 2\exp(-t^2/k^2),\forall t>0. \]Equivalent statement: For some \(\sigma^2>0\),
\[\mathbb{E}\left(e^{\lambda(X-\mu)}\right)\le \exp\left(\frac{\sigma^2k^2}{2}\right). \]Def (Sub-gaussian norm).
\[\Vert X\Vert_{\psi_2}=\inf\{t>0\mid \mathbb{E}\left(e^{X^2/t^2}\right)\le 2\}. \]e.g. \(X\sim N(0,\sigma^2)\), \(\Vert X\Vert_{\psi_2}=\sigma^2\).
Thm. Let \(X_1,...,X_n\) be iid, \(\mathbb{E}(X_i)=0\), then \(\forall t>0\),
\[\mathbb{P}\left\{\left|\sum X_i\right|>t\right\}\le 2\exp\left(-\frac{ct^2}{\sum \Vert X_i\Vert_{\psi_2}}\right). \]Def (Sub-exponential variable). For some \(k>0\),
\[\mathbb{P}\{|X|>t\}\le 2\exp(-t/k),\forall t>0. \]Def (Sub-exponential norm).
\[\Vert X\Vert_{\psi_1}=\inf\{t>0\mid \mathbb{E}\left(e^{|X|/t}\right)\le 2\}. \]e.g. \(X\sim N(0,\sigma^2)\), \(\Vert X^2\Vert_{\psi_1}=\sigma^2\).
Thm (Bernstein's Inequality).
Let \(X_1,...,X_n\) be iid, \(\mathbb{E}(X_i)=0\), then \(\forall t>0\),
\[\mathbb{P}\left\{\left|\sum X_i\right|>t\right\}\le 2\exp\left(-c\min\left(\frac{t^2}{\sum \Vert X_i\Vert^2_{\psi_1}},\frac{t}{\max \Vert X_i\Vert_{\psi_1}}\right)\right). \]Now we want to show gaussian concentrates near the annulus "shell".
Consider a \(X\sim N(0,I_d)\), by the fact that \(X_i^2\) is 1-subexponential, we can apply Bernstein's Inequality to obtain
\[\mathbb{P}\left\{\left|\sum X_i^2-\sum \mathbb{E}(X_i^2)\right|>t\right\}\le \exp\left(-\min\left(\frac{t^2}{d},t\right)\right). \]Let \(t=\sqrt{\log\frac{1}{\delta}d}<d\) , then
\[\mathbb{P}\left\{\left|\Vert X\Vert^2-\sum \mathbb{E}(X_i^2)\right|>t\right\}\le \delta. \]It means that if \(X'\sim N(0,\frac{I_d}{\sqrt{d}})\), then \(\Vert X'\Vert^2\) concentrates near a shell of thickness \(\frac{1}{\sqrt{d}}\).
Thm 2.9 (Gaussian Annulus Theorem). For \(X\sim N(0,I_d)\), for any \(\beta\le\sqrt{d}\), with probability \(\ge 1-3e^{-c\beta^2}\) we have
\[\sqrt{d}-\beta\le\Vert X\Vert\le \sqrt{d}+\beta. \] 标签：mathbb,Dimensional,right,frac,Vert,High,le,智应数,left From： https://www.cnblogs.com/xcyle/p/18167923