ベトリス-リプス コンプレックスの定義
定義 1 2
簡単な定義
ユークリッド空間 $\left( \mathbb{R}^{d} , \left\| \cdot \right\|_{2} \right)$ と正数 $\varepsilon > 0$ が与えられたとしよう。有限集合 $S \subset \mathbb{R}^{d}$ に対し、以下の2つの条件を満たす単体複体 $\text{VR}_{\varepsilon} (S)$ をビエトリス-リプス複体vietoris-Rips Complexという。
- (i): $S$ を頂点の集合とする。
- (ii): $k$-シンプレックス $\left[ v_{0} , v_{1} , \cdots, v_{k} \right]$ が $\text{VR}_{\varepsilon} (S)$ に属することは、すべての $0 \le i,j \le k$ に対し、以下が成立することと同値である。 $$ \left\| v_{i} - v_{j} \right\|_{2} \le 2 \varepsilon $$
難しい定義
距離空間 $\left( X, d \right)$ と正数 $\varepsilon > 0$ が与えられたとしよう。有限集合 $S \subset X$ に対し、以下のように定義された抽象単体複体 $\text{VR}_{\varepsilon} (S)$ をビエトリス-リプス複体vietoris-Rips Complexという。 $$ \text{VR}_{\varepsilon} (S) := \left\{ \sigma \subset S : \diam \sigma \le 2 \varepsilon \right\} $$ ここで、$\diam$ は直径diameterとして、与えられた集合 $\sigma \subset X$ の全ての点間の距離のスープリームにより定義される。 $$ \diam \sigma := \sup_{x_{1} , x_{2} \in \sigma} d \left( x_{1} , x_{2} \right) $$
説明
ビエトリス-リプス複体vietoris-Rips Complexは、しばしば単にVR複体またはリプス複体とも呼ばれる。
少し異なる表現だが、簡単な定義であれ難しい定義であれ、核心はシンプレックスがなるための条件が、そこに含まれるすべての点の距離が $2 \varepsilon$ 以下であることである。これを図で描くと、次のように $0$-シンプレックスの頂点を中心に、半径 $\varepsilon$ の球体を考えた時、2つの球が触れ合うことを基準に $1$-シンプレックスを作り、3つの頂点が $1$-シンプレックスで繋がれば $2$-シンプレックスを作るという風にVR複体を構築できる。
ビエトリス-リプス複体とチェック複体の違い
ビエトリス-リプス複体: $$\text{VR}_{\varepsilon} (S) := \left\{ \sigma \subset S : \diam \sigma \le 2 \varepsilon \right\}$$
チェック複体: $$\check{C}_{\varepsilon} (S) := \left\{ \sigma \subset S : \bigcap_{x \in \sigma} B_{d} \left( x ; \varepsilon \right) \ne \emptyset \right\}$$
次の図は、同じデータに対するビエトリス-リプス複体とチェック複体を比較したものである。上は $\text{VR}_{\varepsilon}$ 、下は $\check{C}_{\varepsilon}$ である。
- ビエトリス-リプスは $k$-シンプレックスを含む条件として、そのFaceたる $k-1$-シンプレックスの存在だけを要求する。例えば、$1$-シンプレックスである $AB$、$BC$、$CA$ が存在するため、$2$-シンプレックスである $ABC$ が含まれる。
- それに対し、チェック複体は、これらのフェースを含むだけでなく、$ABC$ 自体もその球が1点で結びつかなければならない。これは、チェック複体を構築する条件がビエトリス-リプス複体を構築するよりも厳格であることを意味し、次の観察につながる。 $$ \check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon} $$ さらに、次の事実が知られている。 $$ \check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon} \subset \check{C}_{2 \varepsilon} $$
定義から推測できることは、チェック複体がビエトリス-リプス複体に比べて少し多くの情報を持つ可能性があるという点である。$\text{VR}_{\varepsilon}$ は与えられた点が連結しているだけで、$k-1$-シンプレックスの存在が当然であると言っている。つまり、シンプレックスの存在とそのすべてのフェースの存在性の間には差がない。例えば, $2$-シンプレックスである $ABC$ が存在するということや、$1$-シンプレックスである $AB$、$BC$、$CA$ が存在するということは、正確に等価であり、大胆に言えば、一方を知っていれば、残りのものは無意味な情報である。一方、$\check{C}_{\varepsilon}$ は、$AB$、$BC$、$CA$ が存在することだけでは、$ABC$ の存在を断言できず、別途の確認が必要である。この点で、チェック複体はビエトリス-リプス複体に比べて、データをもう少し細かく見ていると期待できる。
一方、実際の計算の観点からは、ビエトリス-リプス複体を構築する計算コストは圧倒的に安価である。確かに、$\text{VR}_{\varepsilon}$ が単に固定された点間の距離を計算するのに対し、$\check{C}_{\varepsilon}$ はその球がどこで交わるかもわからず、交わったとしてもそれが $\varepsilon$ より長いか短いかもわからない。この問題を克服し、チェック複体を構築する方法の一つとして、Welzlアルゴリズムなどを使用して最小包含円を見つける方法が考慮されるが、その一回一回の計算はかなり高価であり、その高価な計算を可能なすべての点の組み合わせに対して繰り返さなければならない。