logo

ベトリス-リプス コンプレックスの定義 📂位相データ分析

ベトリス-リプス コンプレックスの定義

定義 1 2

簡単な定義

ユークリッド空間 (Rd,2)\left( \mathbb{R}^{d} , \left\| \cdot \right\|_{2} \right) と正数 ε>0\varepsilon > 0 が与えられたとしよう。有限集合 SRdS \subset \mathbb{R}^{d} に対し、以下の2つの条件を満たす単体複体 VRε(S)\text{VR}_{\varepsilon} (S)ビエトリス-リプス複体vietoris-Rips Complexという。

  • (i): SS を頂点の集合とする。
  • (ii): kk-シンプレックス [v0,v1,,vk]\left[ v_{0} , v_{1} , \cdots, v_{k} \right]VRε(S)\text{VR}_{\varepsilon} (S) に属することは、すべての 0i,jk0 \le i,j \le k に対し、以下が成立することと同値である。 vivj22ε \left\| v_{i} - v_{j} \right\|_{2} \le 2 \varepsilon

難しい定義

距離空間 (X,d)\left( X, d \right) と正数 ε>0\varepsilon > 0 が与えられたとしよう。有限集合 SXS \subset X に対し、以下のように定義された抽象単体複体 VRε(S)\text{VR}_{\varepsilon} (S)ビエトリス-リプス複体vietoris-Rips Complexという。 VRε(S):={σS:diamσ2ε} \text{VR}_{\varepsilon} (S) := \left\{ \sigma \subset S : \diam \sigma \le 2 \varepsilon \right\} ここで、diam\diam直径diameterとして、与えられた集合 σX\sigma \subset X の全ての点間の距離のスープリームにより定義される。 diamσ:=supx1,x2σd(x1,x2) \diam \sigma := \sup_{x_{1} , x_{2} \in \sigma} d \left( x_{1} , x_{2} \right)

説明

ビエトリス-リプス複体vietoris-Rips Complexは、しばしば単にVR複体またはリプス複体とも呼ばれる。

少し異なる表現だが、簡単な定義であれ難しい定義であれ、核心はシンプレックスがなるための条件が、そこに含まれるすべての点の距離が 2ε2 \varepsilon 以下であることである。これを図で描くと、次のように 00-シンプレックスの頂点を中心に、半径 ε\varepsilon の球体を考えた時、2つの球が触れ合うことを基準に 11-シンプレックスを作り、3つの頂点が 11-シンプレックスで繋がれば 22-シンプレックスを作るという風にVR複体を構築できる。

20220306_203242.png

ビエトリス-リプス複体とチェック複体の違い

ビエトリス-リプス複体: VRε(S):={σS:diamσ2ε}\text{VR}_{\varepsilon} (S) := \left\{ \sigma \subset S : \diam \sigma \le 2 \varepsilon \right\}

チェック複体: Cˇε(S):={σS:xσBd(x;ε)}\check{C}_{\varepsilon} (S) := \left\{ \sigma \subset S : \bigcap_{x \in \sigma} B_{d} \left( x ; \varepsilon \right) \ne \emptyset \right\}

次の図は、同じデータに対するビエトリス-リプス複体とチェック複体を比較したものである。上は VRε\text{VR}_{\varepsilon} 、下は Cˇε\check{C}_{\varepsilon} である。

20220314_124807.png

  • ビエトリス-リプスは kk-シンプレックスを含む条件として、そのFaceたる k1k-1-シンプレックスの存在だけを要求する。例えば、11-シンプレックスである ABABBCBCCACA が存在するため、22-シンプレックスである ABCABC が含まれる。
  • それに対し、チェック複体は、これらのフェースを含むだけでなく、ABCABC 自体もその球が1点で結びつかなければならない。これは、チェック複体を構築する条件がビエトリス-リプス複体を構築するよりも厳格であることを意味し、次の観察につながる。 CˇεVRε \check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon} さらに、次の事実が知られている。 CˇεVRεCˇ2ε \check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon} \subset \check{C}_{2 \varepsilon}

定義から推測できることは、チェック複体がビエトリス-リプス複体に比べて少し多くの情報を持つ可能性があるという点である。VRε\text{VR}_{\varepsilon} は与えられた点が連結しているだけで、k1k-1-シンプレックスの存在が当然であると言っている。つまり、シンプレックスの存在とそのすべてのフェースの存在性の間には差がない。例えば, 22-シンプレックスである ABCABC が存在するということや、11-シンプレックスである ABABBCBCCACA が存在するということは、正確に等価であり、大胆に言えば、一方を知っていれば、残りのものは無意味な情報である。一方、Cˇε\check{C}_{\varepsilon} は、ABABBCBCCACA が存在することだけでは、ABCABC の存在を断言できず、別途の確認が必要である。この点で、チェック複体はビエトリス-リプス複体に比べて、データをもう少し細かく見ていると期待できる。

一方、実際の計算の観点からは、ビエトリス-リプス複体を構築する計算コストは圧倒的に安価である。確かに、VRε\text{VR}_{\varepsilon} が単に固定された点間の距離を計算するのに対し、Cˇε\check{C}_{\varepsilon} はその球がどこで交わるかもわからず、交わったとしてもそれが ε\varepsilon より長いか短いかもわからない。この問題を克服し、チェック複体を構築する方法の一つとして、Welzlアルゴリズムなどを使用して最小包含円を見つける方法が考慮されるが、その一回一回の計算はかなり高価であり、その高価な計算を可能なすべての点の組み合わせに対して繰り返さなければならない。


  1. Raul Rabadan. (2020). Topological Data Analysis for Genomics and Evolution: p126. ↩︎

  2. Edelsbrunner, Harer. (2010). Computational Topology An Introduction: p74. ↩︎