持続的相同性

Method for computing topological features of a space at different spatial resolutions

位相データ解析において、パーシステントホモロジーとは、異なる空間解像度における空間の位相的特徴を計算する手法である。より持続的な特徴は、幅広い空間スケールにわたって検出され、サンプリング、ノイズ、あるいは特定のパラメータ選択によるアーティファクトではなく、基礎となる空間の真の特徴を反映している可能性が高いと判断される。^[1]

空間の永続ホモロジーを求めるには、まずその空間を単体複体として表現する必要がある。基礎空間上の距離関数は、単体複体のフィルトレーション、すなわち増加する部分集合の入れ子列に対応する。これを行う一般的な方法の一つは、点群への距離のサブレベルフィルトレーション、あるいはそれと同等の、点群のオフセットフィルトレーションとそのナーブ（nerve）を用いて、チェフフィルトレーションとして知られる単体フィルトレーションを得ることである。^{[2]同様の構成として、}ヴィエトリス・リップス複体の入れ子列を用いる方法があり、これはヴィエトリス・リップスフィルトレーションと呼ばれる。^[3]

意味

形式的には、面の増加列に対して非減少な単体複体上の実数値関数を考えます。つまり、がの面であるときはいつでも、となります。すると、任意の に対して、サブレベル集合はKの部分複体となり、の単体上の の値の順序付け（実際には常に有限）は、サブレベル複体上の順序付けを誘導し、これはフィルタリングを定義します。 ${\displaystyle f:K\rightarrow \mathbb {R} }$ ${\displaystyle f(\sigma )\leq f(\tau )}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle K}$ ${\displaystyle a\in \mathbb {R} }$ ${\displaystyle K_{a}=f^{-1}((-\infty ,a])}$ ${\displaystyle f}$ ${\displaystyle K}$

${\displaystyle \emptyset =K_{0}\subseteq K_{1}\subseteq \cdots \subseteq K_{n}=K}$

のとき、包含は各次元 の単体ホモロジー群に準同型写像を誘導する。パーシステントホモロジー群はこれらの準同型の像であり、パーシステントベッティ数はこれらの群の階数である。^[4]のパーシステントベッティ数は、パーシステントホモロジーの前身であるサイズ関数と一致する。^[5] ${\displaystyle 0\leq i\leq j\leq n}$ ${\displaystyle K_{i}\hookrightarrow K_{j}}$ ${\displaystyle f_{p}^{i,j}:H_{p}(K_{i})\rightarrow H_{p}(K_{j})}$ ${\displaystyle p}$ ${\displaystyle p^{\text{th}}}$ ${\displaystyle p^{\text{th}}}$ ${\displaystyle \beta _{p}^{i,j}}$ ${\displaystyle p=0}$

体上の任意のフィルタリングされた複体は、フィルタリングを保存する線形変換によって、いわゆる標準形式に変換することができます。標準形式とは、2種類のフィルタリングされた複体の標準的に定義された直和です。1次元複体で微分が自明な複体 と2次元複体でホモロジーが自明な複体です。^[6] ${\displaystyle F}$ ${\displaystyle d(e_{t_{i}})=0}$ ${\displaystyle d(e_{s_{j}+r_{j}})=e_{r_{j}}}$

半順序集合上の持続加群はでインデックス付けされたベクトル空間の集合であり、のときは常に線型写像を持ち、 は恒等写像に等しく、 のときはである。同様に、これをからベクトル空間（または-加群）のカテゴリへの関手とみなすこともできる。でインデックス付けされた体上の持続加群の分類がある。 による乗算は、持続加群で 1 ステップ前進することに対応する。直感的には、右側の自由部分は濾過レベルで現れて消えることのないホモロジー生成子に対応し、一方、捩れ部分は濾過レベルで現れて濾過のステップ間続く（または同等に、濾過レベル で消える）ホモロジー生成子に対応する。^{[7] [6]} ${\displaystyle P}$ ${\displaystyle U_{t}}$ ${\displaystyle P}$ ${\displaystyle u_{t}^{s}:U_{s}\to U_{t}}$ ${\displaystyle s\leq t}$ ${\displaystyle u_{t}^{t}}$ ${\displaystyle u_{t}^{s}\circ u_{s}^{r}=u_{t}^{r}}$ ${\displaystyle r\leq s\leq t}$ ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle F}$ ${\displaystyle \mathbb {N} }$ $${\displaystyle U\simeq \bigoplus _{i}x^{t_{i}}\cdot F[x]\oplus \left(\bigoplus _{j}x^{r_{j}}\cdot (F[x]/(x^{s_{j}}\cdot F[x]))\right).}$$ ${\displaystyle x}$ ${\displaystyle t_{i}}$ ${\displaystyle r_{j}}$ ${\displaystyle s_{j}}$ ${\displaystyle s_{j}+r_{j}}$

これら 2 つの定理により、フィルタリングされた単体複合体の持続ホモロジーを持続バーコードまたは持続ダイアグラムで一意に表すことができます。バーコードは、持続する各ジェネレータを、それが現れた最初のフィルタリング レベルから始まり、それが消えるフィルタリング レベルで終わる水平線で表します。一方、持続ダイアグラムは、各ジェネレータの x 座標が誕生時刻、y 座標が死亡時刻である点をプロットします。同様に、同じデータはバラニコフの標準形で表され、^[6]各ジェネレータは、それぞれについて別々の線上にプロットされた誕生値と死亡値を結ぶ線分で表されます 。 ${\displaystyle p}$

安定性

パーシステントホモロジーは厳密な意味で安定であり、ノイズに対する堅牢性を提供する。ボトルネック距離は、パーシステントダイアグラムの空間上の自然な計量であり、 は一対一の関係にある。入力フィルトレーションに小さな摂動を与えると、ボトルネック距離におけるパーシステントダイアグラムも小さな摂動を受ける。具体的には、連続した tame 関数のサブレベル集合で決まる単体複体に同相な空間上のフィルトレーションを考える。そのth ホモロジーのパーシステントダイアグラムへの写像は、関数の -計量とパーシステントダイアグラム上のボトルネック距離に関して1- Lipschitzである。つまり、 である。^[8] $${\displaystyle W_{\infty }(X,Y):=\inf _{\varphi :X\to Y}\sup _{x\in X}\Vert x-\varphi (x)\Vert _{\infty },}$$ ${\displaystyle \varphi }$ ${\displaystyle X}$ ${\displaystyle f:X\to \mathbb {R} }$ ${\displaystyle D}$ ${\displaystyle f}$ ${\displaystyle k}$ ${\displaystyle \sup }$ ${\displaystyle W_{\infty }(D(f),D(g))\leq \lVert f-g\rVert _{\infty }}$

計算

主なアルゴリズムは、フィルタリングされた複素数を上三角行列によって標準形に導くことに基づいており、単体の数で最悪の場合3乗の計算量で実行されます。^[6]持続ホモロジーを計算するための既知の最速のアルゴリズムは、行列の乗算時間で実行されます。^[9]

単体の数は計算時間に大きく関係するため、単体の数が少ないフィルター付き単体複体を見つけることは活発な研究分野です。フィルター付き単体複体における単体の数を減らし、永続ホモロジーを近似するいくつかのアプローチが提案されています。^{[10] [11] [12] [13]}

ソフトウェア

有限濾過の持続間隔を計算するための様々なソフトウェアパッケージが存在する。^[14]

ソフトウェアパッケージ	クリエイター	最新リリース	発売日	ソフトウェアライセンス[15]	オープンソース	プログラミング言語	特徴
オープンPH	ロドリゴ・メンドーサ＝スミス、ジャレッド・タナー	0.0.1	2019年4月25日	アパッチ2.0	はい	Matlab、CUDA	GPUアクセラレーション
ジャバプレックス	アンドリュー・タウシュ、ミカエル・ヴェジデモ＝ヨハンソン、ヘンリー・アダムス	4.2.5	2016年3月14日	カスタム	はい	Java、Matlab
ディオニュソス	ドミトリー・モロゾフ	2.0.10	2023年6月27日	修正BSD	はい	C++、Pythonバインディング
ペルセウス	ヴィディット・ナンダ	4.0ベータ版		GPL	はい	C++
ファット[16]	ウルリッヒ・バウアー、ミヒャエル・ケルバー、ヤン・ライニングハウス	1.4.1			はい	C++
ディファ	ヤン・ライニングハウス				はい	C++
グディ[17]	インリア	3.10.1	2024年7月1日	MIT / GPLv3	はい	C++、Pythonバインディング
CTL	ライアン・ルイス	0.2		BSD	はい	C++
フォム	アンドリュー・タウズ				はい	R
TDA	ブリタニー・T・ファシー、ジス・キム、ファブリツィオ・レッキ、クレマン・マリア、ヴァンサン・ルヴロー	1.5	2016年6月16日		はい	R	GUDHI、Dionysus、PHAT用のRインターフェースを提供します
エイレーネ	グレゴリー・ヘンゼルマン	1.0.1	2019年3月9日	GPLv3	はい	ジュリア
リプサー	ウルリッヒ・バウアー	1.0.1	2016年9月15日	マサチューセッツ工科大学	はい	C++
キュービクル	ヒューバート・ワーグナー	v0.8ベータ版	2018年5月	GPL	はい	C++	大規模な 3D および 2D グレースケール画像 (スカラー ボクセル データ) を処理
トポロジーツールキット	ジュリアン・ティエニー、ギョーム・ファヴリエ、ジョシュア・レヴィーン、シャルル・グーネ、マイケル・ミショー	0.9.8	2019年7月29日	BSD	はい	C++、VTK、Pythonバインディング
リブスティック	ステファン・フーバー	0.2	2014年11月27日	マサチューセッツ工科大学	はい	C++
リプサー++	サイモン・チャン、メンバイ・シャオ、ハオ・ワン	1.0	2020年3月	マサチューセッツ工科大学	はい	CUDA、C++、Pythonバインディング	GPUアクセラレーション

参照

• 計算トポロジー

参考文献

1. Carlsson, Gunnar (2009). 「トポロジーとデータ」.アメリカ数学会報. 46 (2): 255– 308. doi : 10.1090/S0273-0979-09-01249-X .
2. Kerber, Michael; Sharathkumar, R. (2013). 「低次元および高次元における近似チェフ複体」. Cai, Leizhen, Cheng, Siu-Wing, Lam, Tak-Wah (編).アルゴリズムと計算. コンピュータサイエンス講義ノート. 第8283巻. ベルリン、ハイデルベルク: Springer. pp.  666– 676. doi :10.1007/978-3-642-45030-3_62. ISBN 978-3-642-45030-3. S2CID  5770506。
3. Dey, Tamal K.; Shi, Dayu; Wang, Yusu (2019-01-30). 「SimBa: 単純バッチコラプスによるRips-filteration Persistenceの近似のための効率的なツール」. ACM Journal of Experimental Algorithmics . 24 : 1.5:1–1.5:16. doi : 10.1145/3284360 . ISSN  1084-6654. S2CID  216028146.
4. Edelsbrunner, H および Harer, J (2010).計算トポロジー入門. アメリカ数学会.
5. Verri, A.; Uras, C.; Frosini, P.; Ferri, M. (1993). 「形状解析におけるサイズ関数の利用について」 .生物学的サイバネティクス. 70 (2): 99– 107. doi :10.1007/BF00200823. S2CID  39065932.
6. バラニコフ, セルゲイ (1994). 「フレームド・モース複体とその不変量」.ソビエト数学の進歩. 21 : 93–115 .
7. Zomorodian, Afra; Carlsson, Gunnar (2004-11-19). 「永続ホモロジーの計算」.離散幾何学と計算幾何学. 33 (2): 249– 274. doi : 10.1007/s00454-004-1146-y . ISSN  0179-5376.
8. Cohen-Steiner, David; Edelsbrunner, Herbert; Harer, John (2006-12-12). 「持続図の安定性​​」.離散幾何学と計算幾何学. 37 (1): 103– 120. doi : 10.1007/s00454-006-1276-5 . ISSN  0179-5376.
9. Morozov, Dmitriy; Skraba, Primoz (2024). 「行列乗算時間における永続的（コ）ホモロジー」. arXiv : 2412.02591 [math.AT].
10. Sheehy, Donald R. (2013年6月). 「Vietoris-Ripsろ過に対する線形サイズ近似」.離散幾何学と計算幾何学. 49 (4): 778– 796. arXiv : 1203.6786 . doi :10.1007/s00454-013-9513-1.
11. Botnan, Magnus Bakke; Spreemann, Gard (2015年3月). 「ユークリッド空間における持続ホモロジーの崩壊による近似」.応用代数工学、コミュニケーション、コンピューティング. 26 ( 1–2 ): 73–101 . arXiv : 1403.0533 . doi :10.1007/s00200-014-0247-y.
12. Choudhary, Aruni; Kerber, Michael; Raghvendra, Sharath (2021). 「シフト整数格子と立方体複体を用いた改良近似Rips濾過法」. Journal of Applied and Computational Topology . 5 (3): 425– 458. doi :10.1007/s41468-021-00072-4. MR  4298670. PMC 8549989 . ESA 2017 の予備版、doi : 10.4230/LIPIcs.ESA.2017.28。
13. Brun, Morten; Blaser, Nello (2019年6月). 「スパース・ダウカー神経」. Journal of Applied and Computational Topology . 3 ( 1–2 ): 1– 28. arXiv : 1802.03655 . doi : 10.1007/s41468-019-00028-9 .
14. Otter, Nina; Porter, Mason A; Tillmann, Ulrike; et al. (2017-08-09). 「パーシステントホモロジーの計算のためのロードマップ」. EPJ Data Science . 6 (1). Springer: 17. doi : 10.1140/epjds/s13688-017-0109-5 . ISSN  2193-1127. PMC 6979512. PMID 32025466  . 
15. ここでのライセンスは概要であり、ライセンスの完全な記述ではありません。一部のパッケージでは、異なるライセンスのライブラリを使用している場合があります。
16. バウアー、ウルリッヒ;ケルバー、マイケル。ヤン・ライニングハウス。ワーグナー、ヒューバート (2014)。 「PHAT – 永続的相同性アルゴリズム ツールボックス」。数学ソフトウェア – ICMS 2014。シュプリンガー ベルリン ハイデルベルク。 pp.  137–143。土井:10.1007/978-3-662-44199-2_24。ISBN 978-3-662-44198-5. ISSN  0302-9743.
17. Maria, Clément; Boissonnat, Jean-Daniel; Glisse, Marc; et al. (2014). 「Gudhiライブラリ：単体複体とパーシステントホモロジー」. Mathematical Software – ICMS 2014 (PDF) . ベルリン、ハイデルベルク：Springer. pp.  167– 174. doi :10.1007/978-3-662-44199-2_28. ISBN 978-3-662-44198-5. ISSN  0302-9743. S2CID  17810678.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Persistent_homology&oldid=1316553137"