Trvalá homologie - Persistent homology

Vidět homologie pro úvod do notace.

Trvalá homologie je metoda pro výpočet topologických rysů prostoru v různých prostorových rozlišeních. Trvalejší funkce jsou detekovány v širokém rozsahu prostorových měřítek a jsou považovány za pravděpodobnější, že představují skutečné vlastnosti podkladového prostoru, spíše než artefakty vzorkování, šumu nebo konkrétní volby parametrů.^[1]

Chcete-li najít trvalou homologii prostoru, musí být prostor nejprve reprezentován jako zjednodušený komplex. Funkce vzdálenosti na podkladovém prostoru odpovídá a filtrace zjednodušeného komplexu, to je vnořená sekvence zvyšujících se podmnožin.

Definice

Formálně zvažte funkci se skutečnou hodnotou zjednodušeného komplexu ${ displaystyle f: K rightarrow mathbb {R}}$ to není snižující se na rostoucí posloupnosti tváří, tak ${ displaystyle f ( sigma) leq f ( tau)}$ kdykoli ${ displaystyle sigma}$ je tváří ${ displaystyle tau}$ v ${ displaystyle K}$. Pak pro každého ${ displaystyle a in mathbb {R}}$ the sada podúrovní ${ displaystyle K (a) = f ^ {- 1} (- infty, a]}$ je dílčí komplex K.a řazení hodnot ${ displaystyle f}$ na jednoduchosti v ${ displaystyle K}$ (což je v praxi vždy konečné) vyvolá uspořádání na podúrovňových komplexech, které definuje filtraci

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

Když ${ displaystyle 0 leq já leq j leq n}$, zahrnutí ${ displaystyle K_ {i} hookrightarrow K_ {j}}$ indukuje a homomorfismus ${ displaystyle f_ {p} ^ {i, j}: H_ {p} (K_ {i}) rightarrow H_ {p} (K_ {j})}$ na zjednodušená homologie skupiny pro každou dimenzi ${ displaystyle p}$. The ${ displaystyle p ^ { text {th}}}$ skupiny trvalé homologie jsou obrazy těchto homomorfismů a ${ displaystyle p ^ { text {th}}}$ vytrvalý Betti čísla ${ displaystyle beta _ {p} ^ {i, j}}$ jsou hodnosti těchto skupin.^[2] Trvalá čísla Betti pro ${ displaystyle p = 0}$ shodovat se s funkce velikosti, předchůdce trvalé homologie.^[3]

Libovolný filtrovaný komplex přes pole ${ displaystyle F}$ lze přenést lineární transformací zachovávající filtraci na tzv kanonická forma, kanonicky definovaný přímý součet filtrovaných komplexů dvou typů: jednorozměrné komplexy s triviálním diferenciálem ${ displaystyle d (e_ {t_ {i}}) = 0}$ a dvourozměrné komplexy s triviální homologií ${ displaystyle d (e_ {s_ {j} + r_ {j}}) = e_ {r_ {j}}}$.^[4]

A modul perzistence přes částečně objednané soubor ${ displaystyle P}$ je sada vektorových prostorů ${ displaystyle U_ {t}}$ indexováno podle ${ displaystyle P}$, s lineární mapou ${ displaystyle u_ {t} ^ {s}: U_ {s} do U_ {t}}$ kdykoli ${ displaystyle s leq t}$, s ${ displaystyle u_ {t} ^ {t}}$ rovná se totožnosti a ${ displaystyle u_ {t} ^ {s} circ u_ {s} ^ {r} = u_ {t} ^ {r}}$ pro ${ displaystyle r leq s leq t}$. Rovněž to můžeme považovat za funktor z ${ displaystyle P}$ považována za kategorii do kategorie vektorových prostorů (nebo ${ displaystyle R}$- moduly ). V poli existuje klasifikace modulů perzistence ${ displaystyle F}$ indexováno podle ${ displaystyle mathbb {N}}$:

Násobení ${ displaystyle x}$ odpovídá posunu o jeden krok vpřed v modulu perzistence. Volné části na pravé straně intuitivně odpovídají generátorům homologie, které se objevují na úrovni filtrace ${ displaystyle t_ {i}}$ a nikdy nezmizí, zatímco torzní části odpovídají těm, které se objevují na filtrační úrovni ${ displaystyle r_ {j}}$ a poslední pro ${ displaystyle s_ {j}}$ kroky filtrace (nebo ekvivalentně zmizí na filtrační úrovni ${ displaystyle s_ {j} + r_ {j}}$).^{[5] [4]}

Každá z těchto dvou vět nám umožňuje jedinečně reprezentovat trvalou homologii filtrovaného zjednodušeného komplexu s a čárový kód nebo diagram perzistence. Čárový kód představuje každý perzistentní generátor s vodorovnou čarou začínající na první filtrační úrovni, kde se zobrazuje, a končící na filtrační úrovni, kde zmizí, zatímco diagram perzistence vykreslí bod pro každý generátor s jeho x-ovou souřadnicí doby narození a jeho y-koordinovat čas smrti. Stejná data jsou rovnocenně reprezentována Barannikovovými kanonická forma^[4], kde každý generátor je reprezentován segmentem spojujícím hodnoty narození a smrti vynesené na samostatných řádcích pro každý z nich ${ displaystyle p}$.

Stabilita

Trvalá homologie je stabilní v přesném smyslu, což poskytuje odolnost proti hluku. V prostoru perzistenčních diagramů je dána přirozená metrika

volal vzdálenost úzkého hrdla. Malé narušení vstupní filtrace vede k malému narušení jeho perzistenčního diagramu ve vzdálenosti úzkého hrdla. Z důvodu konkrétnosti zvažte filtraci v prostoru ${ displaystyle X}$ homeomorfní na zjednodušený komplex určený podúrovňovými množinami spojité krotké funkce ${ displaystyle f: X to mathbb {R}}$. Mapa ${ displaystyle D}$ brát ${ displaystyle f}$ na perzistenční diagram ${ displaystyle k}$homologie je 1-Lipschitz s ohledem na ${ displaystyle sup}$-metrický na funkce a úzká vzdálenost na diagramech perzistence. To znamená, ${ displaystyle W _ { infty} (D (f), D (g)) leq lVert f-g rVert _ { infty}}$. ^[6]

Výpočet

Existují různé softwarové balíčky pro výpočet intervalů perzistence konečné filtrace ^[7] . Hlavní algoritmus je založen na přenesení filtrovaného komplexu do jeho kanonická forma horní trojúhelníkové matice^[4].

Softwarový balíček	Tvůrce	Poslední vydání	Datum vydání	Softwarová licence[8]	Otevřený zdroj	Programovací jazyk	Funkce
OpenPH	Rodrigo Mendoza-Smith, Jared Tanner	0.0.1	25. dubna 2019	Apache 2.0	Ano	Matlab, CUDA
javaPlex	Andrew Tausz, Mikael Vejdemo-Johansson, Henry Adams	4.2.5	14. března 2016	Zvyk	Ano	Jáva, Matlab
Dionýsos	Dmitrij Morozov	2.0.8	24. listopadu 2020	Upravená BSD	Ano	C ++, Krajta vazby
Perseus	Vidit Nanda	4.0 beta		GPL	Ano	C ++
PHAT [9]	Ulrich Bauer, Michael Kerber, Jan Reininghaus	1.4.1			Ano	C ++
DIPHA	Jan Reininghaus				Ano	C ++
Gudhi [10]	INRIA	3.0.0	23. září 2019	GPLv3	Ano	C ++, Krajta vazby
CTL	Ryan lewis	0.2		BSD	Ano	C ++
phom	Andrew Tausz				Ano	R
TDA	Brittany T. Fasy, Jisu Kim, Fabrizio Lecci, Clement Maria, Vincent Rouvreau	1.5	16. června 2016		Ano	R
Eirene	Gregory Henselman	1.0.1	9. března 2019	GPLv3	Ano	Julie
Ripser	Ulrich Bauer	1.0.1	15. září 2016	MIT	Ano	C ++
sada nástrojů topologie	Julien Tierny, Guillaume Favelier, Joshua Levine, Charles Gueunet, Michael Michaux	0.9.8	29. července 2019	BSD	Ano	C ++, VTK a Krajta vazby
libstick	Stefan Huber	0.2	27. listopadu 2014	MIT	Ano	C ++
Ripser ++	Simon Zhang, Mengbai Xiao a Hao Wang	1.0	Březen 2020	MIT	Ano	CUDA, C ++, Krajta vazby	Zrychlení GPU

Viz také

• Analýza topologických dat
• Výpočetní topologie

Reference