From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives

Methods of topological data analysis have been successfully applied in a wide range of fields to provide useful summaries of the structure of complex data sets in terms of topological descriptors, such as persistence diagrams. While there are many powerful techniques for computing topological descriptors, the inverse problem, i.e., recovering the input data from topological descriptors, has proved to be challenging. In this article, we study in detail the Topological Morphology Descriptor (TMD), which assigns a persistence diagram to any tree embedded in Euclidean space, and a sort of stochastic inverse to the TMD, the Topological Neuron Synthesis (TNS) algorithm, gaining both theoretical and computational insights into the relation between the two. We propose a new approach to classify barcodes using symmetric groups, which provides a concrete language to formulate our results. We investigate to what extent the TNS recovers a geometric tree from its TMD and describe the effect of different types of noise on the process of tree generation from persistence diagrams. We prove moreover that the TNS algorithm is stable with respect to specific types of noise.

From Trees to Barcodes and Back Again:A Combinatorial, Probabilistic and Geometric Study of a Topological Inverse Problem

Adélie Eliane Garin

In this thesis, we investigate the inverse problem of trees and barcodes from a combinatorial, geometric, probabilistic and statistical point of view.Computing the persistent homology of a merge tree yields a barcode B. Reconstructing a tree from B involves gluing the branches back together. We are able to define combinatorial equivalence classes of merge trees and barcodes that allow us to completely solve this inverse problem. A barcode can be associated with an element in the symmetric group, and the number of trees with the same barcode, the tree realization number, depends only on the permutation type. We compare these combinatorial definitions of barcodes and trees to those of phylogenetic trees, thus describing the subtle differences between these spaces. The result is a clear combinatorial distinction between the phylogenetic tree space and the merge tree space.The representation of a barcode by a permutation not only gives a formula for the tree realization number, but also opens the door to deeper connections between inverse problems in topological data analysis, group theory, and combinatorics.Based on the combinatorial classes of barcodes, we construct a stratification of the barcode space. We define coordinates that partition the space of barcodes into regions indexed by the averages and the standard deviations of birth and death times and by the permutation type of a barcode. By associating to a barcode the coordinates of its region, we define a new invariant of barcodes.These equivalence classes define a stratification of the space of barcodes with n bars where the strata are indexed by the symmetric group on n letters and its parabolic subgroups.We study the realization numbers computed from barcodes with uniform permutation type (i.e., drawn from the uniform distribution on the symmetric group) and establish a fundamental null hypothesis for this invariant. We show that the tree realization number can be used as a statistic to distinguish distributions of trees by comparing neuronal trees to random barcode distributions.

EPFL2022

Algebraic Homotopy Interleaving Distance

Nicolas Michel Berkouk

The theory of persistence, which arises from topological data analysis, has been intensively studied in the one-parameter case both theoretically and in its applications. However, its extension to the multi-parameter case raises numerous difficulties, where it has been proven that no barcode-like decomposition exists. To tackle this problem, algebraic invariants have been proposed to summarize multi-parameter persistence modules, adapting classical ideas from commutative algebra and algebraic geometry to this context. Nevertheless, the crucial question of their stability has raised little attention so far, and many of the proposed invariants do not satisfy a naive form of stability. In this paper, we equip the homotopy and the derived category of multi-parameter persistence modules with an appropriate interleaving distance. We prove that resolution functors are always isometric with respect to this distance. As an application, this explains why the graded-Betti numbers of a persistence module do not satisfy a naive form of stability. This opens the door to performing homological algebra operations while keeping track of stability. We believe this approach can lead to the definition of new stable invariants for multi-parameter persistence, and to new computable lower bounds for the interleaving distance (which has been recently shown to be NP-hard to compute in [2]).

SPRINGER INTERNATIONAL PUBLISHING AG2021

From Trees to Barcodes and Back Again:A Combinatorial, Probabilistic and Geometric Study of a Topological Inverse Problem

Adélie Eliane Garin

EPFL2022