Seminar ;SPMquot;`Topologie und Datenanalyse;SPMquot;'
- Dozenten: Thomas Schick und Max Wardetzky
- Thema: Topologie und Datenanalyse
- Gebiet: Topologie, mit Bezug zur angewandten Mathematik
- Interessentenkreis: ab 5. Semester, Studenten der Mathematik
- Termin: nach Vereinbarung, Di, 14:15-15:55
- Ort: Sitzungszimmer
- Kontakt/Fragen:
schick@math.uni-goettingen.de, Tel.~39-7799
cd
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:
- aus einer Menge von Punkten in #tex2html_wrap_inline276#, welche (Zentren von) Atomen
eines gro<#57#>ß<#57#>en Molek<#58#>ü<#58#>ls festlegen, effizient Kavit<#59#>ä<#59#>ten oder Tunnel im
Molek<#60#>ü<#60#>l bestimmen!
- Rekonstruktion von (Ober)fl<#61#>ä<#61#>chen aus Datenpunkten
Die wichtigsten topologischen Grundlagen bestehen darin:
- Simplizialkomplexe zu kennen und einzusetzen
- Homologie (von Simplizialkomplexen) zu kennen, berechnen und
interpretieren zu k<#64#>ö<#64#>nnen.
- Homologie als Funktor zu verstehen
- kombinatorische Laplace-Operatoren.
- Fortgeschrittene Berechnungsmethoden von Homologie aus der homologischen
Algebra (exakte Sequenzen, bis zur Spektralsequenzen)
- Morse-Theorie zur Beschreibung von Homologie einzusetzen.
Spezielle Entwicklungen der ``Topologie der Datenanalyse'' sind insbesondere
- geschickte Konstruktionen von Simplizialkomplexen aus Daten,
z.B. Rips-Komplexe, Delauny-Triangulierungen, Zeugen-Komplexe, alpha-Formen; und diese zu
vergleichen
- persistente Homologie und bar-codes
- (effiziente) Algorithmen zur Berechnung von Homologie
- Morse-Theorie des Fluss-Komplexes
- lokale Homologie
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 |
|
|
|
- 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.
- (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)
- 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
- 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
- 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.
- 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.
- 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)
- 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).
- 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)
- 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)
- 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
- 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.
- 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
- 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
- Simon Beier
- Rasmus Bentmann (ohne Vortrag)
- Jonas Conrad (ohne Vortrag)
- Malte Dehling
- Nicolai Deuschle
- David Ellenberger
- Matthias Garbs
- Robert Hesse
- Benjamin Heuer
- Jan Henrik Hofmann
- Martin Holzke
- Carolin Homann
- Corinna Krüger
- Michael Mathe
- Simon Naarmann
- Vlada Pototskaia (ohne Vortrag)
- Thomas Schick (ohne Vortrag)
- Johannes Steiner