A stability theorem for bigraded persistence barcodes

Technische Zusammenfassung: Ein Stabilitätssatz für bigraduierte Persistenz-Barcodes

Problemstellung
Die Arbeit adressiert zwei grundlegende Einschränkungen bei der Anwendung von bigraduierter persistenter Homologie auf Datenwissenschaften, speziell wenn diese aus den Moment-Angle-Komplexen $Z_K$ im Zusammenhang mit der Vietoris–Rips-Filtration eines endlichen Pseudo-metrischen Raumes $X$ abgeleitet werden.

Erstens ist die standardmäßige bigraduierte Homologie von Moment-Angle-Komplexen, obwohl theoretisch reichhaltig, rechnerisch prohibitiv. Durch die Hochster-Zerlegung erfordert die Berechnung dieser Gruppen die Berechnung der simplizialen Homologie aller vollen Unterkomplexe des zugrunde liegenden simplizialen Komplexes, eine Aufgabe, die mit der Größe der Daten schlecht skaliert.

Zweitens, was für Anwendungen in der Datenwissenschaft kritischer ist, fehlt der standardmäßigen bigraduierten persistenten Homologie eine Stabilitätseigenschaft. In der topologischen Datenanalyse gewährleistet Stabilität, dass kleine Störungen in den Eingangsdaten (gemessen an der Gromov–Hausdorff-Distanz) nur geringfügige Änderungen in den resultierenden Persistenz-Barcodes (gemessen an der Bottleneck-Distanz) bewirken. Ohne diese Eigenschaft sind die Invarianten nicht robust gegenüber Rauschen, was ihren Nutzen für reale Anwendungen einschränkt. Die Autoren stellen fest, dass während bigraduierte Persistenz Punktwolken unterscheiden kann, die durch gewöhnliche Persistenz ununterscheidbar sind (wie in Beispiel 3.4 gezeigt), ihr Mangel an Stabilität sie für praktische Anwendungen unbrauchbar macht.

Methodik
Um diese Probleme zu lösen, nutzen die Autoren die bigraduierte Doppel-Homologie von Moment-Angle-Komplexen, ein Konzept, das in [LPSS] eingeführt und untersucht wurde.

1. Konstruktion der Doppel-Homologie: Anstatt die standardmäßige Homologie $H_*(Z_K)$ zu verwenden, definieren die Autoren einen Kettenkomplex $CH_*(Z_K) = (H_*(Z_K), \partial')$ durch die Ausstattung der bigraduierten Homologiegruppen mit einer zweiten Differenzialen $\partial'$. Die Homologie dieses neuen Komplexes, bezeichnet als $HH_*(Z_K)$, ist die Doppel-Homologie.
2. Bigraduierte persistente Doppel-Homologie: Die Autoren definieren das bigraduierte persistente Doppel-Homologie-Modul $PHHZ(X)$, indem sie den Doppel-Homologie-Funktor auf die Moment-Angle-Komplexe $Z_{R(X,t)}$ anwenden, die mit der Vietoris–Rips-Filtration $\{R(X,t)\}_{t \geq 0}$ assoziiert sind.
3. Die Verdoppelungs-Operation: Ein zentrales technisches Werkzeug im Beweis ist die „Verdoppelungs“-Operation (Doubling) auf simplizialen Komplexen und pseudo-metrischen Räumen. Das Verdoppeln eines Vertex $i$ in einem Komplex $K$ (oder eines Punktes $x$ in einem Raum $X$) erzeugt einen neuen Komplex $K'$ (oder Raum $X'$), indem ein Duplikat des Vertex $i'$ (oder Punktes $x'$) mit dem Abstand Null zum Original hinzugefügt wird.
   • Entscheidend ist, dass das Verdoppeln die standardmäßige Homologie des Moment-Angle-Komplexes verändert (Beispiel 4.18), die Doppel-Homologie jedoch bewahrt (Proposition 4.19).
   • Darüber hinaus kann jede Korrespondenz zwischen zwei endlichen pseudo-metrischen Räumen als Bijektion zwischen deren iterierten Verdoppelungen realisiert werden (Proposition 4.16).

Wesentliche Beiträge und Ergebnisse

• Definition der bigraduierten persistenten Doppel-Homologie: Die Arbeit definiert formal die bigraduierten persistenten Doppel-Homologie-Module $PHHZ(X)$ und die dazugehörigen Barcodes $BB(X)$. Diese Module sind aufgrund der geringeren Größe der Doppel-Homologiegruppen rechentechnisch zugänglicher als ihre standardmäßigen bigraduierten Gegenstücke.
• Stabilität für gewöhnliche bigraduierte Persistenz (modifiziert): Die Autoren etablieren zunächst einen Stabilitätssatz für die standardmäßige bigraduierte persistente Homologie $PHZ(X)$. Dieser Stabilitätssatz gilt jedoch nur in Bezug auf eine modifizierte Gromov–Hausdorff-Distanz ($d'_{GH}$), welche das Infimum in der Definition der Distanz auf bijektive Korrespondenzen beschränkt (Theorem 4.21). Die Arbeit zeigt, dass die standardmäßige Gromov–Hausdorff-Distanz ($d_{GH}$) für die Stabilität von $PHZ(X)$ unzureichend ist, da das Verdoppeln eines Punktes den Barcode verändert, während $d_{GH}$ unverändert bleibt (Beispiel 4.18).
• Stabilitätssatz für die Doppel-Homologie: Das Hauptergebnis (Theorem 4.23) beweist, dass die bigraduierten persistenten Doppel-Homologie-Module einen Stabilitätssatz bezüglich der standardmäßigen Gromov–Hausdorff-Distanz erfüllen. Speziell gilt für zwei beliebige endliche pseudo-metrische Räume $X$ und $Y$:
  $$d_{IL}(PHHZ(X), PHHZ(Y)) \leq 2d_{GH}(X, Y)$$
  wobei $d_{IL}$ die Interleaving-Distanz ist.
• Anwendung des Isometrie-Theorems: Durch Anwendung des Isometrie-Theorems (Theorem 4.12) leiten die Autoren ein entsprechendes Stabilitätsergebnis für die bigraduierten Barcodes $BB(X)$ und $BB(Y)$ in Bezug auf die $\infty$-Wasserstein- ($\infty$-Bottleneck) Distanz ab (Korollar 4.24):
  $$W_\infty(BB(X), BB(Y)) \leq 2d_{GH}(X, Y)$$

Bedeutung und Behauptungen
Die Arbeit behauptet, dass die Einführung der bigraduierten persistenten Doppel-Homologie die beiden primären Nachteile des ursprünglichen bigraduierten Ansatzes löst.

1. Recheneffizienz: Die Doppel-Homologie-Module sind kleiner als die standardmäßigen bigraduierten Homologie-Module, was sie aus rechentechnischer Sicht zugänglicher macht.
2. Robustheit: Am wichtigsten ist, dass die Doppel-Homologie-Module die für datenwissenschaftliche Anwendungen essenzielle Stabilitätseigenschaft besitzen. Die Autoren geben an, dass diese Eigenschaft „etwa aussagt, dass der bigraduierte Barcode robust gegenüber Änderungen in den Eingangsdaten ist.“

Die Autoren betonen, dass die bigraduierte Persistenz zwar reichere algebraische Strukturen bietet und die Fähigkeit besitzt, Datensätze zu unterscheiden, die durch gewöhnliche Persistenz nicht unterscheidbar sind (Beispiel 3.4), sie jedoch zuvor aufgrund ihrer Instabilität in der Praxis unbrauchbar war. Der Stabilitätssatz für die Doppel-Homologie „öffnet einen Weg für eine effizientere Anwendung in der Datenanalyse“, indem er die diskriminative Kraft bigraduierter Invarianten mit der für verrauschte Daten erforderlichen Robustheit kombiniert. Die Arbeit schlägt keine neuen experimentellen Anwendungen vor, sondern schafft die theoretische Grundlage, die notwendig ist, um solche Anwendungen praktikabel zu machen.