インターリーブ距離
Measure of distance between persistence modules
2 つの - インデックス付き永続モジュール M と N 間の 1 インターリーブ。ベクトル空間とそれらの間の線形マップの図として表されます。 Z {\displaystyle \mathbb {Z} }

位相データ解析において、インターリービング距離はパーシステンスモジュール間の類似性の尺度であり、位相データ解析とパーシステントホモロジーの共通の研究対象です。インターリービング距離は、2009年にフレデリック・シャザールらによって初めて導入されました[1]。それ以来、インターリービング距離とその一般化は、応用代数位相幾何学と位相データ解析の研究において中心的な考察となっています[2] [3] [4] [5] [6] 。

意味

持続モジュールとは、 実数直線上でインデックス付けされたベクトル空間の集合と、が常に同型となり、任意の に対して の関係が満たされるような線型写像の集合である。ここでは単純化のためにインデックス付けの場合を示しているが、インターリーブ距離は多次元持続モジュールを含むより一般的な設定にも容易に適応できる。[7] V {\displaystyle \mathbb {V} } ( V t ∣ t ∈ R ) {\displaystyle (V_{t}\mid t\in \mathbb {R} )} ( v t s : V s → V t ∣ s ≤ t ) {\displaystyle (v_{t}^{s}:V_{s}\to V_{t}\mid s\leq t)} v t t {\displaystyle v_{t}^{t}} v t s ∘ v s r = v t r {\displaystyle v_{t}^{s}\circ v_{s}^{r}=v_{t}^{r}} r ≤ s ≤ t {\displaystyle r\leq s\leq t} R {\displaystyle \mathbb {R} }

とを永続モジュールとする。任意の に対して、-シフトは、との内部写像と可換な永続モジュール間の線形写像の集合である。 U {\displaystyle \mathbb {U} } V {\displaystyle \mathbb {V} } δ ∈ R {\displaystyle \delta \in \mathbb {R} } δ {\displaystyle \delta } ( ϕ t : U t → V t + δ ∣ t ∈ R ) {\displaystyle (\phi _{t}:U_{t}\to V_{t+\delta }\mid t\in \mathbb {R} )} U {\displaystyle \mathbb {U} } V {\displaystyle \mathbb {V} }

持続モジュールおよびは、次の図がすべての に対して可換となるような-シフトおよびがある場合、 -インターリーブされていると言われます。 U {\displaystyle \mathbb {U} } V {\displaystyle \mathbb {V} } δ {\displaystyle \delta } δ {\displaystyle \delta } ϕ t : U t → V t + δ {\displaystyle \phi _{t}:U_{t}\to V_{t+\delta }} ψ t : V t → U t + δ {\displaystyle \psi _{t}:V_{t}\to U_{t+\delta }} s ≤ t {\displaystyle s\leq t}

定義から、ある に対してと が-インターリーブされている場合、任意の正の に対しても と は -インターリーブされていることがわかります。したがって、2つのモジュール間の最も近いインターリーブを見つけるには、すべての可能なインターリーブにわたって最小値を求める必要があります。 U {\displaystyle \mathbb {U} } V {\displaystyle \mathbb {V} } δ {\displaystyle \delta } δ {\displaystyle \delta } ( δ + ε ) {\displaystyle (\delta +\varepsilon )} ε {\displaystyle \varepsilon }

2つの持続モジュール間のインターリーブ距離は次のように定義される。[8] U {\displaystyle \mathbb {U} } V {\displaystyle \mathbb {V} } d I ( U , V ) = inf { δ ∣ U  and  V  are  δ -interleaved } {\displaystyle d_{I}(\mathbb {U} ,\mathbb {V} )=\inf\{\delta \mid \mathbb {U} {\text{ and }}\mathbb {V} {\text{ are }}\delta {\text{-interleaved}}\}}

プロパティ

メトリックのプロパティ

インターリーブ距離は三角不等式を満たすことが示される。つまり、3つの持続モジュール、、およびが与えられた場合、不等式は満たされる。[8] U {\displaystyle \mathbb {U} } V {\displaystyle \mathbb {V} } W {\displaystyle \mathbb {W} } d I ( U , W ) ≤ d I ( U , V ) + d I ( V , W ) {\displaystyle d_{I}(\mathbb {U} ,\mathbb {W} )\leq d_{I}(\mathbb {U} ,\mathbb {V} )+d_{I}(\mathbb {V} ,\mathbb {W} )}

一方、同型ではないもののインターリーブ距離が0である持続モジュールの例もあります。さらに、適切な持続モジュールが存在しない場合、2つの持続モジュールは無限のインターリーブ距離を持つと言われています。これらの2つの性質により、インターリーブ距離は拡張擬距離となります。つまり、同一でないオブジェクトは距離が0になることが許され、オブジェクトは無限の距離を持つことが許されますが、適切な距離の他の性質は満たされます。 δ {\displaystyle \delta }

インターリービング距離とその変種のさらなる測定特性は、2020年にルイス・スコッコラによって調査されました。[9]

計算の複雑さ

2つの単一パラメータ持続モジュール間のインターリーブ距離の計算は多項式時間で達成できる。一方、2018年には、2つの多次元持続モジュール間のインターリーブ距離の計算はNP困難であることが示された。[10] [11]

参考文献

  1. ^ Chazal, Frédéric; Cohen-Steiner, David; Glisse, Marc; Guibas, Leonidas J.; Oudot, Steve Y. (2009-06-08). 「持続モジュールの近接性とそれらのダイアグラム」. 第25回計算幾何学シンポジウム論文集. SCG '09. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  237– 246. doi :10.1145/1542362.1542407. ISBN 978-1-60558-501-7. S2CID  840484。
  2. ^ Nelson, Bradley J.; Luo, Yuan (2022-01-31). 「インターリーブ最適化によるトポロジー保存次元削減」arXiv : 2201.13012 [cs.LG].
  3. ^ 「マージツリー間のインターリービング距離 « 出版物 « Dmitriy Morozov」mrzv.org . 2023年4月7日閲覧。
  4. ^ Meehan, Killian; Meyer, David (2017-10-29). 「インターリービング距離の限界」arXiv : 1710.11489 [math.AT].
  5. ^ エリザベス・ムンク、アナスタシオス・ステファノウ（2019）、エレン・ガスパロヴィッチ、カルロッタ・ドメニコーニ（編）、「系統樹におけるインターリービング距離としてのℓ∞-コフェネティックメトリック」、データサイエンス研究、第17巻、Cham：Springer International Publishing、pp.  109– 127、doi：10.1007/978-3-030-11566-1_5、ISBN 978-3-030-11565-4, S2CID  4708500 , 2023年4月7日取得
  6. ^ de Silva, Vin; Munch, Elizabeth; Stefanou, Anastasios (2018-05-30). 「フローを持つカテゴリ上のインターリービング理論」arXiv : 1706.04095 [math.CT].
  7. ^ Lesnick, Michael (2015-06-01). 「多次元パーシスタンス・モジュールにおけるインターリービング距離の理論」.計算数学の基礎. 15 (3): 613– 650. arXiv : 1106.5305 . doi :10.1007/s10208-015-9255-y. ISSN  1615-3383. S2CID  254158297.
  8. ^ ab Chazal, Frédéric; de Silva, Vin; Glisse, Marc; Oudot, Steve (2016). 持続モジュールの構造と安定性. SpringerBriefs in Mathematics. Cham: Springer International Publishing. pp.  67– 83. arXiv : 1207.3674 . doi :10.1007/978-3-319-42545-0. ISBN 978-3-319-42543-6. S2CID  2460562。
  9. ^ Scoccola, Luis (2020-07-15). 局所的に永続的なカテゴリーとインターリービング距離の計量特性.電子論文リポジトリ(論文).
  10. ^ Bjerkevik、Håvard Bakke;ボトナン、マグヌス・バッケ。ケルバー、マイケル (2019-10-09)。 「インターリーブ距離の計算は NP 困難です。」arXiv : 1811.09165 [cs.CG]。
  11. ^ Bjerkevik、Håvard Bakke;ボトナン、マグヌス・バッケ (2018-04-30)。 「インターリーブ距離の計算の複雑さ」。arXiv : 1712.04281 [cs.CG]。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Interleaving_distance&oldid=1309655160"