📂位相データ分析

チェック複体の定義

定義 ^{1 2}

距離空間 $\left( X, d \right)$ と正の数 $\varepsilon > 0$ が与えられたとする。有限集合 $S \subset X$ に対して以下のように定義された抽象単体複体 $\check{C}_{\varepsilon} (S)$ を チェック複体^{Čech Complex}という。 $$\check{C}_{\varepsilon} (S) := \left\{ \sigma \subset S : \bigcap_{x \in \sigma} B_{d} \left( x ; \varepsilon \right) \ne \emptyset \right\}$$

ここでは、$B_{d} (c; r)$ は与えられた距離空間で中心が $c \in X$、半径が $r \in \mathbb{R}$ の開球である。 $$B_{d} \left( c ; r \right) := \left\{ x \in X : d (c,x) < r \right\}$$

説明

定義が少し難しく書かれているが、実際にはユークリッド空間 $\left( \mathbb{R}^{d} , \left\| \cdot \right\|_{2} \right)$で考えると、単に球が重なっているときだけ単体と認める単体複体と考えると簡単だ。式に囚われずに、Vietoris-Rips複体と何が違うかを見ればすぐに理解できる。

Vietoris-Rips複体とチェック複体の違い

Vietoris-Rips複体: $$\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\}$$

次の図は、同じデータに対してVietoris-Rips複体とチェック複体を比較したものだ。上が $\text{VR}_{\varepsilon}$、下が $\check{C}_{\varepsilon}$ だ。

• Vietoris-Ripsは、$k$-単体を含む条件としてその面である$k-1$-単体が存在することのみを要求する。例では、$1$-単体である$AB$、$BC$、$CA$が存在するので、$2$-単体である$ABC$が含まれる。
• それに対してチェック複体は、その面を含むことに加え、$ABC$自体もその球たちが一点で結ばれていなければならない。これはチェック複体を構築する条件がVietoris-Rips複体を構築するよりも厳しいことを意味し、以下が分かる。 $$\check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon}$$ さらに、次の事実が知られている。 $$\check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon} \subset \check{C}_{2 \varepsilon}$$

定義から推測できるのは、おそらくチェック複体がVietoris-Rips複体に比べて少し多くの情報を持てるかもしれないということだ。$\text{VR}_{\varepsilon}$は、与えられた$k \le n$個の点が接続されているだけで、その$k-1$-単体が存在すると断言する。つまり、単体の存在性とその全ての面の存在性の間に差がないと言える。例えば、$2$-単体である$ABC$が存在するとか、$1$-単体である$AB$、$BC$、$CA$が存在すると言うのは、正確に同等で、正直なところ、一つを知っていれば、残りの情報は無意味だ。一方で、$\check{C}_{\varepsilon}$は、$AB$、$BC$、$CA$が存在すると言っても$ABC$の存在を断言できず、別途確認が必要だ。この点から、チェック複体はデータをVietoris-Rips複体よりも少し詳細に見ていると期待できる。

一方で、実際の計算の面では、Vietoris-Rips複体を構築する計算コストが圧倒的に安い。というのも、$\text{VR}_{\varepsilon}$のように単純に固定された点と点の距離を計算するのは簡単だが、$\check{C}_{\varepsilon}$では点の球たちがどこで会うかも分からず、会ったとしてもそれが$\varepsilon$より長いか短いか分からないからだ。これを克服し、チェック複体を構築するためには、Welzlのアルゴリズムなどで最小包含円を見つける方法などが考えられるが、その一回一回の計算がかなり高価で、その高価な計算を可能な全ての点の組み合わせに対して繰り返さなければならない。