La théorie de l'homologie généralise en dimensions supérieures la notion de connectivité dans les graphes. Étant donné un domaine, décrit par un complexe simplicial, elle définit une famille de groupes qui capturent le nombre de composantes connexes, le nombre de trous, le nombre de cavités et le nombre de motifs équivalents en dimensions supérieures. En pratique, l'homologie permet d'analyser des systèmes de données complexes, interprétés comme des nuages de points dans des espaces métriques. La théorie de l'homologie persistante introduit une notion robuste d'homologie pour l'inférence topologique. Son champ d'application est vaste, et comprend notamment la description d'espaces des configurations de systèmes dynamiques complexes, la classification de formes soumises à des déformations et l'apprentissage en imagerie médicale. Dans cette thèse, nous étudions les ramifications algorithmiques de l'homologie persistante. En premier lieu, nous introduisons l'arbre des simplexes, une structure de données efficace pour construire et manipuler des complexes simpliciaux de grandes dimensions. Nous présentons ensuite une implémentation rapide de l'algorithme de cohomologie persistante à l'aide d'une matrice d'annotations compressée. Nous raffinons également l'inférence de topologie en décrivant une notion de torsion en homologie persistante, et nous introduisons la méthode de reconstruction modulaire pour son calcul. Enfin, nous présentons un algorithme de calcul de l'homologie persistante zigzag, qui est une généralisation algébrique de la persistance. Pour cet algorithme, nous introduisons de nouveaux théorèmes de transformations locales en théorie des représentations de carquois, appelés principes du diamant. Ces algorithmes sont tous implémentés dans la librairie de calcul Gudhi. / The theory of homology generalizes the notion of connectivity in graphs to higher dimensions. It defines a family of groups on a domain, described discretely by a simplicial complex that captures the connected components, the holes, the cavities and higher-dimensional equivalents. In practice, the generality and flexibility of homology allows the analysis of complex data, interpreted as point clouds in metric spaces. The theory of persistent homology introduces a robust notion of homology for topology inference. Its applications are various and range from the description of high dimensional configuration spaces of complex dynamical systems, classification of shapes under deformations and learning in medical imaging. In this thesis, we explore the algorithmic ramifications of persistent homology. We first introduce the simplex tree, an efficient data structure to construct and maintain high dimensional simplicial complexes. We then present a fast implementation of persistent cohomology via the compressed annotation matrix data structure. We also refine the computation of persistence by describing ideas of homological torsion in this framework, and introduce the modular reconstruction method for computation. Finally, we present an algorithm to compute zigzag persistent homology, an algebraic generalization of persistence. To do so, we introduce new local transformation theorems in quiver representation theory, called diamond principles. All algorithms are implemented in the computational library Gudhi.
| Identifer | oai:union.ndltd.org:theses.fr/2014NICE4081 |
| Date | 28 October 2014 |
| Creators | Maria, Clément |
| Contributors | Nice, Boissonnat, Jean-Daniel |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0016 seconds