인터리빙 거리

두

{

인덱스

\mathbb {Z}

지속성 모듈 M과 N 사이의 1-interleaving은 벡터 공간과 그들 사이의 선형 맵의 다이어그램으로 표현됩니다.

위상 데이터 분석에서 인터리빙 거리(interleaving distance)는 위상 데이터 분석과 지속적인 상동성에서 공통적인 연구 대상인 지속성 모듈 간의 유사성의 척도입니다.인터리빙 거리는 2009년 ^[1]Fredédéric Chazal 등에 의해 처음 도입되었습니다. 그 이후로, 그것과 그것의 일반화는 적용된 대수 토폴로지 및 위상 데이터 ^[2]^[3]^[4]^[5]^[6]분석 연구에서 중심적인 고려 사항이었습니다.

정의.

지속성 $\mathbb {V}$ V ${\displaystyle$ \ $mathbb$ { $V}$ 는 $\mathbb {V}$ 실선을 통해 인덱싱된 벡터 공간의 집합 $(V_{t}\mid t\in \mathbb {R} )$ $(v_{t}^{s}:V_{s}\to V_{t}\mid s\leq t)$ R ) \ $displaystyle$ (V $(V_{t}\mid t\in \mathbb {R} )$ t ∣ \ $mid$ t \ $in \mathbb {R$ })이며 $(V_{t}\mid t\in \mathbb {R} )$ , 집합 $(v_{t}^{s}:V_{s}\to V_{t}\mid s\leq t)$ s : $(v_{t}^{s}:V_{s}\to V_{t}\mid s\leq t)$ $(v_{t}^{s}:V_{s}\to V_{t}\mid s\leq t)$ → V $(v_{t}^{s}:V_{s}\to V_{t}\mid s\leq t)$ ▁ $(v_{t}^{s}:V_{s}\to V_{t}\mid s\leq t)$ t $(v_{t}^{s}:V_{s}\to V_{t}\mid s\leq t)$ t ) {\ $displaystyle (v _$ t }{ $t$ }: ${$ $displaystyle$ $v_{t}^{s}\circ v_{s}^{r}=v_{t}^{r}$ ${t}^{t}}$ 이 $v_{t}^{t}$ (가) 항상 동형인 선형 $맵의 V_$ {t}\ $mids\leq)}$ 와 $(v_{t}^{s}:V_{s}\to V_{t}\mid s\leq t)$ 같은 선형 맵의 ${$ 는 $r\leq s\leq t$ r≤ $s≤{t$ $}^{r}$ $r\leq s\leq t$ $v_{t$ $}\leq$ $}$ 에 $v_{t}^{s}\circ v_{s}^{r}=v_{t}^{r}$ 대해 만족됩니다.인터리빙 거리는 다차원 지속성 ^[7]모듈을 포함한 $보다$ 일반적인 $\mathbb {R}$ $\mathbb {R}$ 에 쉽게 적응할 수 있지만 $,$ R ${displaystyle$ \ $mathbb$ {R $}$ 인덱싱의 경우는 단순성을 위해 여기에 제시됩니다.

U ${$ $\mathbb {V}$ V ${$ 를 $\mathbb {V}$ 지속성 모듈로 $\mathbb {U}$ 합니다.그러면 임의의 $\delta$ R $\delta \in \mathbb {R}$ {R $\delta \in \mathbb {R}$ 에 대해, $\delta$ $(\phi _{t}:U_{t}\to V_{t+\delta }\mid t\in \mathbb {R} )$ {\ $displaystyle$ \displaystyle $\delta$ } -shift는 $\delta$ $(\phi _{t}:U_{t}\to V_{t+\delta }\mid t\in \mathbb {R} )$ 집합 ( $(\phi _{t}:U_{t}\to V_{t+\delta }\mid t\in \mathbb {R} )$ $(\phi _{t}:U_{t}\to V_{t+\delta }\mid t\in \mathbb {R} )$ $(\phi _{t}:U_{t}\to V_{t+\delta }\mid t\in \mathbb {R} )$ → $(\phi _{t}:U_{t}\to V_{t+\delta }\mid t\in \mathbb {R} )$ + $(\phi _{t}:U_{t}\to V_{t+\delta }\mid t\in \mathbb {R} )$ $(\phi _{t}:U_{t}\to V_{t+\delta }\mid t\in \mathbb {R} )$ R ) ${\phi$ _ ${t})$ 입니다 $.$ U ${$ 와 $\mathbb {U}$ V ${$ 의 $(\phi _{t}:U_{t}\to V_{t+\delta }\mid t\in \mathbb {R} )$ $\mathbb {U}$ 맵과 통근하는 지속성 모듈 사이의 선형 맵의 $U_{t}\to$ V_ ${t+\delta}\midt\in \mathbbb {R}.$

지속성 $\mathbb {U}$ U({ $displaystyle$ \ $mathbb$ {U $\mathbb {U}$ $})$ 와 V({ $displaystyle$ \mathbb { $V})$ 는 $\mathbb {V}$ $\delta$ $\phi _{t}:U_{t}\to V_{t+\delta }$ {\displaystyle \mathbb $\phi _{t}:U_{t}\to V_{t+\delta }$ $}$ - $\phi _{t}:U_{t}\to V_{t+\delta }$ : Ut $\mathbb {U}$ $\phi _{t}:U_{t}\to V_{t+\delta }$ $\phi _{t}:U_{t}\to V_{t+\delta }$ + $\phi _{t}:U_{t}\to V_{t+\delta }$ {{ $t}$ 이 $\phi _{t}:U_{t}\to V_{t+\delta }$ δ ${\displaystyle}$ -interleaved라고 $\delta$ 합니다. $U_{t}\to$ V_ ${t+\delta}}$ 및 $\phi _{t}:U_{t}\to V_{t+\delta }$ $\psi _{t}:V_{t}\to U_{t+\delta }$ t : $\psi _{t}:V_{t}\to U_{t+\delta }$ t $\psi _{t}:V_{t}\to U_{t+\delta }$ → $\psi _{t}:V_{t}\to U_{t+\delta }$ + ${\$ _{ $t}:$ $V_{t}\to$ U_ ${t+\delta}:$ $≤{\displaystyle$ s $\leq$ 에 $\psi _{t}:V_{t}\to U_{t+\delta }$ 대해 다음 다이어그램이 통근하도록 합니다.

만약 ${$ 와 $\mathbb {U}$ V ${$ $displaystyle$ $\mathbb {V}$ 가 $\mathbb {V}$ $\delta$ $\delta$ 으로든 $π{$ displaystyle $\$ $delta$ 에 $\delta$ 대해 인터리브된다면,그러면 ( $(\delta +\varepsilon )$ + $(\delta +\varepsilon )$ $\varepsilon$ ) \\delta + \varepsilon $(\delta$ +\ $varepsilon$ 도 $(\delta +\varepsilon )$ 임의의 양의 $ε$ 에 대해 $(\delta +\varepsilon )$ 인터리빙됩니다. 따라서 두 모듈 사이에서 가장 가까운 인터리빙을 찾기 위해서는 가능한 모든 인터리빙에서 최소값을 취해야 합니다.

두 지속성 $\mathbb {U}$ U $({$ 와 $\mathbb {U}$ $\mathbb {V}$ V $({$ 사이의 인터리빙 $d_{I}(\mathbb {U} ,\mathbb {V} )=\inf\{\delta \mid \mathbb {U} {\text{ and }}\mathbb {V} {\text{ are }}\delta {\text{-interleaved}}\}$ 는 $d_{I}(\mathbb {U} ,\mathbb {V} )=\inf\{\delta \mid \mathbb {U} {\text{ and }}\mathbb {V} {\text{ are }}\delta {\text{-interleaved}}\}$ I $d_{I}(\mathbb {U} ,\mathbb {V} )=\inf\{\delta \mid \mathbb {U} {\text{ and }}\mathbb {V} {\text{ are }}\delta {\text{-interleaved}}\}$ $d_{I}(\mathbb {U} ,\mathbb {V} )=\inf\{\delta \mid \mathbb {U} {\text{ and }}\mathbb {V} {\text{ are }}\delta {\text{-interleaved}}\}$ = $d_{I}(\mathbb {U} ,\mathbb {V} )=\inf\{\delta \mid \mathbb {U} {\text{ and }}\mathbb {V} {\text{ are }}\delta {\text{-interleaved}}\}$ { $d_{I}(\mathbb {U} ,\mathbb {V} )=\inf\{\delta \mid \mathbb {U} {\text{ and }}\mathbb {V} {\text{ are }}\delta {\text{-interleaved}}\}$ U $d_{I}(\mathbb {U} ,\mathbb {V} )=\inf\{\delta \mid \mathbb {U} {\text{ and }}\mathbb {V} {\text{ are }}\delta {\text{-interleaved}}\}$ $d_{I}(\mathbb {U} ,\mathbb {V} )=\inf\{\delta \mid \mathbb {U} {\text{ and }}\mathbb {V} {\text{ are }}\delta {\text{-interleaved}}\}$ 는 δ - $}(\mathbb{U},$ $\mathbb {V})=\inf\{\inf\{\$ mathbb $\mid \mathbb$ { $U}({$ text{ $d_{I}(\mathbb {U} ,\mathbb {V} )=\inf\{\delta \mid \mathbb {U} {\text{ and }}\mathbb {V} {\text{ are }}\delta {\text{-interleaved}}\}$ 및 $})\mathbb$ { $V}({text{$ 및 $})\mathbb$ {{text{- $interleaved$ ^[8]

특성.

메트릭 속성

인터리빙 거리가 삼각 부등식을 만족한다는 것을 보여줄 수 있습니다.즉, 세 개의 지속성 $\mathbb {U}$ U ${\$ ${U$ {\ $displaystyle$ \ $mathbb$ {V $},$ ${\$ \ $mathbb {W}$ 가 $d_{I}(\mathbb {U} ,\mathbb {W} )\leq d_{I}(\mathbb {U} ,\mathbb {V} )+d_{I}(\mathbb {V} ,\mathbb {W} )$ $부등식$ d( $d_{I}(\mathbb {U} ,\mathbb {W} )\leq d_{I}(\mathbb {U} ,\mathbb {V} )+d_{I}(\mathbb {V} ,\mathbb {W} )$ $d_{I}(\mathbb {U} ,\mathbb {W} )\leq d_{I}(\mathbb {U} ,\mathbb {V} )+d_{I}(\mathbb {V} ,\mathbb {W} )$ $d_{I}(\mathbb {U} ,\mathbb {W} )\leq d_{I}(\mathbb {U} ,\mathbb {V} )+d_{I}(\mathbb {V} ,\mathbb {W} )$ $($ $d_{I}(\mathbb {U} ,\mathbb {W} )\leq d_{I}(\mathbb {U} ,\mathbb {V} )+d_{I}(\mathbb {V} ,\mathbb {W} )$ + $dI(V,$ W)가 $주어집니다.$ \ $mathbb {V})+d_{I}(\mathbb {V},\mathbb {W})}$ 이 $d_{I}(\mathbb {U} ,\mathbb {W} )\leq d_{I}(\mathbb {U} ,\mathbb {V} )+d_{I}(\mathbb {V} ,\mathbb {W} )$ (^[8]가) 충족됩니다 $.$

반면에, 동형은 아니지만 인터리빙 거리가 0인 지속성 모듈의 예가 있습니다.또한, 적절한 $δ$ {\displaystyle $\delta}$ 가 $\delta$ 존재하지 않으면 두 개의 지속성 모듈은 무한한 인터리빙 거리를 갖는다고 합니다.이 두 속성은 인터리빙 거리를 확장된 유사 측정법으로 만듭니다. 즉, 동일하지 않은 객체는 거리 0을 가질 수 있고 객체는 무한한 거리를 가질 수 있지만 적절한 메트릭의 다른 속성은 충족됩니다.

루이스 스코콜라는 2020년에 인터리빙 거리와 그 ^[9]변형의 추가 메트릭 특성을 조사했습니다.

계산 복잡도

두 개의 단일 매개 변수 지속성 모듈 사이의 인터리빙 거리를 계산하는 것은 다항 시간 내에 달성될 수 있습니다.반면, 2018년에 두 개의 다차원 지속성 모듈 사이의 인터리빙 거리를 계산하는 것은 ^[10]^[11]NP-hard인 것으로 나타났습니다.

레퍼런스

^ Chazal, Frédéric; Cohen-Steiner, David; Glisse, Marc; Guibas, Leonidas J.; Oudot, Steve Y. (2009-06-08). "Proximity of persistence modules and their diagrams". Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry. SCG '09. New York, NY, USA: Association for Computing Machinery: 237–246. doi:10.1145/1542362.1542407. ISBN 978-1-60558-501-7. S2CID 840484.
^ Nelson, Bradley J.; Luo, Yuan (2022-01-31). "Topology-Preserving Dimensionality Reduction via Interleaving Optimization". arXiv:2201.13012 [cs.LG].
^ "Interleaving Distance between Merge Trees « Publications « Dmitriy Morozov". mrzv.org. Retrieved 2023-04-07.
^ Meehan, Killian; Meyer, David (2017-10-29). "Interleaving Distance as a Limit". arXiv:1710.11489 [math.AT].
^ Munch, Elizabeth; Stefanou, Anastasios (2019), Gasparovic, Ellen; Domeniconi, Carlotta (eds.), "The ℓ ∞-Cophenetic Metric for Phylogenetic Trees As an Interleaving Distance", Research in Data Science, Cham: Springer International Publishing, vol. 17, pp. 109–127, doi:10.1007/978-3-030-11566-1_5, ISBN 978-3-030-11565-4, S2CID 4708500, retrieved 2023-04-07
^ de Silva, Vin; Munch, Elizabeth; Stefanou, Anastasios (2018-05-30). "Theory of interleavings on categories with a flow". arXiv:1706.04095 [math.CT].
^ Lesnick, Michael (2015-06-01). "The Theory of the Interleaving Distance on Multidimensional Persistence Modules". Foundations of Computational Mathematics. 15 (3): 613–650. arXiv:1106.5305. doi:10.1007/s10208-015-9255-y. ISSN 1615-3383. S2CID 254158297.
^ ^a ^b Chazal, Frédéric; de Silva, Vin; Glisse, Marc; Oudot, Steve (2016). The Structure and Stability of Persistence Modules. SpringerBriefs in Mathematics. Cham: Springer International Publishing. pp. 67–83. doi:10.1007/978-3-319-42545-0. ISBN 978-3-319-42543-6. S2CID 2460562.
^ Scoccola, Luis (2020-07-15). "Locally Persistent Categories And Metric Properties Of Interleaving Distances". Electronic Thesis and Dissertation Repository.
^ Bjerkevik, Håvard Bakke; Botnan, Magnus Bakke; Kerber, Michael (2019-10-09). "Computing the interleaving distance is NP-hard". arXiv:1811.09165 [cs.CG].
^ Bjerkevik, Håvard Bakke; Botnan, Magnus Bakke (2018-04-30). "Computational Complexity of the Interleaving Distance". arXiv:1712.04281 [cs.CG].

[1] Chazal, Frédéric; Cohen-Steiner, David; Glisse, Marc; Guibas, Leonidas J.; Oudot, Steve Y. (2009-06-08). "Proximity of persistence modules and their diagrams". Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry. SCG '09. New York, NY, USA: Association for Computing Machinery: 237–246. doi:10.1145/1542362.1542407. ISBN 978-1-60558-501-7. S2CID 840484.

[2] Nelson, Bradley J.; Luo, Yuan (2022-01-31). "Topology-Preserving Dimensionality Reduction via Interleaving Optimization". arXiv:2201.13012 [cs.LG].

[3] "Interleaving Distance between Merge Trees « Publications « Dmitriy Morozov". mrzv.org. Retrieved 2023-04-07.

[4] Meehan, Killian; Meyer, David (2017-10-29). "Interleaving Distance as a Limit". arXiv:1710.11489 [math.AT].

[5] Munch, Elizabeth; Stefanou, Anastasios (2019), Gasparovic, Ellen; Domeniconi, Carlotta (eds.), "The ℓ ∞-Cophenetic Metric for Phylogenetic Trees As an Interleaving Distance", Research in Data Science, Cham: Springer International Publishing, vol. 17, pp. 109–127, doi:10.1007/978-3-030-11566-1_5, ISBN 978-3-030-11565-4, S2CID 4708500, retrieved 2023-04-07

[6] Silva, Vin; Munch, Elizabeth; Stefanou, Anastasios (2018-05-30). "Theory of interleavings on categories with a flow". arXiv:1706.04095 [math.CT].

[7] Lesnick, Michael (2015-06-01). "The Theory of the Interleaving Distance on Multidimensional Persistence Modules". Foundations of Computational Mathematics. 15 (3): 613–650. arXiv:1106.5305. doi:10.1007/s10208-015-9255-y. ISSN 1615-3383. S2CID 254158297.

[:0-8] Chazal, Frédéric; de Silva, Vin; Glisse, Marc; Oudot, Steve (2016). The Structure and Stability of Persistence Modules. SpringerBriefs in Mathematics. Cham: Springer International Publishing. pp. 67–83. doi:10.1007/978-3-319-42545-0. ISBN 978-3-319-42543-6. S2CID 2460562.

[9] Scoccola, Luis (2020-07-15). "Locally Persistent Categories And Metric Properties Of Interleaving Distances". Electronic Thesis and Dissertation Repository.

[10] Bjerkevik, Håvard Bakke; Botnan, Magnus Bakke; Kerber, Michael (2019-10-09). "Computing the interleaving distance is NP-hard". arXiv:1811.09165 [cs.CG].

[11] Bjerkevik, Håvard Bakke; Botnan, Magnus Bakke (2018-04-30). "Computational Complexity of the Interleaving Distance". arXiv:1712.04281 [cs.CG].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Search

인터리빙 거리

네임스페이스

더

목차

정의.

특성.

메트릭 속성

계산 복잡도

레퍼런스