Dvoretzkyの定理

同義語:Dvoretzky's theoremDvoretzky theoremDvoretzky–Milmanの定理Dvoretzky–Milman theorem

概要

Dvoretzkyの定理(Dvoretzky's theorem)とは、ある絶対定数 $c>0$ があって、任意の $n$ 次元実ノルム空間と $0< \varepsilon< 1$ について、次元 $k\ge c\,\varepsilon^2\log n/\log(12/\varepsilon)$ の部分空間で、ある Euclid ノルムと $1\pm\varepsilon$ の精度で一致するものがあるという定理である。Milman の方法では、Gauss 測度の集中によって Gauss 行列の像がほぼ Euclid になることを示し、体積最大の楕円体の位置と Dvoretzky–Rogers の補題で次元 $\log n$ を得る。$\ell^\infty$ ノルムの例から $\log n$ の次数は改良できない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: ノルム空間, 多変量正規分布, 対数Sobolev不等式, 内積空間

Dvoretzky の定理(Dvoretzky's theorem)は、どんな有限次元のノルム空間にも、次元が無限に大きくなるにつれて大きな次元の「ほとんど Euclid 空間」の部分空間があることを述べる。正確には、ある絶対定数 $c>0$ があって、$n$ 次元の実ノルム空間 $X$ と $0< \varepsilon< 1$ について、次元 $k\ge c\,\varepsilon^2\log n/\log(12/\varepsilon)$ の部分空間 $V$ と $V$ の上の Euclid ノルム $\lvert\cdot\rvert'$ で
$$ (1-\varepsilon)\lvert v\rvert'\le\|v\|\le(1+\varepsilon)\lvert v\rvert'\qquad(v\in V) $$
となるものがある。幾何の言葉では、原点について対称な凸体を原点を通る適当な $k$ 次元の平面で切ると、切り口はほとんど楕円になる。
A. Grothendieck の予想を A. Dvoretzky が 1959–61 年に証明し、V. D. Milman が 1971 年に測度の集中を使った確率論的な証明を与えた(Ver18 p. 283。年は同 pp. 287・290 の文献 [73]・[74]・[148])。この記事は Milman の方法で証明する。鍵は、$\mathbb{R}^n$ の標準正規分布に従う $g$ について、Lipschitz 関数 $\|g\|$ が平均の近くに強く集中することである。$n$ 次の正方行列ではなく $n\times k$ の Gauss 行列 $G$ をとると、$\|Gx\|$ は単位球面上のほぼすべての方向でほぼ一定になり、像 $G(\mathbb{R}^k)$ がほとんど Euclid な部分空間になる。

問い答え
一般の形$k\lesssim\varepsilon^2(E\Vert g\Vert /b)^2$ なら Gauss 行列の像はほぼ Euclid(thm-dv-milman)
次元 $\log n$ の出どころ最大体積の楕円体の位置で $E\Vert g\Vert \ge\frac14\sqrt{\log(n/2)}$(lem-dv-dr、lem-dv-max)
主定理どんなノルムでも次元 $c\varepsilon^2\log n/\log(12/\varepsilon)$(thm-dv-main)
$\log n$ は最良か$\ell^\infty$ ノルムでは次元は $O(\log n)$ を超えない(prop-dv-linf)
$\ell^1$ ノルム次元を $n$ に比例させられる(ex-dv-l1)

定義と準備

$\mathbb{R}^n$ の標準内積を $\langle\cdot,\cdot\rangle$、Euclid ノルムを $\lvert\cdot\rvert$ と書く。$\mathbb{R}^n$ のノルム $\|\cdot\|$ は、どの 2 つも同値なので(ノルム空間)、$\|x\|\le b\lvert x\rvert$ となる $b>0$ がある。このとき $\lvert\|x\|-\|y\|\rvert\le\|x-y\|\le b\lvert x-y\rvert$ なので、$x\mapsto\|x\|$ は定数 $b$ の Lipschitz 関数である。

Banach–Mazur 距離

同じ次元の実ノルム空間 $X,Y$ について
$$ d(X,Y):=\inf\{\|T\|\,\|T^{-1}\|: T\colon X\to Y\text{ は線形同型}\} $$
を Banach–Mazur 距離 という。$\ell_2^k$ を $\mathbb{R}^k$ に Euclid ノルムを入れた空間とする。

$d(V,\ell_2^k)\le D$ とは、$V$ の上の Euclid ノルム(内積から来るノルム)$\lvert\cdot\rvert'$ で $\lvert v\rvert'\le\|v\|\le D\lvert v\rvert'$ となるものがあることと同じである($\lvert v\rvert':=\lvert T^{-1}v\rvert$ と定数倍で移り合う)。

球面の網

$0< \delta\le1$ とする。単位球面 $S^{k-1}\subset\mathbb{R}^k$ の有限部分集合 $\mathcal N$ で、$\lvert\mathcal N\rvert\le(3/\delta)^k$ かつ、すべての $x\in S^{k-1}$ について $\lvert x-y\rvert\le\delta$ となる $y\in\mathcal N$ があるものがとれる。

体積で数える

$S^{k-1}$ の点の集合で、どの 2 点の距離も $\delta$ より大きいものを $\delta$ 分離集合という。$\delta$ 分離集合 $\mathcal N$ について、半径 $\delta/2$ の球 $y+\frac\delta2B$($y\in\mathcal N$、$B$ は単位球)は互いに交わらず、すべて $(1+\frac\delta2)B$ に含まれるので、体積を比べて $\lvert\mathcal N\rvert(\delta/2)^k\le(1+\delta/2)^k$、すなわち $\lvert\mathcal N\rvert\le(1+2/\delta)^k\le(3/\delta)^k$ である。点の数に上限があるので、点の数が最大の $\delta$ 分離集合 $\mathcal N$ がとれる。どの $x\in S^{k-1}$ についても、$\lvert x-y\rvert\le\delta$ となる $y\in\mathcal N$ がある。そうでなければ $\mathcal N\cup\{x\}$ がより大きい $\delta$ 分離集合になるからである。$\square$

Gauss 測度の集中

$g$ を $\mathbb{R}^n$ の標準正規分布に従う確率変数、$F\colon\mathbb{R}^n\to\mathbb{R}$ を定数 $b$ の Lipschitz 関数とすると、$r\ge0$ について
$$ P\bigl(\lvert F(g)-E[F(g)]\rvert\ge r\bigr)\le2e^{-r^2/(2b^2)} $$
である。

対数Sobolev不等式 の定理「Gross の不等式」により標準正規分布は $\mathrm{LSI}(1)$ を満たし、同じ記事の定理「Herbst の議論による集中不等式」を定数 $1$ の Lipschitz 関数 $F/b$ と $-F/b$ に当てると、片側ずつ $e^{-r^2/(2b^2)}$ 以下である。$\square$

Milman の定理

Gauss 行列の像はほとんど Euclid

$\|\cdot\|$ を $\mathbb{R}^n$ のノルムで $\|x\|\le b\lvert x\rvert$ をみたすものとし、$\mathbb{R}^n$ の標準正規分布に従う $g$ について $E:=E\|g\|$ とおく。$0< \varepsilon< 1$ と整数 $k\ge1$ が
$$ k\le\frac{\varepsilon^2E^2}{64\,b^2\log(12/\varepsilon)} $$
をみたすとし、$G$ を成分が独立な標準正規分布に従う $n\times k$ 行列とする。このとき確率 $1-2(\varepsilon/12)^k$ 以上で、すべての $x\in\mathbb{R}^k$ について
$$ (1-\varepsilon)E\lvert x\rvert\le\|Gx\|\le(1+\varepsilon)E\lvert x\rvert $$
が成り立つ。特に $G$ は単射で、$V:=G(\mathbb{R}^k)$ は $d(V,\ell_2^k)\le\frac{1+\varepsilon}{1-\varepsilon}$ をみたす $k$ 次元の部分空間である。

1 方向の集中と網の議論

1 方向。 $x\in S^{k-1}$ を固定すると、$Gx$ の成分 $\sum_jg_{ij}x_j$ は独立に $N(0,\lvert x\rvert^2)=N(0,1)$ に従う(多変量正規分布 の定理「1 次変換で多変量正規分布は保たれる」)。よって $Gx$ は $g$ と同じ分布に従い、$E\|Gx\|=E$ で、lem-dv-gauss から $P(\lvert\|Gx\|-E\rvert\ge\eta E)\le2e^{-\eta^2E^2/(2b^2)}$ である。
網の上で同時に。 $\delta:=\eta:=\varepsilon/4$ とし、lem-dv-net の網 $\mathcal N$($\lvert\mathcal N\rvert\le(12/\varepsilon)^k$)をとる。事象 $\Omega$ を「すべての $y\in\mathcal N$ で $\lvert\|Gy\|-E\rvert\le\eta E$」とすると
$$ P(\Omega^c)\le2\Bigl(\frac{12}\varepsilon\Bigr)^k\exp\Bigl(-\frac{\varepsilon^2E^2}{32b^2}\Bigr)\le2\Bigl(\frac{12}\varepsilon\Bigr)^k\Bigl(\frac{12}\varepsilon\Bigr)^{-2k}=2\Bigl(\frac\varepsilon{12}\Bigr)^k $$
である。2 つ目の不等号で $k$ の仮定 $\frac{\varepsilon^2E^2}{32b^2}\ge2k\log(12/\varepsilon)$ を使った。
球面全体へ。 $\Omega$ の上で考える。$A:=\max_{x\in S^{k-1}}\|Gx\|$ とおく(連続関数のコンパクト集合での最大値)。$x\in S^{k-1}$ について $\lvert x-y\rvert\le\delta$ となる $y\in\mathcal N$ をとると、$\|G(x-y)\|\le\delta A$ なので
$$ \|Gx\|\le\|Gy\|+\delta A\le(1+\eta)E+\delta A $$
である。$x$ について最大をとって $A\le\frac{1+\eta}{1-\delta}E\le(1+\varepsilon)E$ を得る($\frac{1+\varepsilon/4}{1-\varepsilon/4}\le1+\varepsilon$ は $\varepsilon\le2$ で成り立つ)。下からは
$$ \|Gx\|\ge\|Gy\|-\delta A\ge(1-\eta)E-\delta(1+\varepsilon)E=\Bigl(1-\frac\varepsilon2-\frac{\varepsilon^2}4\Bigr)E\ge(1-\varepsilon)E $$
である。$x\in S^{k-1}$ で示したので、斉次性からすべての $x\in\mathbb{R}^k$ で成り立つ。$\varepsilon< 1$ なので下の評価から $G$ は単射で、$\lvert v\rvert':=(1-\varepsilon)E\lvert G^{-1}v\rvert$ とおけば $\lvert v\rvert'\le\|v\|\le\frac{1+\varepsilon}{1-\varepsilon}\lvert v\rvert'$ である。$\square$

$\|\cdot\|=\lvert\cdot\rvert$ なら $(E/b)^2=(E\lvert g\rvert)^2$ は $n$ の程度で、$k$ を $n$ に比例させられる。どのノルムでも同じ結論を得るには、$b$ と $E$ の比を良くする座標のとり方が要る。

主定理

Dvoretzky–Rogers の補題

$K:=\{x\in\mathbb{R}^n:\|x\|\le1\}$ とし、原点を中心とする楕円体で $K$ に含まれるもののうち、体積が最大のものが単位球 $B$ であるとする。このとき $\|x\|\le\lvert x\rvert$ で、$n/2$ 次元以上の任意の部分空間 $F$ は $\|x\|\ge\frac12$ となる単位ベクトル $x$ を含む。

楕円体を膨らませて体積を比べる

$B\subset K$ から $\|x\|\le\lvert x\rvert$ である。$F$ の次元を $q\ge n/2$、$p:=n-q$ とし、$\lambda:=\max\{\|z\|:z\in F,\ \lvert z\rvert=1\}$ が $\frac12$ より小さいと仮定して矛盾を導く。
$a,\beta>0$ を $a^2+\lambda^2\beta^2=1$ となるようにとり、楕円体
$$ \mathcal E:=\Bigl\{y+z:\ y\in F^\perp,\ z\in F,\ \frac{\lvert y\rvert^2}{a^2}+\frac{\lvert z\rvert^2}{\beta^2}\le1\Bigr\} $$
を考える($p=0$ のときは $\mathcal E=\beta B$ で、$a$ は使わない)。$\lvert y\rvert=as$、$\lvert z\rvert=\beta t$、$s^2+t^2\le1$ と書けば、Cauchy–Schwarz の不等式から
$$ \|y+z\|\le\|y\|+\|z\|\le\lvert y\rvert+\lambda\lvert z\rvert=as+\lambda\beta t\le\sqrt{a^2+\lambda^2\beta^2}=1 $$
なので $\mathcal E\subset K$ である。$\mathcal E$ の体積は $B$ の $a^p\beta^q$ 倍である。$a^2:=p/n$、$\beta^2:=q/(n\lambda^2)$ とおくと $a^2+\lambda^2\beta^2=1$ で、
$$ (a^p\beta^q)^2=\Bigl(\frac pn\Bigr)^p\Bigl(\frac qn\Bigr)^q\lambda^{-2q} $$
である。$\log$ の凹性から $p\log\frac pn+q\log\frac qn\ge-n\log2$(2 値のエントロピーは $\log 2$ 以下)なので $\bigl(\frac pn\bigr)^p\bigl(\frac qn\bigr)^q\ge2^{-n}$、また $\lambda< \frac12< 1$、$2q\ge n$ から $\lambda^{-2q}\ge\lambda^{-n}>2^n$ である。よって $\mathcal E$ の体積は $B$ より大きく、$B$ の最大性に反する。$\square$

Gauss 変数の最大値

$\gamma_1,\dots,\gamma_m$($m\ge4$)が独立に標準正規分布に従うとき、$E\max_i\lvert\gamma_i\rvert\ge\frac12\sqrt{\log m}$ である。

裾の下界

要点:$t=\sqrt{\log m}$ で $P(\max_i\lvert\gamma_i\rvert\le t)\le\frac12$ を示せば、$E\max\ge tP(\max>t)\ge t/2$ である。

詳しい証明を開く

$\varphi$ を標準正規分布の密度とする。$h(t):=\int_t^\infty\varphi-\frac t{1+t^2}\varphi(t)$ は $h'(t)=-\frac{2\varphi(t)}{(1+t^2)^2}< 0$、$h(t)\to0$($t\to\infty$)なので $h\ge0$、すなわち $P(\gamma_1>t)\ge\frac t{1+t^2}\varphi(t)$ である。$t^2=\log m$ なら $m\varphi(t)=\sqrt m/\sqrt{2\pi}$ で、$P(\max\le t)=(1-P(\lvert\gamma_1\rvert>t))^m\le\exp(-mP(\lvert\gamma_1\rvert>t))\le\exp(-u(m))$、$u(m):=\sqrt{2/\pi}\,\sqrt m\,\frac t{1+t^2}$ である。$L=\log m$ について $\frac{d}{dL}\log u=\frac12+\frac1{2L}-\frac1{1+L}>0$ なので $u$ は増加し、$u(4)=0.787\ldots>\log2$ である。よって $P(\max\le t)\le\frac12$ である。$\square$

Dvoretzky の定理

$n\ge6$、$0< \varepsilon< 1$ とし、
$$ k:=\Bigl\lfloor\frac{\varepsilon^2\log(n/2)}{1024\log(12/\varepsilon)}\Bigr\rfloor $$
とおく。$k\ge1$ なら、$n$ 次元の任意の実ノルム空間 $X$ は、$d(V,\ell_2^k)\le\frac{1+\varepsilon}{1-\varepsilon}$ をみたす $k$ 次元の部分空間 $V$ をもつ。

位置を選んでから Milman の定理を当てる

位置。 $X=(\mathbb{R}^n,\|\cdot\|)$ とし、$K$ を単位球とする。原点を中心とする楕円体は正定値対称行列 $T$ で $T(B)$ と書ける。$T(B)\subset K$ をみたす半正定値対称行列 $T$ の全体は、$K$ が有界なので有界閉集合で、$\varepsilon_0B\subset K$ となる $\varepsilon_0>0$ について $\varepsilon_0I$ を含む。連続関数 $\det T$ はこの上で正の最大値をとり、そこで $T_0$ は正定値である。新しいノルム $\|x\|_0:=\|T_0x\|$ は $X$ と等長な空間を与え、その単位球 $T_0^{-1}K$ の中で体積最大の楕円体は $B$ である。Banach–Mazur 距離は等長同型で変わらないので、はじめから $B$ が体積最大と仮定してよい。
$E\|g\|$ の下界。 lem-dv-dr を、$F=\mathbb{R}^n$、$\{x_1\}^\perp$、$\{x_1,x_2\}^\perp,\dots$ に順に当てて、正規直交な $x_1,\dots,x_m$($m:=\lfloor n/2\rfloor+1\ge4$、$F$ の次元 $n-i+1\ge n/2$)で $\|x_i\|\ge\frac12$ となるものをとる。$\gamma_i:=\langle g,x_i\rangle$、$R:=g-\sum_{i\le m}\gamma_ix_i$ とおくと、$\gamma_1,\dots,\gamma_m$ は独立に標準正規分布に従い $R$ と独立である(多変量正規分布 の定理「無相関なら独立」)。符号 $\epsilon_1,\dots,\epsilon_m,\epsilon_0\in\{\pm1\}$ を固定すると、$(\epsilon_i\gamma_i)_i$ と $\epsilon_0R$ の組は元の組と同じ分布に従う。よって $\epsilon_i$ を $g$ と独立な等確率の符号として
$$ E\|g\|=E\Bigl\|\sum_{i\le m}\epsilon_i\gamma_ix_i+\epsilon_0R\Bigr\| $$
である。$g$ を固定し、$\lvert\gamma_{i^*}\rvert=\max_i\lvert\gamma_i\rvert$ となる $i^*$ をとる。$\epsilon_{i^*}$ 以外の符号について平均すると、ベクトルの平均は $\epsilon_{i^*}\gamma_{i^*}x_{i^*}$ で、ノルムは凸なので
$$ E\|g\|\ge E\|\gamma_{i^*}x_{i^*}\|\ge\frac12E\max_{i\le m}\lvert\gamma_i\rvert\ge\frac14\sqrt{\log m}\ge\frac14\sqrt{\log(n/2)} $$
である(lem-dv-max)。
Milman の定理。 $b=1$ なので、thm-dv-milman の条件は $k\le\varepsilon^2E^2/(64\log(12/\varepsilon))$ で、$E^2\ge\frac1{16}\log(n/2)$ から定義の $k$ はこれをみたす。確率が正なので、$d(G(\mathbb{R}^k),\ell_2^k)\le\frac{1+\varepsilon}{1-\varepsilon}$ となる $G$ がある。$\square$

定数と双対な形

この証明の定数 $1/1024$ は簡単さを優先したもので、$k\ge1$ となるのは $n$ が非常に大きいときに限られる。結論の要点は、次元が $n$ とともに $\log n$ の速さで無限に大きくなることである。Ver18 Theorem 11.3.3(p. 280)は、有界集合の Gauss 行列による像の凸包がほぼ球になるという双対な形で、$\log(1/\varepsilon)$ の因子を含まない評価を述べる。

例

$\ell^1$ ノルム:次元に比例する部分空間

$\|x\|_1=\sum_i\lvert x_i\rvert$ とする。Cauchy–Schwarz の不等式から $\|x\|_1\le\sqrt n\lvert x\rvert$ で $b=\sqrt n$、$E\|g\|_1=nE\lvert g_1\rvert=n\sqrt{2/\pi}$ である。よって $(E/b)^2=2n/\pi$ で、thm-dv-milman から $k\le\frac{\varepsilon^2n}{32\pi\log(12/\varepsilon)}$ なら、$\ell_1^n$ は $d(V,\ell_2^k)\le\frac{1+\varepsilon}{1-\varepsilon}$ の $k$ 次元部分空間をもつ。$n=10^6$、$\varepsilon=1/2$ なら $k=782$ がとれる。$\ell_1^n$ の単位球(正軸体)は頂点が $2n$ 個しかない多面体だが、無作為な $k$ 次元の切り口はほとんど円い。

$\ell^\infty$ ノルムの上界

$\ell_\infty^n=(\mathbb{R}^n,\|\cdot\|_\infty)$ の $k$ 次元部分空間 $V$ が $d(V,\ell_2^k)\le D$ をみたせば、$k\le2D^2\log(2n)+4$ である。

Gauss 変数の最大値を上から抑える

仮定から、線形写像 $T\colon\mathbb{R}^k\to V$ で $\lvert x\rvert\le\|Tx\|_\infty\le D\lvert x\rvert$ となるものがある。$(Tx)_i=\langle x,w_i\rangle$ となる $w_i\in\mathbb{R}^k$ をとると、$\lvert w_i\rvert=\max_{\lvert x\rvert=1}\lvert(Tx)_i\rvert\le D$ である。$\gamma$ を $\mathbb{R}^k$ の標準正規分布に従う確率変数とすると、$Z_i:=\langle\gamma,w_i\rangle$ は $N(0,\lvert w_i\rvert^2)$ に従う。$\lambda>0$ について、Jensen の不等式から
$$ e^{\lambda E\max_i\lvert Z_i\rvert}\le E\,e^{\lambda\max_i\lvert Z_i\rvert}\le\sum_{i=1}^nE\bigl(e^{\lambda Z_i}+e^{-\lambda Z_i}\bigr)\le2n\,e^{\lambda^2D^2/2} $$
なので、$E\max_i\lvert Z_i\rvert\le\frac{\log(2n)}\lambda+\frac{\lambda D^2}2$ で、$\lambda=\sqrt{2\log(2n)}/D$ として $E\|T\gamma\|_\infty\le D\sqrt{2\log(2n)}$ である。一方 $\|T\gamma\|_\infty\ge\lvert\gamma\rvert$ で、対数Sobolev不等式 の例「高次元の Gauss 測度」から $(E\lvert\gamma\rvert)^2\ge k-4$ である。よって $k-4\le2D^2\log(2n)$ である。$\square$

$D$ を固定すると、$\ell_\infty^n$ のほとんど Euclid な部分空間の次元は $O(\log n)$ を超えない。thm-dv-main の $\log n$ の次数は、すべての空間に通用する評価としては改良できない。$\ell_\infty^n$ の単位球は立方体で、$E\|g\|_\infty$ は $\sqrt{2\log(2n)}$ 以下、$b=1$ なので、thm-dv-milman が与える次元もこの程度である。

反例:条件を外すと成り立たないこと

主張外す条件反例成り立たなくなること
thm-dv-milman次元の上限 $k\le\varepsilon^2E^2/(64b^2\log(12/\varepsilon))$$\ell_\infty^n$ で $k=n$、$\varepsilon=1/2$、$n\ge200$$G$ は確率 $1$ で可逆、$V=\mathbb{R}^n$ で $d(V,\ell_2^n)\le3$ は成り立たない
thm-dv-milman部分空間が Gauss 行列の像であること$\ell_\infty^n$ の座標部分空間($G$ の代わりに最初の $2$ 個の基本ベクトルを並べた行列)、$\varepsilon=1/10$$\Vert x\Vert_\infty/\lvert x\rvert$ は $1/\sqrt2$ から $1$ まで動き、比 $\sqrt2>\frac{1.1}{0.9}$
lem-dv-dr単位球が体積最大の楕円体であること$\Vert x\Vert:=\lvert x\rvert/4$($K=4B$ は $B$ を含むが、$4B$ の方が大きい)すべての単位ベクトルで $\Vert x\Vert=1/4< 1/2$
反例の確かめ

確かめ:

3 行の確かめを開く

1 行目:正方行列 $G$ の行列式は $0$ でない確率が $1$ なので $V=\mathbb{R}^n$ である。$d(\ell_\infty^n,\ell_2^n)\le3$ なら、prop-dv-linf から $n\le18\log(2n)+4$ である。$n=200$ では右辺は $18\cdot5.99\ldots+4=111.8\ldots< 200$ で、右辺は $n$ より遅く増えるので、$n\ge200$ で成り立たない。

2 行目:$\|Gx\|_\infty=\max(\lvert x_1\rvert,\lvert x_2\rvert)$ で、$x=(1,0)$ では $\lvert x\rvert$ に等しく、$x=(1,1)$ では $\lvert x\rvert/\sqrt2$ である。結論 $(1-\varepsilon)E\lvert x\rvert\le\|Gx\|\le(1+\varepsilon)E\lvert x\rvert$ がある定数 $E$ で成り立つなら、比 $\sqrt2$ は $\frac{1+\varepsilon}{1-\varepsilon}=\frac{11}9$ 以下のはずだが、$\sqrt2=1.414\ldots>1.222\ldots$ である。$n$ を十分大きくとれば $k=2$ は次元の上限をみたす($E\|g\|_\infty\to\infty$)。

3 行目:$B\subset K=4B$ だが、$4B$ は $K$ に含まれる体積のより大きい楕円体である。$\|x\|=\lvert x\rvert/4$ なので、どの部分空間の単位ベクトルでも $\|x\|=1/4$ である。

応用

  • 高次元の凸体。Milman の証明は、高次元では Lipschitz 関数がほぼ定数になるという「測度の集中」の考え方を、凸体の幾何に持ち込んだ。証明の 2 つの段(1 方向の集中と、網による球面全体への拡張)は、濃度不等式 を使う議論の典型である。
  • 無作為な切り口と射影。thm-dv-milman は特定の部分空間でなく、Gauss 行列の像という無作為な部分空間のほとんどすべてがほぼ Euclid であることを示す。双対的には、高次元の凸体を無作為な低次元の部分空間へ射影するとほぼ球になる(Ver18 Theorem 11.3.3、p. 280)。
  • Banach 空間論。無限次元の Banach 空間はすべて、どんな $k$ についても $\ell_2^k$ に $1+\varepsilon$ の精度で近い部分空間を含む(有限次元の部分空間に thm-dv-main を当てる)。Hilbert 空間がすべての Banach 空間の中に「局所的に」現れることを意味する。

歴史と出典

出典

A. Dvoretzky は 1959 年の速報と 1961 年の論文で、任意の $n$ 次元ノルム空間が、$n\to\infty$ とともに次元が無限に大きくなるほとんど Euclid な部分空間をもつことを示し、Grothendieck の予想を解いた(Dvo61)。V. D. Milman は 1971 年に測度の集中による確率論的な証明を与え、最良の次元の研究を始めた(Mil71。いずれも Ver18 p. 283 の記述による。年は同 pp. 287・290 の文献 [73]・[74]・[148])。この記事の証明は Milman の方法を Gauss 測度で書いたもので、体積最大の楕円体の位置と Dvoretzky–Rogers の補題を組み合わせて $E\|g\|$ を下から抑える。

関連項目

参考文献

[1]
Aryeh Dvoretzky, Some results on convex bodies and Banach spaces, Proceedings of the International Symposium on Linear Spaces (Jerusalem, 1960), Jerusalem Academic Press,, 1961
[2]
Vitali D. Milman, New proof of the theorem of Dvoretzky on sections of convex bodies, Functional Analysis and Its Applications 5 (1971), 1971
[3]
Roman Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science, 1st ed., Cambridge University Press, 2018, Theorem 11.3.3(p. 280)、§11.4(p. 283)、文献表(pp. 287・290)。番号・頁は著者公開の第 1 版による

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する