Schedule for: 18w5140 - Multiparameter Persistent Homology

It is widely known that persistent homology in more than one parameter is significantly more "complicated" than in the single-parameter setting. In this talk I will discuss in what sense it is more complicated from the point of view of representation theory, and from the point of view of algorithms. I will also give examples of how multi-parameter persistence modules naturally appear in applications.

In this talk I will focus on a specific class of 2-parameter persistence modules whose internal morphisms satisfy a certain exactness property. The main result I will present states that such modules decompose into direct sums of constant thin summands whose supports are planar quadrants or bands. I will also mention some of the implications of this result, e.g. on the stability theory for zigzag modules and interlevel-sets persistence.

I will discuss how topological summaries can be used to model various shapes as well as other high-dimensional data. I will talk about geometric and statistical properties of the space of summaries and how these summaries are the result of various filtrations. I will then discuss why multi-parameter persistence would be a very nice tool for these problems. The first half of the talk will be a review and I will focus on some of my research in the second half.

The usual definition of minimal primary decomposition in commutative algebra grants a little too much leeway. Making minimality work for real multiparameter persistence modules -- that is, multigraded modules over rings of polynomials with real exponents -- requires tighter control over what algebraists call socles and computational topologists call deaths. Functorial definitions yield finiteness statements for primary decompositions of reasonable persistence modules. In contrast, for irreducible decompositions finiteness is impossible with continuous parameters; but nonetheless minimality can be characterized by density with respect to certain topologies arising in the context of partially ordered vector spaces.

Theoretical methods in persistent homology have traditionally considered one of two viewpoints: R-indexed/sub-level set persistence, or zig-zag/level-set persistence. Even in the case of a single variable real-valued function, there is still much to be understood by combining these two forms of persistence together. This version of multiparameter persistence naturally lends itself to analysis of families of functions on smooth manifolds, as well as generalized versions of Reeb graphs and Merge trees. In this talk, I will show what we hope to learn by mixing these two together through a variety of examples, ranging from manifolds to Arnold's Calculus of Snakes. This ongoing work is joint with Peter Bubenik.

A systematic review shows that there is a link between craniofacial morphology and obstructive sleep apnea syndrome in pediatric patients. To evaluate this association, a clinical study has been conducted at the University of Alberta. In this talk, we discuss interim analyses in classification of craniofacial shapes using two methods. First, for persistence homology, we estimate curvature at a neighborhood of each point in 3d point-cloud facial image. We propose a nonparametric method to compare 3d point-cloud datasets with pseudo bi-filtration of scale and curvature parameters. Second, we apply convolutional neural network to 2d facial image data. To overcome small sample sizes, we adapt transfer learning which learns new skills faster by using current related skills. We compare the results from both methods. This is joint work with Matthew Pietrosanu, Mathieu Chalifour, and Milad Kiaee.

Peter Bubenik and Jonathan Scott, in 2012, made the perspicuous suggestion that any functor, from a suitable source category into any target category, could be regarded as a "generalised persistence module" (GPM), and that categories of GPM carried natural distance functions called interleaving metrics. I will discuss several examples and constructions on GPM. These include Reeb graphs, merge trees, dynamical systems, Morse functions. I will also discuss a recently joint project, led by Anastasios Stefanou and Liz Munch, which extends the interleaving distance from GPM categories to, more generally, categories with a flow.

Discovering a new drug costs more than a billion dollars and takes ten years or more. So researchers are always looking for new ways to use computers to find more promising candidate drugs. We present a promising new system that applies the two-parameter persistent homology to the complex task of finding good drug candidates, by finding similarities in the 3D shapes of the molecules.

Computation of the interleaving distance between persistence modules is a central task in topological data analysis. For $1$-D persistence modules, thanks to the isometry theorem, this can be done by computing the bottleneck distance with known efficient algorithms. The question is open for most $n$-D persistence modules, $n>1$, because of the well recognized complications of the indecomposables. Here, we consider a reasonably complicated class called {\em $2$-D interval decomposable} modules whose indecomposables may have a description of non-constant complexity. We present a polynomial time algorithm to compute the interleaving distance between two such indecomposables. This leads to a polynomial time algorithm for computing the bottleneck distance between two $2$-D interval decomposable modules, which bounds their interleaving distance from above. We give another algorithm to compute a new distance called {\em dimension distance} that bounds it from below.

In joint work with Ulrich Bauer, Magnus Botnan and Steffen Oppermann, we construct equivalences relating certain subcategories of abelian categories. (These arise as components in so-called torsion and cotorsion pairs.) I will explain how this construction works, and with this as a fairly general starting point, we will see how this can be specialized to 2-parameter clustering. For the last part, I will give examples to show that the finiteness of representation type is sensitive to the orientation of the underlying quivers.

In persistence theory and practice, measuring distances between modules is central. The Wasserstein distances are the standard family of $L^p$ distances (with $1 \leq p \leq \infty$) for persistence modules. We give an algebraic formulation of these distances. For $p=1$ it generalizes to abelian categories and for arbitrary $p$ it generalizes to Krull-Schmidt categories. These distances may be useful for the computation of distance between generalized persistence modules. This is joint work with Peter Bubenik and Donald Stanley.

In Carlsson and Zomorodian's foundational paper on multi parameter persistence, the nonexistence of a “complete discrete invariant” for such modules is shown via a specific example. It is a 2-parameter module with two generators in bidegree (0,0) and four relations in degrees (0,3), (1,2), (2,1), and (3,0). In this talk I will discuss this example in greater detail with a particular focus on completely describing the isomorphism classes of such modules. This will lead me to make some wild claims that I am currently investigating.

We will discuss the format and topics of the breakout sessions.

I will discuss the efficient computation of the Vietoris–Rips persistence barcode for a finite metric space. The implementation in the C++ code „Ripser“ focuses on memory and time efficiency, outperforming previous software on typical benchmark examples both in terms of time and memory. The improved computational efficiency is based on a close connection between persistent homology and discrete Morse theory, together with novel algorithmic design principles, avoiding the explicit construction of the filtration boundary matrix.

Topological Data Analysis is a relatively new paradigm in data-science that models datasets as point-clouds sampled from a shape embedded in an Euclidean space. The inference problem is to estimate the essential topological features of the underlying shape from a point-cloud sampled from it. This is done through a technique called persistent homology which is a mathematical formalism based on algebraic topology. A necessary step in the persistent homology pipeline is the reduction a so-called boundary matrix, which is a process reminiscent to Gaussian elimination. In this talk, I present a number of structural dependencies in boundary matrices and use them to design a novel parallel algorithm for their reduction, which is especially fit for GPUs. Simulations on synthetic examples show that the computational burden can be conducted in a small fraction of the number of iterations needed by traditional methods. For example, numerical experiments show that for a boundary matrix with 10^4 columns, the reduction completed to within 1% in about ten iterations as opposed to nearly approximately eight thousand iterations for traditional methods.

In this talk I'll review some of the basic concepts of sheaf theory as it is relevant to persistence in one or more parameters. One of the themes that will be emphasized is how the same formalism can be used and simply by changing the underlying topology many different constructs in TDA can be obtained: multi-filtered homology (Alexandrov/gamma topology), level set persistence and Reeb spaces (Euclidean topology), the persistent homology transform and vineyards (mixture of Alexandrov and Euclidean topologies). Additionally, I'll describe how sheaves can be used to organize various counting problems associated to persistence.

The classical Kunneth formula in homological algebra provides a link between the homology of a product space and that of its factors. We will show in this talk a collection of similar results for persistent homology. That is, we show how the persistent homology of a filtered product space --- different product filtrations lead to different formulae --- can be recovered from that of its filtered factors.

A fundamental tool in topological data analysis is persistent homology, which allows extraction of information from complex datasets in a robust way. Persistent homology assigns a module over a principal ideal domain to a one-parameter family of spaces obtained from the data. In applications data often depend on several parameters, and in this case one is interested in studying the persistent homology of a multiparameter family of spaces associated to the data. While the theory of persistent homology for one-parameter families is well-understood, the situation for multiparameter families is more delicate. Following Carlsson and Zomorodian we recast the problem in the setting of multigraded algebra, and we propose multigraded Hilbert series, multigraded associated primes and local cohomology as invariants for studying multiparameter persistent homology. Multigraded associated primes provide a stratification of the region where a multigraded module does not vanish, while multigraded Hilbert series and local cohomology give a measure of the size of components of the module supported on different strata. These invariants generalize in a suitable sense the invariant for the one-parameter case.

Our primary motivation for persistent homology is in its applications to shape similarity measures. Multidimensional or multiparameter persistence comes into play in that context when two objects are to be simultaneously compared according to several features. The ideas go back to early 1900s when Pareto’s optimal points of multiple functions were studied with applications to economy on mind. In our previous work, we developed an algorithm that produces an acyclic partial matching (A, B, C) on the cells of a given simplicial complex, in the way that it is compatible with a vector-valued function given on its vertices. This implies the construction can be used to build a reduced filtered complex with the same multidimensional persistent homology as of the original one filtered by the sublevel sets of the function. Until now, any simplex added to C by our algorithm has been defined as critical. It was legitimate to do so, because an application- driven extension of Forman’s discrete Morse theory to multi-parameter functions has not been carried out yet. In particular, no definition of a general combinatorial critical cell has been given in this context. We now propose new definitions of a multidimensional discrete Morse function (for short, mdm function), of its gradient field, its regular and critical cells. We next show that the function f used as input for our algorithm gives rise to an mdm function g with the same order of sublevel sets and the same partial matching as the one produced by our algorithm. This is a joint work with Madjid Allili, Claudia Landi, and Filippo Masoni.

Kernels for one-parameter persistent homology have been established to connect persistent homology with machine learning techniques, We contribute a kernel construction for multiparameter persistence by integrating a one-parameter kernel along straight lines. We prove a stability result for our construction and show that our kernel can be approximated in polynomial time to any absolute precision.

The interleaving distance for persistence modules, originally defined by Chazal et al., is arguably the most powerful, generalizable mathematical idea to come out of TDA in the last decade. The categorification of persistence modules and the related interleaving distance provided a plug-and-play system to create new metrics for functors with a poset category domain. In this talk, we will generalize this work even further to give a definition of the interleaving distance for a category with a flow; that is, a category $C$ with a functor $S:\mathbb{R}_{\geq0} \to \mathrm{End}(C)$ which satisfies certain compatibility conditions. From this framework, we can see that many commonly used metrics, such as the Hausdorff distance on sets and the $\ell_\infty$ distance on $\R^n$ are all examples of interleaving distances. The categorical viewpoint gives an immediate construction for a host of stability theorems. Further, a new construction on elements of a category with a flow called a hom-tree provides a lower bound for the interleaving distance. This work is joint with Anastasios Stefanou and Vin de Silva.

From an algebraic perspective, generalized persistence modules are just finitely-generated modules for the incidence algebra of a finite partially- ordered set. With this in mind, we suggest a template for a representation- theoretic analogue of the isometry theorem for R-indexed persistence modues. We then prove such a theorem for a large class of posets, including many of wild rep- resentation type. This theorem shows that for such posets, the interleaving metric of Bubenik, de Silva and Scott can be realized as a bottleneck metric which incorporates some algebraic information. We then show that this dis- crete viewpoint approximates the classical one for one-dimensional persistence modules with arbitrary precision. Specifically, if two persistence modules come from filtrations, we can associate to them a directed set of incidence algebras over which they can be compared. We may then recover their (classical) inter- leaving distance uniformly by taking limits.

We describe homotopy and homology based on Cech closure spaces. In particular, we show how this category gives a natural framework for defining homotopy theory directly on point clouds, as opposed to thickening the point clouds into nicer topological spaces, and that it also gives new insight into classical invariants in TDA.

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.

Completeness, separability, and characterization of the precompact subsets are important for doing probability and statistics on a metric space, using tools like Prokhorov's Theorem. Recently in applied topology, a common type of (pseudo/quasi)metric space is an interleaving distance on a category. We relate the metric limit of a Cauchy sequence in such a space to the categorical limit of a corresponding diagram. Using this, we show that many familiar examples in the applied topology literature are metrically complete. We also study separability and precompactness for some familiar examples. Finally, we show how this new understanding can be used to prove results about probability and statistics on these spaces.