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 Abhishek Rathod
rathod@ma.tum.de
List of upcoming seminars
Past seminars
- Wednesday 10/04/19, 10:00, room 02.06.011.
- Håvard Bakke Bjerkevik (Norwegian University of Science and Technology) Multiparameter interleaving distance is NP-hard
The interleaving distance is arguably the most important distance used
for comparing persistence modules. In one-parameter persistence, there
exist efficient algorithms for computing the interleaving distance. In
the multiparameter case, however, one has suspected for a while that the
problem is NP-hard, in part due to the lack of a nice decomposition
theorem for these modules. In a joint work with Magnus Botnan and
Michael Kerber, we show that deciding whether two two-parameter modules
are 1-interleaved is NP-complete even if we assume that the modules
decompose into summands of a particularly nice form. I will present the
proof along with some related hardness results proved by similar methods.
- Wednesday 03/04/19, 10:00, room 02.06.011.
- Bernhard Brehm TBD
- Tuesday 02/04/19, 14:00, room 02.06.011.
- Erika Berenice Roldan Roa (Ohio State University) Evolution of the homology and related geometric properties of the Eden Growth Model
In this talk, we study the persistent homology and related geometric properties of the evolution in time of a discrete-time stochastic process defined on the 2-dimensional regular square lattice. This process corresponds to a cell growth model called the Eden Growth Model (EGM). It can be described as follows: start with the cell square of the 2-dimensional regular square lattice of the plane that contains the origin; then make the cell structure grow by adding one cell at each time uniformly random to the perimeter. We give a characterization of the possible change in the rank of the first homology group of this process (the "number of holes"). Based on this result we have designed and implemented a new algorithm that computes the persistent homology associated to this stochastic process and that also keeps track of geometric features related to the homology. Also, we present obtained results of computational experiments performed with this algorithm, and we establish conjectures about the asymptotic behavior of the homology and other related geometric random variables. The EGM can be seen as a First Passage Percolation model after a proper time-scaling. This is the first time that tools and techniques from stochastic topology and topological data analysis are used to measure the evolution of the topology of the EGM and in general in FPP models.
- Friday 22/03/19, 14:00, room 02.06.011.
- Barbara Giunti (Università di Pavia) Filtered Chain Complexes: Decomposition and Algorithm
Persistent homology has proven to be a useful tool to extract information from
data sets. Homology, however, is a drastic simplification and in certain situations
might remove too much information. This prompts us to study filtered chain
complexes. We prove a structure theorem for filtered chain complexes and list
all possible indecomposables. We call these indecomposables interval spheres and
classify them into three types. Two types correspond respectively to finite and
infinite interval modules, while the third type is unseen by homology. The structure
theorem states that any filtered chain complex can be written as the unique sum of
interval spheres, up to isomorphism and permutation.
The proof is based on a hierarchy of full subcategories of the category of filtered
chain complexes. Such hierarchy suggests an algorithm for decomposing filtered
chain complexes, which also retrieves the usual persistent barcodes.
- Friday 22/03/19, 10:00, room 02.06.011.
- Fabian Roll (TUM) Nerve Theorem for Closed Balls. Part II
It is well known that the nerve of a good and open cover U of a space X is homotopy equivalent to X. We prove the analogous statement in the case that U is a finite collection of closed balls in R^d.
- Friday 15/02/19, 14:00, room 02.06.011.
- Andrew Newman (TU Berlin) The evolution of random simplicial complexes
In 2003, Linial and Meshulam introduced their model of random
simplicial complexes generalizing the Erdős--Rényi random graph model to
higher dimensions. In this talk I will discuss the evolution of the
homology groups of random simplicial complexes in the Linial--Meshulam
model. Along the way, we will see how the story in d ≥ 2 dimensions
parallels the story in the random graph setting, but with some
unexpected differences.
- Friday 11/01/19, 10:00, room 02.06.011.
- Fabian Roll (TUM) Nerve Theorem for Closed Balls. Part I
It is well known that the nerve of a good and open cover U of a space X is homotopy equivalent to X. We prove the analogous statement in the case that U is a finite collection of closed balls in R^d.
- Friday 21/12/18, 10:00, room 02.06.011.
- Abhishek Rathod (TUM) Hardness of Approximation for Morse Matching
Discrete Morse theory has emerged as a powerful tool for a wide range of
problems, including the computation of (persistent) homology. In this
context, discrete Morse theory is used to reduce the problem of
computing a topological invariant of an input simplicial complex to
computing the same topological invariant of a (significantly smaller)
collapsed cell or chain complex. Consequently, devising methods for
obtaining gradient vector fields on complexes to reduce the size of the
problem instance has become an emerging theme over the last decade.
While computing the optimal gradient vector field on a simplicial
complex is NP-hard, several heuristics have been observed to compute
near-optimal gradient vector fields on a wide variety of datasets.
Understanding the theoretical limits of these strategies is therefore a
fundamental problem in computational topology. In this paper, we
consider the approximability of maximization and minimization variants
of the Morse matching problem. We establish hardness results for
Max-Morse matching and Min-Morse matching, settling an open problem
posed by Joswig and Pfetsch. In particular, we show that, for a
simplicial complex of dimension d ≥ 3 with n simplices, it is NP-hard to
approximate Min-Morse matching within a factor of O(n^(1-ε)), for any
ε>0. Moreover, we establish hardness of approximation results for
Max-Morse matching for simplicial complexes of dimension d ≥ 2, using an
L-reduction from Degree 3 Max-Acyclic Subgraph to Max-Morse matching.
- Friday 07/12/18, 10:00, room 02.06.011.
- Fabian Lenzen (TUM) Decomposition of Persistence Modules
A continuation of the talk given on 30/11/18.
- Friday 30/11/18, 10:00, room 02.06.011.
- Fabian Lenzen (TUM) Decomposition of Persistence Modules
A pointwise finite dimensional persistence module assigns to each integer t a finite dimensional vector space V(t) and to each s≤t a map V(s≤t): V(s)→V(t) of vector spaces. It from the classification of finitely generated modules over PIDs that every such V can be written as a direct sum of so-called interval modules k(I) for I some interval, which assign the one-dimensional space to every t∈I and the zero-space to every t∉I.
Things get more involved if we replace "integer" by "real number". As proven by W. Crawley-Boevey, the statement still holds true, and the goal of the talk is to get the idea behind his proof.
- Friday 23/11/18, 10:00, room 02.06.011.
- Maximilian Schmahl (TUM) Computation and Clearing
- Friday 16/11/18, 10:00, room 02.06.011.
- Erik Rybakken (NTNU) Reconstructing metric graphs from trajectories
- Friday 26/10/18, 10:00, room 02.06.011.
- Maximilian Schmahl (TUM) Computing Image Persistent (Co-)Homology
Given a filtration and a subfiltration of simplicial complexes, the
inclusion of the subfiltration into the filtration induces a morphism
between their persistent homologies. We discuss how to efficiently
compute the barcode of the image of this morphism. While doing so, we
establish correspondence results between the images for persistent
absolute and relative (co)homology and investigate certain endofunctors
on the category of persistence modules as technical tools.
- Friday 05/10/18, 10:00, room 02.06.011.
- Michael Haberl (TUM) Object Pose Estimation with PointNet
What does it take for a computer to detect the location and orientation of objects? The aim of this thesis is to try to answer this question using neural networks to evaluate point clouds of the objects.
- Wednesday 30/05/18, 10:00, room 02.06.011.
- Magdalena Reich (TUM): Audio fingerprinting: the mathematics of Shazam
- 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.
- 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.
- Tuesday 23/04/18, 14:!5, room 02.06.011.
- Erik Rybakken (NTNU Norway): Decoding of neural data using cohomological learning
We introduce a novel data-driven approach to discover and decode features in the neural code coming from large population neural recordings with minimal assumptions, using cohomological learning. We apply our approach to neural recordings of mice moving freely in a box, where we find a circular feature. We then observe that the decoded value corresponds well to the head direction of the mouse. Thus we capture head direction cells and decode the head direction from the neural population activity without having to process the behaviour of the mouse.
- Friday 20/04/18, 10:15, room 03.04.011.
- 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.