Collapse-invariant properties of spaces equipped with signals or directions

Collapsing cell complexes was first introduced in the 1930's as a way to deform a space into a topological-equivalent subspace with a sequence of elementary moves. Recently, discrete Morse theory techniques provided an efficient way to construct deformation retracts collapsing one space into the other while preserving global topological properties. This type of collapse, called a Morse matching, has been widely used to speed up computations in (persistent) homology by reducing the size of complexes. Unlike classical collapses, in this thesis we consider topological spaces equipped with signals or directions. The main goal is then to reduce the size of the spaces while preserving as much as possible of both the topological structure and the properties of the signals or the directions. In the first part of the thesis we explore collapsing in topological signal processing. In this context, each signal on the cells of a complex is processed using the combinatorial Laplacian and the resultant Hodge decomposition.In Article 2.1 we provide an approach to signal compression and reconstruction on chain complexes that leverages the tools of algebraic discrete Morse theory. We first prove that any deformation retract of real finite-dimensional based chain complex is equivalent to a Morse matching. We then study the interaction between the Hodge decomposition and signal compression and reconstruction. Specifically, we prove that parts of a signal's Hodge decomposition are preserved under compression and reconstruction for specific classes of discrete Morse deformation retracts of a given based chain complex. Finally, we provide an algorithm to compute Morse matchings with minimal reconstruction error.Complementary to our theoretic results in topological signal processing, we provide two applications in this field. Article 2.2 extends graph convolutional neural networks to simplicial complexes, while Article 2.3 presents a novel algorithm, inspired by the well-known spectral clustering algorithm, to embed simplices in a Euclidean space. The object of our studies in the second part of the thesis is topological spaces equipped with a sense of direction. In the directed setting, the topology of the space is characterized by directed paths between fixed initial and terminal points. Motivated by applications in concurrent programs, we focus on directed Euclidean cubical complexes and their spaces of directed paths.In Article 3.1 we define a notion of directed collapsibility for Euclidean cubical complexes using the notion of past links, a combinatorial local representations of cubical complexes. We show that this notion of collapsability preserves given properties of the directed path spaces. In particular, we give sufficient conditions for a directed Euclidean cubical complex to have a contractible or a connected space of directed paths from a fixed initial vertex.In Article 3.2 we extend these results, providing further conditions for directed collapses to preserve the contractability or conneectdness of spaces of directed paths. Furthermore, we provide simple combinatorial conditions for preserving the topology of past links. These conditions are the first step towards developing an algorithm that checks at each iteration if a collapse preserves certain properties of the directed space.

Reduced representations of complexes, signals, and multifiltrations

Celia Camille Hacker

The field of computational topology has developed many powerful tools to describe the shape of data, offering an alternative point of view from classical statistics. This results in a variety of complex structures that are not always directly amenable for machine learning tasks. We develop theory and algorithms to produce computable representations of simplicial or cell complexes, potentially equipped with additional information such as signals and multifiltrations. The common goal of the topics discussed in this thesis is to find reduced representations of these often high dimensional and complex structures to better visualize, transform or formulate theoretical results about them. We extend the well known graph learning algorithm node2vec to simplicial complexes, a higher dimensional analogue of graphs. To this end we propose a way to define random walks on simplicial complexes, which we then use to design an extension of node2vec called k-simplex2vec, producing a representation of the simplices in a Euclidean space. Furthermore, the study of this method leads to interesting questions about robustness of graph and simplicial learning methods. In the case of graphs, we study node2vec embeddings arising from different parameter sets, analysing their quality and stability using various measures. In the topic of signal processing, we explore how discrete Morse theory can be used for compression and reconstruction of cell complexes equipped with signals. In particular we study the effect of the compression of a complex on the Hodge decomposition of its signals. We study how the signal changes through compression and reconstruction by introducing a topological reconstruction error, showing in particular that part of the Hodge decomposition is preserved. Moreover, we prove that any deformation retract over R can be expressed as a Morse deformation retract in a well-chosen basis, thus extending the reconstruction results to any deformation retract. In addition, we introduce an algorithm to minimize the loss induced by the reconstruction of a compressed signal. Finally, we use discrete Morse theory to compute an invariant of multi-parameter persistent homology, the rank invariant. We can restrict a multi-parameter persistence module to a one- dimensional persistence module along any line of positive slope and compute the one-dimensional analogue of the rank invariant, namely the barcode. Through a discrete Morse matching we can determine critical values in the multifiltration, which in turn allows us to identify equivalence classes of lines in the parameter space. In our main result, we explain how to compute the barcode along any given line of an equivalence class given the barcode along a representative line. This provides a way to fiber the rank invariant according to the critical values of a discrete Morse matching and to perform computations in the corresponding one-dimensional module, which is much better understood.

EPFL2022

Reduced representations of complexes, signals, and multifiltrations

Celia Camille Hacker

EPFL2022