Research seminar Applied and Computational Topology
This seminar will normally take place on Thursdays 10:15–12:00 in room 02.12.020.
For questions contact Magnus Botnan
botnan@ma.tum.de
List of upcoming seminars
- Tuesday 15/05/18, 14:15, room 02.06.011.
- Konstantin Mischaikow (Rutgers University): Solving x’=?.
With the advent of every improving information technologies, science and engineering is being being evermore guided by data-driven models and large-scale computations. In this setting, one often is forced to work with models for which the nonlinearities are not derived from first principles and quantitative values for parameters are not known. With this in mind, I will describe an alternative approach formulated in the language of combinatorics and algebraic topology that is inherently multiscale, amenable to mathematically rigorous results based on discrete descriptions of dynamics, computable, and capable of recovering robust dynamic structures. To keep the talk grounded, I will discuss the ideas in the context of modeling of gene regulatory networks.
Past seminars
- Friday 27/04/18, 13:05, room 02.06.011.
- Magnus Botnan (TUM): Decomposition of persistence modules: A fast approach
Let P be a poset, and let vec denote the category of finite dimensional vector spaces over a field k. First I will show that any functor F: P->vec decomposes as a direct sum of indecomposables (with local endomorphism ring). Then I will apply this result in the specific setting of P = R, in order to to provide a new, simple, proof that any functor F: R->Vec decomposes as a direct sum of interval modules (== thin modules). This is joint work with Bill Crawley-Boevey.
- Friday 20/04/18, 10:15, room 02.0X.0XX.
- Nina Otter (Oxford University): Magnitude meets persistence. Homology theories for filtered simplicial sets
The Euler characteristic is an invariant of a topological space that in a precise sense captures its canonical notion of size, akin to the cardinality of a set. The Euler characteristic is closely related to the homology of a space, as it can be expressed as the alternating sum of its betti numbers, whenever the sum is well-defined. Thus, one says that homology categorifies the Euler characteristic. In his work on the generalisation of cardinality-like invariants, Leinster introduced the magnitude of a metric space, a real number that gives the “effective number of points” of the space. Recently, Leinster and Shulman introduced a homology theory for metric spaces, called magnitude homology, which categorifies the magnitude of a space.
In their paper Leinster and Shulman list a series of open questions, two of which are as follows:
- Magnitude homology only “notices” whether the triangle inequality is a strict equality or not. Is there a “blurred” version that notices “approximate equalities”?
- Almost everyone who encounters both magnitude homology and persistent homology feels that there should be some relationship between them. What is it?
In this talk I will introduce magnitude and magnitude homology, give an answer to these questions and show that they are intertwined: it is the blurred version of magnitude homology that is related to persistent homology. Leinster and Shulman's paper can be found at
https://arxiv.org/abs/1711.00802.
- Thursday 29/03/18, 11:00, room 02.06.011.
- Sara Kalisnik (MPI Leipzig): The Higher-Dimensional Skeletonization Problem
Real data is often given as a point cloud, i.e. a finite set of points with pairwise distances between them. An important problem is to detect the topological shape of data --- for example, to approximate a point cloud by a low-dimensional non-linear subspace such as an embedded graph or a simplicial complex. Classical clustering methods and principal component analysis work well when given data points split into well-separated clusters or lie near linear subspaces of a Euclidean space. Methods from topological data analysis in general metric spaces detect more complicated patterns such as holes and voids that persist for a long time in a 1-parameter family of shapes associated to a cloud. These features can be visualized in the form of a 1-dimensional homologically persistent skeleton, which optimally extends a minimal spanning tree of a point cloud to a graph with cycles. We generalize this skeleton to higher dimensions and prove its optimality among all complexes that preserve topological features of data at any scale.
- Thursday 15/02/18, 14:15, room 02.06.011.
- Greg Henselman (Princeton University): The Matroid of Barcodes: Combinatorial Foundations in TDA
Topological data analysis (TDA) is a robust field of mathematical data science specializing in complex, noisy, and high-dimensional data. While the elements of modern TDA have existed since the mid-1980’s, applications over the past decade have seen a dramatic increase in systems analysis, engineering, medicine, and the sciences. Two of the primary challenges in this field regard modeling and computation: what do topological features mean, and are they computable? While these questions remain open for some of the simplest structures considered in TDA — homological persistence modules and their indecomposable submodules — in the past two decades researchers have made great progress in algorithms, modeling, and mathematical foundations through diverse connections with other fields of mathematics. This talk will give a first perspective on the idea of matroid theory as a framework for unifying and relating some of these seemingly disparate connections (e.g. with quiver theory, classification, and algebraic stability), and some questions that the fields of matroid theory and TDA may mutually pose to one another. No expertise in homological persistence or general matroid theory will be assumed, though prior exposure to the definition of a matroid and/or persistence module may be helpful.
- Friday 15/12/17, 10:15, room 02.06.011.
- Abishek Rathod (TU Munich):
We consider the approximability of maximization and minimization variants of the Morse matching problem, posed as open problems by Joswig and Pfetsch. We establish hardness results for Max-Morse matching and Min-Morse matching. In particular, we show that, for a simplicial complex with n simplices and dimension d ≥ 3, it is NP-hard to approximate Min-Morse matching within a factor of O(n1−ε), for any ε > 0. Moreover, using an L-reduction from Degree 3 Max-Acyclic Subgraph to Max-Morse matching, we show that it is both NP-hard and UGC-hard to approximate Max-Morse matching for simplicial complexes of dimension d ≥ 2 within certain explicit constant factors.
- Friday 30/11/17, 10:15, room 02.06.011.
- Magnus Bakke Botnan (TUM): Computational Complexity of the Interleaving Distance
- Friday 23/11/17, 10:15, room 02.06.011.
- Benedikt Fluhr (TUM): From Reeb graphs to merge trees and back to contour trees (part 2)
We start with a concrete version of the interleaving distance of Reeb
graphs. Then we connect this approach to the interleaving distance of
merge trees. Afterwards we discuss Reeb graphs and merge trees coming
from Morse functions in more detail. Then we talk about some ideas for
using branch decomposition trees to "approximate" the interleaving
distance of merge trees. Afterwards we discuss how this might help with
contour trees and some problems with that.
- Thursday 16/11/17, 13:00, room 02.12.020.
- Benedikt Fluhr (TUM): From Reeb graphs to merge trees and back to contour trees
We start with a concrete version of the interleaving distance of Reeb
graphs. Then we connect this approach to the interleaving distance of
merge trees. Afterwards we discuss Reeb graphs and merge trees coming
from Morse functions in more detail. Then we talk about some ideas for
using branch decomposition trees to "approximate" the interleaving
distance of merge trees. Afterwards we discuss how this might help with
contour trees and some problems with that.
- Thursday 27/07/17, 10:15, room 02.12.020.
- Morten Brun (University of Bergen): Filtered Covers
I will introduce the concept of filtered covers. I show that the persistent homology of a bounded metric space obtained from the Cech complex is the persistent homology of what I call the filtered nerve of the filtered Cech cover. Given a parameter δ with 0<δ≤1 I introduce the concept of a δ-filtered cover and show that its filtered nerve is interleaved with the Cech complex. Finally, I introduce a particular δ-filtered cover, the divisive cover. The special feature of the divisive cover is that it is constructed top-down. If we disregard fine scale structure and X is a finite subspace of euclidean space, then we obtain a filtered simplicial complex whose size is bounded by an upper bound independent of the cardinality of X. The time needed to compute this filtered simplicial complex depends linearly on the cardinality of X.
- Thursday 06/07/17, 11:00, room 02.12.020.
- Ulrich Bauer (TU Munich): The Reeb graph edit distance is universal
We consider Reeb graphs in a general topological setting, and the construction of distances between Reeb graphs that are stable, meaning that similar functions in the supremum norm have similar Reeb graphs. We define a graph edit distance and show that it is universal, providing an upper bound to any other stable distance.
- Monday 19/06/17, room 02.12.020.
- Magnus Bakke Botnan (TU Munich): A brief summary of my research
- Thursday 8/06/17, room 02.12.020.
- Abishek Rathod (TU Munich): An output sensitive algorithm for computing persistent homology using Discrete Morse theory (part 2)
- Thursday 1/06/17, room 02.12.020.
- Abishek Rathod (TU Munich): An output sensitive algorithm for computing persistent homology using Discrete Morse theory
- Tuesday 23/5/17, room 02.06.011, 15:30.
- Mathieu Carrière (INRIA, France): A theoretical framework for the analysis of Mapper
Mapper is probably the most widely used TDA (Topological Data Analysis) tool in the applied sciences and industry. Its main application is in exploratory analysis, where it provides novel data representations that allow for a higher-level understanding of the geometric structures underlying the data. The output of Mapper takes the form of a graph, whose vertices represent homogeneous subpopulations of the data, and whose edges represent certain types of proximity relations. Nevertheless, the inherent instability of the output and the difficult parameter tuning make the method rather difficult to use in practice. This talk will focus on the study of the structural properties of the graphs produced by Mapper, together with their partial stability properties, with a view towards the design of new tools to help users set up the parameters and interpret the outputs.
- Thursday 18/5/17, room 02.06.011.
- Florian Pausinger (TU Munich): Persistent Betti Numbers of Random Simplicial Complexes
Some recent results on persistent Betti numbers.
- Thursday 9/2/17, room 02.12.020.
- Benjamin Busam (TUM/Framos): Vision-based approaches for robust real-time tracking via energy minimization
- Tuesday 7/2/17, room 02.06.011, 15:30.
- Frederic Chazal (INRIA, France): Persistent homology for data: stability and statistical properties
Computational topology has recently seen an important development toward data analysis, giving birth to Topological Data Analysis. Persistent homology appears as a fundamental tool in this field. It is usually computed from filtrations built on top of data sets sampled from some unknown (metric) space, providing "topological signatures" revealing the structure of the underlying space. When the size of the sample is large, direct computation of persistent homology often suffers two issues. First, it becomes prohibitive due to the combinatorial size of the considered filtrations and, second, it appears to be very sensitive to noise and outliers. The goal of the talk is twofold. First, we will briefly introduce the notion of persistent homology and show how it can be used to infer relevant topological information from metric data through stability properties. Second, we will present a method to overcome the above mentioned computational and noise issues by computing persistent diagrams from several subsamples and combining them in order to efficiently infer robust and relevant topological information.
- Friday 3/2/17, room 02.06.011.
- Magnus Botnan: Generalized interleaving on posets
The theory of interleavings lies at the very core of the theoretical foundations of persistent homology. With rising interest in more generalized indexing categories (zigzag, commutative ladders, circle valued maps, etc. ) comes the desire to extend this theory. In the first part of the talk I will survey interleavings in ordinary persistent homology, and, in particular, the celebrated algebraic stability theorem. Then I will report on recent work with Michael Lesnick (Princeton U.) where we extend this to zigzag persistence. Lastly I will show how the notion of interleavings can be generalized to general posets by means of cosheaves. The last part is joint work with Justin Curry (Duke) and Elizabeth Munch (U Albany).
- Monday 9/1/17, 4pm, room 02.12.020.
- Ulrich Bauer: Tenure track status talk
I'll give a survey about my recent research at TUM.
- Thursday 15/12/16, room 02.12.020.
- Magnus Botnan: Interval Decomposition of Infinite Zigzag Persistence Modules
I'll give an elementary introduction to the decomposition of representations of (infinite) linear quivers.
- Thursday 08/12/16, room 02.12.020.
- Frank Himstedt (TUM): An introduction to the representation theory of Lie-type groups
- Thursday 17/11/16, room 02.12.020.
- Mickael Buchet (Tohoku University): Parameter-free data denoising and persistence diagram interpretation
During this talk I will look into two different problems related to data analysis. The first one is the denoising of the data. Usual methods rely either on a precise knowledge of the noise model or several choices of parameter. I will present a new parameter free methods to denoise data assuming some minimal assumption. On a second, I will look into a difficult problem from the user point of view when working with persistence diagram. What does the persistence diagram means in the data? I will present new work on how to build good representatives for one-dimensional homology features and associate them with barcodes.
- Thursday 10/11/16, room 02.12.020.
- Konstantinos Panagiotou (LMU): On the Connectivity Threshold of Achlioptas Processes
- Thursday 3/11/16, room 02.12.020.
- Abishek Rathod: Approximation Algorithms for Morse Matching
- Thursday 27/10/16, SFB room.
- Ulrich Bauer: Implementing Vietoris–Rips cohomology
- Friday 07/10/16.
- Ulrich Bauer: Persistent connections
I will outline a novel computational method for persistent homology of finite metric spaces, which outperforms the previous state of the art by an order of magnitude. After that, I will survey several surprising connections and applications of persistent homology to various areas relevant to our collaborative research center.
Summer 2016
- Tuesday 05/07/16, SFB room.
- Claudia Landi (University of Modena and Reggio Emilia): Reducing Complexes in Multidimensional Persistence
An algorithm is presented that constructs an acyclic partial matching on the cells of a simplicial complex from a vector-valued function defined on the vertices. The resulting acyclic partial matching is used to construct a reduced complex with the same multidimensional persistent homology as the original complex filtered by sublevel sets of the function. Numerical tests on triangle meshes show that the achieved rate of reduction is substantial.
- Tuesday 21/06/16, SFB room.
- Fernando Galaz-Garcia (Karlsruhe Institute of Technology): Alexandrov spaces and topological data analysis
Alexandrov spaces (with curvature bounded below) are a synthetic generalization of Riemannian manifolds with sectional curvature bounded below. In this talk I will discuss the geometric and topological properties of these metric spaces and how they arise in the context of topological data analysis.
- Tuesday 31/05/16, 10:15, SFB room.
- José Carlos Gómez Larrañaga (CIMAT/ TU Munich): Simply connected 2-stratifolds.
2-stratifolds are the simplest 2-complexes which can be good models for topological
data analysis. A 2-stratifold X contains a collection X1 of finitely many simple closed
curves such that X –X1 is a 2-manifold and a neighborhood of each component C of X1 consists
of sheets intersecting in C. In contrast to 2-manifolds there is no known classification of
2-stratifolds in terms of algebraic invariants. In this talk we will describe 2-stratifolds and their
graphs and present efficient algorithms that detect whether certain 2-stratifolds have trivial
first homology, whether they are simply connected, or whether they have the same homotopy
type as a 2-sphere.
This is joint work with F. González-Acuña, UNAM, Mexico and W. Heil, Florida State University.
- Wednesday 18/05/16, 12:45-14:00, SFB room.
- Johan Steen (NTNU / U Stuttgart): Auslander–Reiten Theory
An introduction to Auslander-Reiten Theory. This theory deals with the problem of understanding all indecomposable representations of a quiver with relations (or equivalently the indecomposable modules of certain algebras), as well as the "minimal" morphisms. In general, writing down all indecomposable modules turns out to be an impossible task, but one of the things AR-theory provides us is a way to find new indecomposable modules from old ones. In particular, AR-theory provides theoretical justification for topological data analysis.
- Tuesday 10/05/16, 10:15–11:15, SFB room.
- Florian Pausinger (TU Munich): Persistent Betti Numbers of Random Simplicial Complexes
Some recent results on persistent Betti numbers.
- Tuesday 03/05/16, 10:15–11:15, SFB room.
- Ulrich Bauer (TU Munich): Morse Theory of Geometric Filtrations
A summary of
http://arxiv.org/abs/1312.1231
- Friday 29/04/16, 14:15–15:15, SFB room.
- Andreas Sühling (U Münster): The Geodesic Flow on Hadamard Spaces and CAT(0) Spaces
We examine the flow space of proper CAT(0)-spaces and warped products of Riemannian manifolds and intrinsic metric spaces. Then we construct some embeddings of the flow space of non-constant generalized geodesics on Hadamard manifolds and proper CAT(0)-spaces using warped products.