Vietoris–Rips複体(Vietoris–Rips complex)とは、距離空間 $X$ と尺度 $r\ge0$ について、直径が $r$ 以下の空でない有限部分集合をすべて単体とする単体複体 $\operatorname{VR}_r(X)$ である。距離 $r$ 以下の 2 点を結んだグラフの旗複体であり、内在的 Čech 複体と $\operatorname{VR}_r\subset\check C_r\subset\operatorname{VR}_{2r}$ の関係にある。歪み $\eta$ の対応で結ばれた距離空間の複体の列は尺度を $\eta$ ずらした写像で行き来でき、持続ホモロジーが Gromov–Hausdorff 距離について安定になる。$\delta$ 双曲群では尺度を $\delta$ に応じて大きく取ると可縮になる。
Vietoris–Rips 複体は、距離空間 $X$ と尺度 $r\geq0$ から、「直径が $r$ 以下の有限部分集合」をすべて単体とする単体複体 $\operatorname{VR}_r(X)$ を作る構成である。点どうしの距離だけから決まり、$X$ を囲む空間を必要としない。$r$ を動かすと単体複体の増大列が得られ、点の集まりの「形」を尺度ごとに読み取る道具になる。
この構成は二つの場面で働く。一つは、有限な標本点から元の図形の位相を推定する計算である。ここでは、近い距離空間から近い複体の列が得られるという安定性が基礎になる。もう一つは、双曲群の幾何的群論である。ここでは、尺度を十分大きく取ると複体が可縮になることが、群の有限性の性質を導く。この記事では、定義と基本性質、Čech 複体との比較、Gromov–Hausdorff 距離についての安定性、双曲群の Rips 複体の可縮性を、証明をつけて述べる。
$(X,d)$ を距離空間、$r\geq0$ とする。$X$ の空でない有限部分集合 $\sigma$ で、直径 $\operatorname{diam}\sigma=\max_{x,x'\in\sigma}d(x,x')$ が $r$ 以下のもの全体を $\operatorname{VR}_r(X)$ と書く。$\operatorname{VR}_r(X)$ は頂点集合 $X$ の抽象単体複体であり、$X$ の尺度 $r$ の Vietoris–Rips 複体(Vietoris–Rips complex)という。単に Rips 複体ともいう。
単体の部分集合の直径はもとの直径以下なので、$\operatorname{VR}_r(X)$ は確かに単体複体である。$r\leq r'$ なら $\operatorname{VR}_r(X)\subset\operatorname{VR}_{r'}(X)$ で、増大する族 $(\operatorname{VR}_r(X))_{r\geq0}$ を Vietoris–Rips フィルトレーションとよぶ。以下、単体複体は幾何的単体複体として実現した位相空間 $\lvert\operatorname{VR}_r(X)\rvert$ も同じ記号で表す。
$X$ の空でない有限部分集合 $\sigma$ について、$\sigma\in\operatorname{VR}_r(X)$ であることと、$\sigma$ のどの $2$ 点も $\operatorname{VR}_r(X)$ の辺($1$ 単体)で結ばれていることは同値である。したがって $\operatorname{VR}_r(X)$ は $1$ 骨格で決まる。
$\operatorname{diam}\sigma\leq r$ は「すべての $x,x'\in\sigma$ について $d(x,x')\leq r$」と同じであり、後者は $\{x,x'\}\in\operatorname{VR}_r(X)$ と同じである。$\square$
頂点集合の上のグラフ $\Gamma$ について、$\Gamma$ の完全部分グラフの頂点集合をすべて単体とする単体複体を $\Gamma$ の旗複体(クリーク複体)という。命題は、$\operatorname{VR}_r(X)$ が「距離 $r$ 以下の $2$ 点を結んだグラフ」の旗複体であることを述べている。計算では、辺だけを求めれば高次の単体が自動的に決まる。
距離空間 $X$ と $r\geq0$ について、$X$ の空でない有限部分集合 $\sigma$ で、閉球 $B(x,r)=\{y\in X\mid d(x,y)\leq r\}$($x\in\sigma$)の共通部分が空でないもの全体を $\check C_r(X)$ と書き、内在的 Čech 複体という。
$\check C_r(X)$ は、$X$ の閉球による被覆 $\{B(x,r)\}_{x\in X}$ の開被覆の脈体と同じ組合せで作られる複体である。可換環論の Čech 複体(加群の複体)とは別のものである。
任意の距離空間 $X$ と $r\geq0$ について
$$
\operatorname{VR}_r(X)\subset\check C_r(X)\subset\operatorname{VR}_{2r}(X).
$$
$\sigma\in\operatorname{VR}_r(X)$ なら、$\sigma$ の一点 $x_0$ はどの $x\in\sigma$ からも距離 $r$ 以下なので、$x_0\in\bigcap_{x\in\sigma}B(x,r)$ である。$\sigma\in\check C_r(X)$ で $c$ が共通部分の点なら、$x,x'\in\sigma$ について $d(x,x')\leq d(x,c)+d(c,x')\leq2r$ である。$\square$
Čech 複体は旗複体ではない。どの $2$ 点の球も交わるのに $3$ 点の球が共通点をもたないことがあるからである。たとえば一辺 $1$ の正三角形の頂点 $a,b,c$ と各辺の中点の $6$ 点を $X$ とすると、$\check C_{1/2}(X)$ で $\{a,b\}$ は $ab$ の中点を共通点にもつので単体だが、$a,b,c$ のすべてから距離 $\frac12$ 以下の点は $X$ にないので $\{a,b,c\}$ は単体でない(平面の円板の被覆で考えた例は下の反例)。挟み込みは、Vietoris–Rips 複体が Čech 複体を尺度の因子 $2$ の範囲で近似していることを示す。内在的 Čech 複体のフィルトレーションも、下の thm-vr-stability と同じ形の安定性をもつ(CdSO14 Lemma 4.4、p. 8 と Theorem 5.2、p. 13)。
$n\geq4$ とし、巡回群 $\mathbb{Z}/n$ に生成元 $1$ についての語距離(円周上に並べた $n$ 点の、隣を距離 $1$ とする道の距離)を入れる。$\operatorname{VR}_1(\mathbb{Z}/n)$ の辺は隣り合う $2$ 点を結ぶ $n$ 本で、互いに隣り合う $3$ 点は $n\geq4$ では存在しないので $2$ 単体はない。よって $\operatorname{VR}_1(\mathbb{Z}/n)$ は $n$ 角形のグラフで、円周 $S^1$ と同相である。一方、$r\geq\lfloor n/2\rfloor$($=\operatorname{diam}\mathbb{Z}/n$)なら全体が一つの単体で、可縮である。
$n=4$ は平面の単位正方形の $4$ 頂点(ユークリッド距離)と同じ組合せになる。辺の長さは $1$、対角線は $\sqrt2$ なので、$1\leq r< \sqrt2$ で $\operatorname{VR}_r\cong S^1$、$r\geq\sqrt2$ で可縮である。
$X=\{\pm e_1,\pm e_2,\pm e_3\}\subset\mathbb{R}^3$ にユークリッド距離を入れる。$i\neq j$ なら $\lvert\pm e_i\mp e_j\rvert=\sqrt2$、$\lvert e_i-(-e_i)\rvert=2$ である。$\sqrt2\leq r< 2$ のとき、$\operatorname{VR}_r(X)$ の単体は「対蹠点の組 $\{e_i,-e_i\}$ を含まない部分集合」全体で、これは正八面体の境界の三角形分割そのものである。よって $\operatorname{VR}_r(X)\cong S^2$ である。$6$ 点だけから $2$ 次元球面が現れる。同じように、$\mathbb{R}^{n+1}$ の $\pm e_i$ の $2n+2$ 点は $\sqrt2\leq r< 2$ で $S^n$ を与える。
周の長さ $1$ の円周 $S^1$ に弧の長さの距離を入れる。$0< r< \frac12$ と $l=0,1,2,\dots$ について、
$$
\frac{l}{2l+1}< r< \frac{l+1}{2l+3}\ \Longrightarrow\ \operatorname{VR}_r(S^1)\simeq S^{2l+1}
$$
であり、$r=\frac{l}{2l+1}$($l\geq1$)では $\operatorname{VR}_r(S^1)$ は連続体濃度個の $S^{2l}$ の一点和とホモトピー同値である(Adamaszek と Adams による。AA17 p. 2 の主結果の要約)。$r\geq\frac12$ ならすべての有限部分集合が単体になり、可縮である。尺度が小さいうちは円周を復元し、大きくなると $S^3,S^5,\dots$ という元の空間と無関係な型を経て可縮になる。境界の値で型が変わることは、rem-vr-convention の規約の違いが効く典型である。
尺度が小さいとき元の多様体が復元されることは一般に成り立つ。閉 Riemann 多様体 $M$ と、単射半径に比べて十分小さい $r$ について、$\operatorname{VR}_{< r}(M)$ は $M$ とホモトピー同値である(Hausmann の定理。主張は AA17 p. 1 による)。
距離空間を少し動かしたとき Vietoris–Rips 複体の列がどれだけ変わるかを、Gromov-Hausdorff距離で測る。道具は単体写像のホモトピーについての次の補題である。
$K,L$ を単体複体、$\varphi,\psi\colon K\to L$ を単体写像とする。$K$ のどの単体 $\sigma$ についても $\varphi(\sigma)\cup\psi(\sigma)$ が $L$ の単体であるとき($\varphi$ と $\psi$ は隣接するという)、実現 $\lvert\varphi\rvert,\lvert\psi\rvert\colon\lvert K\rvert\to\lvert L\rvert$ はホモトピックである。
$p\in\lvert\sigma\rvert$ について、$\lvert\varphi\rvert(p)$ と $\lvert\psi\rvert(p)$ はどちらも単体 $\lvert\varphi(\sigma)\cup\psi(\sigma)\rvert$ の点なので、線分 $H(p,s)=(1-s)\lvert\varphi\rvert(p)+s\lvert\psi\rvert(p)$($0\leq s\leq1$)はこの単体の中にある。$p$ が二つの単体の共通の面にあるときは、その面について同じ式になるので $H$ は矛盾なく定まる。$H$ は各閉単体と $[0,1]$ の積の上で連続であり、$\lvert K\rvert\times[0,1]$ はこれらの積の弱位相をもつので、$H$ は連続である。$\square$
以下、体 $k$ を係数とするホモロジーを $H_*$ と書き、$r\leq r'$ について包含 $\operatorname{VR}_r(X)\subset\operatorname{VR}_{r'}(X)$ が誘導する写像を $\iota_{r,r'}$ と書く。
$X,Y$ を距離空間、$R\subset X\times Y$ を歪み $\operatorname{dis}R\leq\eta$ の対応とする。写像 $f\colon X\to Y$、$g\colon Y\to X$ を、すべての $x,y$ について $(x,f(x))\in R$、$(g(y),y)\in R$ となるように選ぶ。このとき、すべての $r\geq0$ について次が成り立つ。
(1) $f$ は単体写像 $f_r\colon\operatorname{VR}_r(X)\to\operatorname{VR}_{r+\eta}(Y)$ を、$g$ は単体写像 $g_r\colon\operatorname{VR}_r(Y)\to\operatorname{VR}_{r+\eta}(X)$ を定める。
(2) $g_{r+\eta}\circ f_r$ は包含 $\operatorname{VR}_r(X)\subset\operatorname{VR}_{r+2\eta}(X)$ とホモトピックであり、$f_{r+\eta}\circ g_r$ も同様である。
とくに、ホモロジーの写像 $(f_r)_*$、$(g_r)_*$ は包含が誘導する写像と可換で、
$$
(g_{r+\eta})_*\circ(f_r)_*=\iota_{r,r+2\eta},\qquad(f_{r+\eta})_*\circ(g_r)_*=\iota_{r,r+2\eta}
$$
を満たす。
各次数 $k$ について、ベクトル空間 $H_k(\operatorname{VR}_r(X))$ と包含の誘導する写像 $\iota_{r,r'}$ の族を、$X$ の Vietoris–Rips フィルトレーションの持続ホモロジー(持続加群)という。定理の結論は、二つの持続加群が尺度を $\eta$ ずらす写像で互いに行き来でき、往復すると尺度を $2\eta$ ずらす包含になる、という形をしている。これを $\eta$ インターリーブという。Gromov–Hausdorff 距離 $d_{GH}$ は対応の歪みの下限の半分なので(Gromov-Hausdorff距離の「対応による特徴付け」)、$\eta>2d_{GH}(X,Y)$ ならこの定理が使える。これは CdSO14 Lemma 4.3(p. 7)の内容を、対応から選んだ写像で書き直したものである。
全有界な距離空間 $X,Y$ については、持続加群から持続図(各ホモロジー類の生まれる尺度と消える尺度の組の多重集合)が定まり、インターリーブについての一般論と合わせて、持続図のボトルネック距離は $2d_{GH}(X,Y)$ 以下になる(CdSO14 Theorem 5.2、p. 13。証明は同 Theorem 2.3、p. 4 と Lemma 4.3・4.4 による)。有限の標本点 $S\subset X$ について $d_{GH}(X,S)$ は $S$ の網の目の細かさで抑えられるので、標本から計算した持続図は元の空間の持続図に近い。データ解析で Vietoris–Rips 複体を使う根拠はここにある。
有限生成群 $G$ と有限生成系 $S$ について、$G$ に語距離 $d$(Cayleyグラフ $\Gamma$ の辺の長さを $1$ とした道の距離を頂点に制限したもの)を入れる。値は整数で、$\Gamma$ の頂点 $u,v$ を結ぶ測地線は、$u$ から距離 $0,1,\dots,d(u,v)$ の頂点を順に通る。$\Gamma$ の測地三角形の各辺が他の $2$ 辺の和集合の $\delta$ 近傍に含まれるとき、$G$ は $\delta$ 双曲であるという(双曲群)。
$G$ を $\delta$ 双曲群とし、整数 $d\geq2$ が $\lfloor d/2\rfloor\geq2\delta$ を満たすとする。このとき $\operatorname{VR}_d(G)$ は可縮である。
段階 0(有限部分への帰着)。 $\lvert\operatorname{VR}_d(G)\rvert$ は CW 複体なので、Whiteheadの定理により、すべてのホモトピー群が消えることを示せばよい。球面からの写像の像はコンパクトなので有限個の単体に含まれ、それらの頂点を含む有限集合 $F\subset G$ について、$F$ の上の部分複体 $\operatorname{VR}_d(F)$ に含まれる。よって、どの有限集合 $F$ についても、包含 $\operatorname{VR}_d(F)\hookrightarrow\operatorname{VR}_d(G)$ が定値写像とホモトピックであることを示せば十分である。
$x_0\in F$ を固定し、$\Phi(F):=\sum_{v\in F}d(x_0,v)$ についての帰納法で示す。
段階 1(錐になる場合)。 $F$ のすべての点が $x_0$ から距離 $d$ 以下なら、$\operatorname{VR}_d(F)$ の各単体 $\sigma$ について $\sigma\cup\{x_0\}$ の直径は $d$ 以下である。よって包含と、すべてを $x_0$ に写す定値写像は隣接し、lem-vr-contiguous によりホモトピックである。
段階 2(遠い点を引き寄せる不等式)。 そうでないとき、$x\in F$ を $D:=d(x_0,x)$ が最大になる点とすると $D>d$ である。$m:=\lfloor d/2\rfloor\geq1$ とし、測地線 $[x_0,x]$ の上の頂点 $x'$ を $d(x',x)=m$ となるように取る。$y\in G$ が $d(x,y)\leq d$ と $d(x_0,y)\leq D$ を満たすなら、$d(x',y)\leq d$ であることを示す。
測地線 $[x,y]$、$[x_0,y]$ を選んで測地三角形を作ると、$x'$ から距離 $\delta$ 以下の点 $z$ が $[x,y]\cup[x_0,y]$ の上にある。$z\in[x,y]$ なら、$d(x,z)\geq d(x,x')-\delta=m-\delta$ より
$$
d(x',y)\leq\delta+d(z,y)=\delta+d(x,y)-d(x,z)\leq d-m+2\delta.
$$
$z\in[x_0,y]$ なら、$d(x_0,z)\geq d(x_0,x')-\delta=D-m-\delta$ より
$$
d(x',y)\leq\delta+d(x_0,y)-d(x_0,z)\leq\delta+D-(D-m-\delta)=m+2\delta.
$$
$d-m=\lceil d/2\rceil\geq m\geq2\delta$ なので、どちらの場合も右辺は $d$ 以下である。
段階 3(隣接する写像で置き換える)。 $F':=(F\setminus\{x\})\cup\{x'\}$ とし、$\varphi\colon F\to F'$ を $\varphi(x)=x'$、他の点では恒等写像とする。$\sigma\in\operatorname{VR}_d(F)$ が $x$ を含むとき、$\sigma$ の各点 $y$ は $d(x,y)\leq d$ を満たし、$x$ の最大性から $d(x_0,y)\leq D$ なので、段階 2 から $d(x',y)\leq d$ である。$d(x,x')=m\leq d$ でもあるので、$\sigma\cup\{x'\}$ の直径は $d$ 以下である。$x$ を含まない単体では $\varphi$ は恒等である。よって $\varphi$ は単体写像 $\operatorname{VR}_d(F)\to\operatorname{VR}_d(F')$ を定め、$\operatorname{VR}_d(G)$ への写像として包含と隣接する。lem-vr-contiguous により、$\operatorname{VR}_d(F)$ の包含は、$\operatorname{VR}_d(F')$ の包含と $\varphi$ の合成とホモトピックである。
$x\neq x_0$ なので $x_0\in F'$ であり、$d(x_0,x')=D-m< D$ なので $\Phi(F')<\Phi(F)$ である($x'$ がもとから $F$ にあればさらに小さい)。$\Phi$ は非負整数なので、帰納法の仮定から $\operatorname{VR}_d(F')$ の包含は定値写像とホモトピックであり、$\operatorname{VR}_d(F)$ の包含も同様である。$\square$
$G$ は左からの積で $\operatorname{VR}_d(G)$ に単体的に作用し、どの単体も平行移動で単位元を含む単体に移る。単位元を含む単体は半径 $d$ の球(有限集合)の部分集合なので、単体の軌道は有限個である。DK17 Theorem 11.211(p. 443)は、十分大きな $d$ について $\operatorname{VR}_d(G)$ が可縮であることを述べ、そこから双曲群が有限性の条件 $F_\infty$ をもつことを導いている。上の証明は、$d$ の下限を $\lfloor d/2\rfloor\geq2\delta$ という具体的な形で与えるために、細い三角形の条件から直接書いたものである。
階数 $2$ の自由群 $F_2$ と自由基底についての Cayley グラフは木で、測地三角形は三脚の形になり $\delta=0$ で双曲である。定理から $d\geq2$ で $\operatorname{VR}_d(F_2)$ は可縮である。$d=1$ でも、$\operatorname{VR}_1(F_2)$ は Cayley グラフそのもの(木には三角形がないので $2$ 単体はない)で可縮である。
平面の一辺 $1$ の正三角形の頂点 $a,b,c$ を $X$ とする。$\operatorname{VR}_1(X)$ は $2$ 単体 $\{a,b,c\}$ 全体で可縮である。一方、平面の中で各頂点を中心とする半径 $\frac12$ の閉円板を考えると、どの $2$ 枚も辺の中点で交わるが、$3$ 枚に共通な点はない。共通点 $p$ があれば $3$ 頂点からの距離がすべて $\frac12$ 以下になるが、$3$ 頂点からの距離の最大値を最小にする点は外心で、その値は外接円の半径 $1/\sqrt3>\frac12$ だからである。よってこの円板の被覆の脈体は三角形の周で、$S^1$ とホモトピー同値である。$2$ 点の距離が $1$ 以下であることは半径 $\frac12$ の円板が交わることと同じだが、$3$ 枚以上の共通部分は対ごとの交わりでは決まらない。半径 $r/2$ の球の被覆の脈体は旗複体でなく、$\operatorname{VR}_r(X)$ とホモトピー型も異なりうる。
平面の $2$ 本の平行な線分 $X=\{(t,0)\}\cup\{(t,1)\}$($0\leq t\leq1$)にユークリッド距離を入れる(CdSO14 p. 15)。$X$ はコンパクトだが、$H_1(\operatorname{VR}_1(X);k)$ は非可算次元である。
実際、$e_t:=\{(t,0),(t,1)\}$ は辺である。$e_t$ を含む $2$ 単体があれば、第 $3$ の点は $2$ 端点から距離 $1$ 以下だが、$(s,0)$ と $(t,1)$ の距離は $\sqrt{(s-t)^2+1}$ なので $s=t$ に限られ、$(s,1)$ も同様である。よって $e_t$ はどの $2$ 単体の辺でもない。$0< t\leq1$ について、$(0,0)\to(t,0)\to(t,1)\to(0,1)\to(0,0)$ をたどる $1$ 輪体 $\gamma_t$ を考える(各辺の長さは $1$ 以下)。有限個の $\gamma_t$ の一次結合 $\sum c_t\gamma_t$ が境界なら、$e_t$ の係数 $c_t$ は $0$ でなければならない。境界はどの $2$ 単体の辺でもない辺の係数が $0$ であり、$e_t$($t>0$)を含む輪体は $\gamma_t$ だけだからである。よって $\{\gamma_t\}$ は $H_1$ で一次独立である。「コンパクトな距離空間の Vietoris–Rips 複体のホモロジーは有限生成」という主張は偽である。
| 主張 | 成否 | 根拠 |
|---|---|---|
| $\operatorname{VR}_r(X)$ は $1$ 骨格で決まる | 真 | prop-vr-flag |
| $\operatorname{VR}_r(X)$ は球の被覆の脈体と同じ型 | 偽 | 正三角形(ex-vr-not-cech) |
| コンパクトなら $H_*(\operatorname{VR}_r(X))$ は有限次元 | 偽 | 平行な線分(ex-vr-uncountable) |
| 尺度を大きくしても元の空間の型が保たれる | 偽 | 円周で $S^3,S^5,\dots$ が現れる(ex-vr-circle) |
| 双曲群ならどの $d\geq1$ でも $\operatorname{VR}_d(G)$ は可縮 | 偽 | $\operatorname{VR}_1(\mathbb{Z}/n)\cong S^1$($n\geq4$。ex-vr-cycle) |
最後の行の $\mathbb{Z}/n$ は有限群なので(直径以上の $\delta$ で)双曲群である。thm-vr-hyperbolic は $d\geq2$ と $\lfloor d/2\rfloor\geq2\delta$ を仮定しており、尺度は $\delta$ に応じて大きく取らなければならない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する