The Minisymposium on Computational Topology will consist of two mini-workshops, entitled Metric Geometry and Topology, and Statistical and Stochastic Computational Topology. This workshop accompanies Computational Geometry Week 2018 in Budapest, Hungary, 2018.
Tuesday, June 12, 9:00 - 10:30 and 11:00 - 12:30
Wednesday, June 13, 15:30 - 16:45 and 17:15 - 18:30
Omer Bobrowski, Homological percolation - the formation of large cycles
In probability theory and statistical physics, the study of percolation investigates the formation of large connected components in various random structures. In this talk, we will discuss a higher dimensional analog of this phenomenon, where large k-cycles are formed in random simplicial complexes. Suppose that we are given a random dataset, from which we try to extract some “significant” topological features. One common practice is to create a filtration (e.g. Cech, Rips, alpha), compute its persistent homology and examine cycles at various scales. It is usually assumed that cycles in persistent homology split into two: “large” ones that are considered significant, and “small” ones that are considered as noise. In this work we are trying to provide some probabilistic analysis for the large cycles. In particular, the question we ask is: what can we say about the birth time of large cycles in random samples? We show that there is critical threshold value below which large cycles never appear and above which they appear with high probability. In addition, there is an order in which large cycles in different homology degrees appear. We will also discuss how these new results on large cycles compare to our knowledge about small cycles.
This is joint work with Primoz Skraba and Shmuel Weinberger.
Tamal Dey, Nerves can only kill, also serially!
We show that the one-dimensional homology of the nerve complex N(U) of a path-connected cover U of a domain X cannot be richer than that of the domain X itself. Intuitively, this result means that H_1-homology classes can only be be killed under a natural map from X to the nerve complex N(U). Equipping X with a pseudometric d, we further refine this result and characterize the classes of H_1(X) that may survive in the nerve complex using the notion of size of the covering elements in U. These fundamental results about nerve complexes then lead to an analysis of the H_1-homology of Reeb spaces, mappers and multiscale mappers.
Joint work with Facundo Memoli and Yusu Wang.
Sara Kalisnik, Learning algebraic varieties from samples
I will discuss how to determine a real algebraic variety from a fixed finite sample of points and what to do with that information. For example, from the equations defining a variety one can learn the degree and the dimension of the variety. One can also construct ellipsoid complexes which, based on the experiments, strengthen the topological signal for persistent homology. All the algorithms needed are made available in a Julia package.
Joint work with Bernd Sturmfels, Paul Breiding, and Madeleine Weinstein.
Anthea Monod, Statistical Inference for Persistent Homology via Rank Functions
Persistent homology rank functions are invariant measures of "shape" first introduced to relate variation in topological information (as measured by cellular homology) with variation in data. Persistent homology barcodes and diagrams were since constructed to capture this same information, and have been used in many real data settings. In this work, we revisit the persistent homology rank function as a data analytic tool. In particular, we show that a reinterpretation of the rank function via the Möbius transform results in properties that are desirable for parametric statistical inference: a task which has been challenging thus far when using barcodes and diagrams. The theoretical implications of our work extend to the setting of multiparameter persistent homology, which is a direction of active research in the domain of applied algebraic topology. We demonstrate our method on a real data application of avian influenza exhibiting intra- and inter-subtype recombination via functional logistic regression to model the probability of observing one recombination type or the other, given the rank functions of genomic distances.
This is joint work with Gregory Henselman Petrusek.
Primoz Skraba, Random Structures, Persistence, and Stability
Overall the purpose of this talk is to discuss the problem of finding "good" cycle representatives in data. This is in general an ill-posed problem and most of the existing approaches have been based purely on geometric considerations. Here I will discuss a stochastic approach - given a random process, what can we say about the various structures that appear. The talk will introduce minimum spanning acycles or generalized trees and go over what is known about them in terms of limit theorems as well as more empirical approaches and how they relate to geometric problems.
Ziga Virk, Persistence of geodesic spaces
Given a locally contractible geodesic space, say a Riemannian manifold, we show how a critical value of the one-dimensional persistence corresponds to a closed geodesic. Using this result we can explain the surprising relationship between the Vietoris-Rips and Cech induced persistences. It also allows us to deduce several results about approximations by discrete samples, including an improved stability theorem. We then show how to utilize contractions and deformation contractions to extract geometric information from higher-dimensional persistence. For example, we can detect certain contractible geodesic loops by higher-dimensional persistence.
Yusu Wang, Gromov-Hausdorff and Interleaving Distances for Trees
The Gromov-Haudorff distance is a common way to measure the distortion between two metric spaces. Given two tree metric spaces (metric trees), it provides a natural distance for them. The merge tree is a simple yet meaningful (topological) summary of a scalar function defined on a domain. There are various ways to define the distance between merge trees, including the so-called interleaving distance between trees.
In this talk, I will present an interesting relationship between the Gromov-Hausdorff distance and the interleaving distance. I will then show that these distances are NP-hard to approximate within a certain constant factor. But I will also present a fix-parameter-tractable (FPT) algorithm to compute the interleaving distance. Due to the relation between Gromov-Hausdorff distance and interleaving distances, this also lead to a FPT approximate algorithm for the Gromov-Hausdorff distance between general metric trees.
The talk is based on joint work with P. Agarwal, K. Fox, A. Nath and A. Sidiroupolos, as well as based on joint work with E. Farahbakhsh Touli.
Mathijs Wintraecken, Triangulating stratified manifolds: a reach comparison theorem
We define the reach for submanifolds of Riemannian manifolds, in a way that is similar to the Euclidean case. Given a $d$-dimensional submanifold $\mathcal{S}$ of a smooth Riemannian manifold $\mathcal{M}$ and a point $p \in \mathcal{M}$ that is not too far from $ \mathcal{S} $ we want to give bounds on local feature size of $\exp_p^{-1}( \mathcal{S} )$. Here $\exp_p^{-1}$ is the inverse exponential map, a canonical map from the manifold to the tangent space. Bounds on the local feature size of $\exp_p^{-1}( \mathcal{S} )$ can be reduced to giving bounds on the reach of $\exp_p^{-1} (B(c,r))$, where $B(c,r)$ is a geodesic ball, or equivalently on $\exp_p^{-1}\circ \exp_c (B (c,r))$, where now $B(c,r)$ is a ball in the tangent space. To establish bounds on the reach of $\exp_p^{-1}\circ \exp_c (B (c,r))$, we use bounds on the metric and on its derivative in Riemann normal coordinates. This result is a first step towards answering the important question of how to triangulate stratified manifolds.
This is joint work with Jean-Daniel Boissonnat.
Lori Ziegelmeier, A complete characterization of the 1-dimensional intrinsic Cech persistence diagrams for metric graphs
Metric graphs are special types of metric spaces used to model and represent simple, ubiquitous, geometric relations in data such as biological networks, social networks, and road networks. We are interested in giving a qualitative description of metric graphs using topological summaries. In particular, we provide a complete characterization of the 1-dimensional intrinsic Cech persistence diagrams for metric graphs using persistent homology. Together with complementary results by Adamaszek et. al, which imply results on intrinsic Cech persistence diagrams in all dimensions for a single cycle, our results constitute important steps toward characterizing intrinsic Cech persistence diagrams for arbitrary metric graphs across all dimensions.