Seminar ;SPMquot;`Topologie und Datenanalyse;SPMquot;'

Wissenschaftler aller Couleur sammeln heutzutags enorme Datenmengen. Der Flaschenhals wird mehr und mehr deren Auswertung. Insbesondere sollen die entscheidenden qualitativen Informationen effizient ermittelt werden (oft aus verrauschten, hochdimensionalen Daten, die in unnat<#49#>ü<#49#>rlichen Koordinaten vorliegen).

Topologie ist (vom Standpunkt der Geometrie in der reinen Mathematik) die Teildisziplin, welche genau diese Aufgabe leistet. Im letzten Jahrzehnt gibt es sehr aktive Entwicklungen dies auch in der Praxis umzusetzen.

Beispielhafte Frage: in einem Scan von Zellmembranen sollen die verschiedenen Komponenten voneinander unterschieden, Verbindungen entdeckt werden (insbesondere zeitliche Ver<#50#>ä<#50#>nderungen), aber dies bei verrauschten Daten: irrelevante Artefakte m<#51#>ü<#51#>ssen unterdr<#52#>ü<#52#>ckt werden.

Das Programm zur topologischen L<#53#>ö<#53#>sung, mit einigen der wichtigsten Ans<#54#>ä<#54#>tze, soll im Seminar erarbeitet werden, wobei wir auch bis zu (echten) Anwendungen kommen wollen.

Beispiele solcher Anwendungen:

Die wichtigsten topologischen Grundlagen bestehen darin:

Spezielle Entwicklungen der ``Topologie der Datenanalyse'' sind insbesondere

Ziel des Seminars ist, die topologischen Grundlagen einzuf<#68#>ü<#68#>hren (oder zu festigen), die speziellen theoretischen Konstruktionen kennen zu lernen, die dazugeh<#69#>ö<#69#>rigen Algorithmen zu verstehen und uns einige konkrete Anwendungen anzuschauen.

Je nach Vorwissen wird der Grundlagenteil gen<#70#>ü<#70#>gend ausf<#71#>ü<#71#>hrlich oder etwas knapper behandelt werden. Die Veranstaltung ist auf jeden Fall so konzipiert, dass das Basiswissen der ersten drei Semester f<#72#>ü<#72#>r die Teilnahme ausreicht.

Programm

Nr Thema Quelle Name Termin
1 Simplizialkomplexe EH, (Z) Nikolai Deuschle
2 Homologie: Einführung EH, (Z) Jan Hendrik Hofmann
3 Homologie II EH, (Z) Johannes Neumann, Benjamin Heuer
4 Cech- und Ripskomplexe EH III.2 Johannes Spille, Robert Hesse
5 sphärische Inversion, Voronoi-Zerlegung EH III.3, E Johannes Steiner
6 Delaunay- und alpha-Komplexe EH III.3, III.4, E Martin Holzke, Benjamin Heuer (?)
7 Persistente Homologie EH VII.1, Z, 6.1 Simon Naarmann
8 Algorithmen für (persistente) Homologie EH IV.2, VII.1, Z Kap 7 (?) Matthias Garbs
9 Algorithmus: Homologie von Teilmengen in #tex2html_wrap_inline279# EH V.4, DE Simon Beier
10 Stabilität von persistenter Homologie EH VIII.2 David Ellenberger
11 Kombinatorische Morse-Theorie für Entrauschen BLW 2-3 Malte Dehling
12 Optimaler Entrauschungsalgorithmus für Funktionen auf Flächen BLW 4--5 Carolin Homann
13 Anwendung: 1-dimensionale Gen-Expression EH IX.1 Michael Mathe
14 Anwendung: Taschen in Proteinen IX.2, GJ1 Corinna Krüger

  1. Simplizialkomplexe (EH III.1, M 1.1, 1.2 auch Z 2.3): Grundidee= kombinatorische Beschreibung geometrischer Objekte. Inhalt=geometrische, abstrakte Simplizialkomplexe, geometrische Realisierung, Triangulierung, Unterteilung, simpliziale Approximation.
  2. (Simpliziale) Homologie (EH IV.1, IV.2-Anfang, M 1 (Auswahl), Z 4.2, EH III.2): Grundidee= berechenbare Invarianten, welche grundlegende Eigenschaften eines geometrischen Objekts kodieren. Inhalt=Zyklen, R<#86#>ä<#86#>nder, Homologie, Beispielrechnungen, Euler Charakteristik, knapp: Z-und andere Koeffizienten; Homotopie, Homotopie<#87#>ä<#87#>quivalenz (Teil von EH III.2)
  3. Homologie II (EH IV.3, IV.4, M 1,2 (Auswahl)): Grundidee=wichtige fortgeschrittene Eigenschaften von Homologie, auch Berechnungsmethoden. relative Homologie, Paarsequenz, exakte Sequenzen, Mayer-Vietoris, Beispielrechnungen
  4. Cech- und Rips-Komplex (EH III.2): Grundidee= Vereinfachung eines geometrischen Objekts, indem geeignete <#88#>Ü<#88#>berdeckungen und die Kombinatorik der Schnittverhaltens der <#89#>Ü<#89#>berdeckungsmengen betrachtet wird. Inhalt=<#90#>Ü<#90#>berdeckungen, Nerv, Nerv-Theorem, Cech-Komplex und Rips-Komplex
  5. sph<#91#>ä<#91#>rische Inversion, Voronoi-Zerlegung (EH III.3, E): Grundidee=klassische geometrische Konstruktionen, um einer diskreten Punktmenge im #tex2html_wrap_inline386# eine sinnvolle ``Aufdickung'' zuzuordnen. Inhalt=sph<#92#>ä<#92#>rische Inversion, stereographische Projektion, Voronoi-Zellen, Voronoi-Zerlegung, Lift zur h<#93#>ö<#93#>heren Dimension; Gewichte eventuell kurz erw<#94#>ä<#94#>hnen, oder weglassen.
  6. Delaunay- und alpha-Komplexe (EH III.3,III.4, E): Grundidee=verfeinerte kombinatorische Beschreibung von aufgedickten diskreten Teilmengen des #tex2html_wrap_inline388#. Inhalt=Delaunay-Komplex, Delaunay-Triangulierung, alpha-Komplex, Filtrierung durch alpha, Hasse Diagramm, kritische <#95#>Ü<#95#>berg<#96#>ä<#96#>nge und regul<#97#>ä<#97#>rer Kollaps.
  7. Persistene Homologie (EH VII.1, Z 6.1 (Teil)): Grundidee=geschickte Nutzung von Topologie/Homologie und relevante Informationen <#98#>ü<#98#>ber geometrische Objekte halbautomatisch zu erhalten. Inhalt=Zusammenhangs-Komponenten-Beispiel, Vorrang des <#99#>Ä<#99#>lteren, Persistene Homologie, Persistenz-Diagramme, Beispiele (siehe insbesondere auch Z)
  8. Algorithmen f<#100#>ü<#100#>r persistente Homologie (EH IV.2, VII.1, Z 7.3): Grundidee=praktisch verwendbare Algorithmen zur Berechnung persistenter Homologie. Inhalt=matrix reduction for homology, for persistent homology ---description of algorithmen, example, analysis; (eventuell: sparse matrix technique).
  9. Algorithmus: Homologie von Unterkomplexen von #tex2html_wrap_inline390# (EH V.4, DE): Grundidee=f<#101#>ü<#101#>r die spezielle (aber praktisch relevante) Situation einer Teilmenge des #tex2html_wrap_inline392# effizienten Algorithmus zur Homologieberechnung. Inhalt=Schwerpunkt der Algorithmus; ggf.~knappe Behandlung von Alexander-Dualit<#102#>ä<#102#>t.; m<#103#>ö<#103#>gliche Erweiterung: Nutzung f<#104#>ü<#104#>r effiziente Algorithmen zu Persistenz (EH VII.2)
  10. Stabilit<#105#>ä<#105#>t von Persistenz (EH VIII.2): Grundidee=Persistene Homologie <#106#>ä<#106#>ndert sich wenig, wenn die Daten sich wenig <#107#>ä<#107#>ndern. Inhalt=Flaschenhals-Metrik, Flaschenhals-Stabilit<#108#>ä<#108#>t (f<#109#>ü<#109#>r zahme Funktionen), Wasserstein-Metrik, Wasserstein-Stabilit<#110#>ä<#110#>t (weniger Details). M<#111#>ö<#111#>gliche Erweiterung: Berechungsaspekte (EH VIII.1)
  11. Kombinatorische Morse-Theorie f<#112#>ü<#112#>r Entrauschen (BLW 2--3, F1, F2, AGHLM): Grundidee=kombinatorischer Prozess, um Funktionen auf einem Simplizialkomplex zu entrauschen/vereinfachen. Inhalt=kombinatorische Morsefunktionen, kombinatorische Vektorfelder, Ausl<#113#>ö<#113#>schung kritischer Zellen, Dualit<#114#>ä<#114#>t f<#115#>ü<#115#>r Fl<#116#>ä<#116#>chen
  12. Optimaler Entrauschungsalgorithmus f<#117#>ü<#117#>r Funktionen auf Fl<#118#>ä<#118#>chen (BLW 4--5): Grundidee: effizienter Algorithmus, welcher auf einer Fl<#119#>ä<#119#>che eine Funktion optimal entrauscht. Inhalt: Beschreibung des Algorithmus, Diskussion.
  13. Anwendung: 1-dimensionale Gen-Expression (EH IX.1): Grundidee: bei Entwicklung des Wirbeltier-Embryos steuern periodisch aktive Gene die Entwicklung der Wirbels<#120#>ä<#120#>ule (mit verschiedener Anzahl von Wirbeln); aber welche---Analyse mit persistenter Homologie
  14. Anwendung: Taschen in Proteinen (IX.2, GJ1): . Inhalt: Beschreibung des Problems, Diskussion des 1-dimensionaler ``Spielzeug-Fall'' aus EH; kurze Diskussion des Ansatzes aus (GJ1)


Literatur

(AGHLM) Attali, Glisse, Hornus,Lazarus, Morozov: Persistence-sensitive simplication of functions on surfaces in linear time
(BLW) Bauer, Lange, Wardetzky: Optimal topological simplification of discrete functions on surfaces.
(C) Carlsson, Gunnar: Topology and Data (<#123#>Ü<#123#>bersichtsartikel).
(DE) Delfinado and Edelsbrunner, H.: An efficient algorithm for Betti Numbers of Simplicial Complexes
(E) Edelsbrunner, H.: The union of balls and its dual shape, Discrete Comp. Geom. 13, 415-440 (1995)
(EH) Edelsbrunner, H.~and J. Harer. Computational Topology. An Introduction. Amer. Math. Soc., Providence, Rhode Island, 2009. (Lehrbuch).
(EMP) Edelsbrunner, Moroov, Pascucci: Persistence-sensitive simplification functions on 2-manifolds
(F1) R. Forman: Morse theory for cell complexes. Advances in Mathematics, 134(1):90–145, 1998.
(F2) R. Forman. A user’s guide to discrete Morse theory. S<#124#>é<#124#>minaire Lotharingien de Combinatoire, B48c: 1–35, 2002.
(GJ1) Giesen and John: The flow complex: a data structure for geometric modelling
(GJ2) Giesen and John: Computing the weighted flow complex
(M) Munkres, James: Elements of algebraic topology
(Z) Zomorodian, Afra: Computational topology (Lehrbuch)

Teilnehmer

  1. Simon Beier
  2. Rasmus Bentmann (ohne Vortrag)
  3. Jonas Conrad (ohne Vortrag)
  4. Malte Dehling
  5. Nicolai Deuschle
  6. David Ellenberger
  7. Matthias Garbs
  8. Robert Hesse
  9. Benjamin Heuer
  10. Jan Henrik Hofmann
  11. Martin Holzke
  12. Carolin Homann
  13. Corinna Krüger
  14. Michael Mathe
  15. Simon Naarmann
  16. Vlada Pototskaia (ohne Vortrag)
  17. Thomas Schick (ohne Vortrag)
  18. Johannes Steiner