Publication

Reduced representations of complexes, signals, and multifiltrations

Celia Camille Hacker
2022
Thèse EPFL
Résumé

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.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Concepts associés (54)
Topological data analysis
In applied mathematics, topological data analysis (TDA) is an approach to the analysis of datasets using techniques from topology. Extraction of information from datasets that are high-dimensional, incomplete and noisy is generally challenging. TDA provides a general framework to analyze such data in a manner that is insensitive to the particular metric chosen and provides dimensionality reduction and robustness to noise. Beyond this, it inherits functoriality, a fundamental concept of modern mathematics, from its topological nature, which allows it to adapt to new mathematical tools.
Complexe simplicial
thumb|Exemple d'un complexe simplicial.En mathématiques, un complexe simplicial est un objet géométrique déterminé par une donnée combinatoire et permettant de décrire certains espaces topologiques en généralisant la notion de triangulation d'une surface. Un tel objet se présente comme un graphe avec des sommets reliés par des arêtes, sur lesquelles peuvent se rattacher des faces triangulaires, elles-mêmes bordant éventuellement des faces de dimension supérieure, etc.
CW-complexe
En topologie algébrique, un CW-complexe est un type d'espace topologique, défini par J. H. C. Whitehead pour répondre aux besoins de la théorie de l'homotopie. L'idée était de travailler sur une classe d'objets plus grande que celle des complexes simpliciaux et possédant de meilleures propriétés du point de vue de la théorie des catégories, mais présentant comme eux des propriétés combinatoires se prêtant aux calculs. Le nom CW provient du qualificatif de l'espace topologique, en anglais : closure-finite weak topology, pour « à fermeture finie » et « topologie faible ».
Afficher plus
Publications associées (77)

Cochains are all you need

In this thesis, we apply cochain complexes as an algebraic model of space in a diverse range of mathematical and scientific settings. We begin with an algebraic-discrete Morse theory model of auto-encoding cochain data, connecting the homotopy theory of d ...
EPFL2024

A structured prediction approach for robot imitation learning

Aude Billard, Iason Batzianoulis, Anqing Duan

We propose a structured prediction approach for robot imitation learning from demonstrations. Among various tools for robot imitation learning, supervised learning has been observed to have a prominent role. Structured prediction is a form of supervised le ...
London2023

Equivariant Neural Architectures for Representing and Generating Graphs

Clément Arthur Yvon Vignac

Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences. By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entitie ...
EPFL2023
Afficher plus
MOOCs associés (32)
Introduction to optimization on smooth manifolds: first order methods
Learn to optimize on smooth, nonlinear spaces: Join us to build your foundations (starting at "what is a manifold?") and confidently implement your first algorithm (Riemannian gradient descent).
Digital Signal Processing [retired]
The course provides a comprehensive overview of digital signal processing theory, covering discrete time, Fourier analysis, filter design, sampling, interpolation and quantization; it also includes a
Digital Signal Processing
Digital Signal Processing is the branch of engineering that, in the space of just a few decades, has enabled unprecedented levels of interpersonal communication and of on-demand entertainment. By rewo
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.