Submitted by FERNANDO GASPAROTTO DA SILVA null (fernando.gaspt@hotmail.com) on 2017-09-13T20:17:28Z No. of bitstreams: 1 Gasparotto da Silva, F. - Estrutura e estabilidade de módulos de persistência.pdf: 1909578 bytes, checksum: 4ee1ae3d4306638fe4afbf721614e688 (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-09-15T13:38:44Z (GMT) No. of bitstreams: 1 silva_fg_me_sjrp.pdf: 1909578 bytes, checksum: 4ee1ae3d4306638fe4afbf721614e688 (MD5) / Made available in DSpace on 2017-09-15T13:38:44Z (GMT). No. of bitstreams: 1 silva_fg_me_sjrp.pdf: 1909578 bytes, checksum: 4ee1ae3d4306638fe4afbf721614e688 (MD5) Previous issue date: 2017-08-14 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / O intuito deste trabalho é de integrar os aspectos aplicado e teórico da Homologia Persistente, uma ferramenta popular da Topological Data Analysis (TDA). Para isso, são apresentados e demonstrados os resultados fundamentais da teoria embasada na topologia algébrica que permitem o desenvolvimento de algoritmos e paradigmas computacionais para obter diagramas de persistência. Dessa forma, iniciaremos explorando como decodificar as informações contidas em um módulo de persistência, entendendo os conceitos de multiconjuntos, módulos de persistência e cálculos Quiver. Em seguida, o caminho contrário será explorado, onde os dados são codificados em diagramas de persistência a fim de extrair suas características topológicas, aprofundando os conceitos de funções de Morse, Homologia Persistente, diagramas de persistência, dualidade e simetria, bem como estabilidade. Por último, encerramos demonstrando duas possíveis aplicações da teoria no âmbito computacional no campo da Biologia. / The goal of this work is to integrate applied and theoretical aspects of Persistence Homology, a popular tool in Topological Data Analysis (TDA). For this, we present and prove fundamental theoretical results based on algebraic topology, which allow us to develop algorithms and computational paradigms to obtain persistence diagrams. In this way, we start exploring how to decode the information contained in a persistence module, understanding the concepts of multiset, persistence modules and Quiver alculations. Then, the opposite path will be explored, where the data are encoded in persistence diagrams in order to extract their topological characteristics, going deep into the concepts of Morse functions, persistent homology, persistence diagrams, duality and symmetry, as well as stability. Finally, we conclude with two possible applications, one from computational theory, and the second one in the field of biology. / CNPq: 135622/2015-8

Orientador: Hélio Pedrini / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:14:20Z (GMT). No. of bitstreams: 1 Silva_RicardoDutrada_D.pdf: 13549105 bytes, checksum: 3d49e5116a70a72601ba4cc3b3c85762 (MD5) Previous issue date: 2013 / Resumo: A Teoria de Morse é importante para o estudo da topologia em funções escalares como elevação de terrenos e dados provenientes de simulações físicas, a qual relaciona a topologia de uma função com seus pontos críticos. A teoria contínua foi adaptada para dados discretos através de construções como os complexos de Morse-Smale e o complexo discreto de Morse. Complexos de Morse têm sido aplicados em processamento de imagens, no entanto, ainda existem desafios envolvendo algoritmos e considerações práticas para a computação e modelagem dos complexos para imagens. Complexos de Morse podem ser usados como um meio de definir a conexão entre pontos de interesse em imagens. Normalmente, pontos de interesse são considerados como elementos independentes descritos por informação local. Tal abordagem apresenta limitações uma vez que informação local pode não ser suficiente para descrever certas regiões da imagem. Pontos de mínimo e máximo são comumente utilizados como pontos de interesse em imagens, os quais podem ser obtidos a partir dos complexos de Morse, bem como sua conectividade no espaço de imagem. Esta tese apresenta uma abordagem dirigida por algoritmos e estruturas de dados para computar o complexo de Morse discreto em imagens bidimensionais. A construção é ótima e permite fácil manipulação do complexo. Resultados teóricos e experimentais são apresentados para mostrar que o método é eficaz. Experimentos realizados incluem a computação de homologia persistente e hierarquias de complexos sobre dados de elevação de terrenos. Outra contribuição é a proposição de um operador topológico, chamado Contexto Local de Morse, computado sobre complexos de Morse, para extrair vizinhanças de pontos de interesse para explorar a informação estrutural de imagens. O contexto local de Morse é usado no desenvolvimento de um algoritmo que auxilia a redução do número de casamentos incorretos entre pontos de interesse e na obtenção de uma medida de confiança para tais correspondências. A abordagem proposta é testada em pares de imagens sintéticas e de imagens subaquáticas, para as quais métodos existentes podem obter muitas correspondências incorretas / Abstract: The Morse theory is important for studying the topology of scalar functions such as elevation of terrains and data from physical simulations, which relates the topology of a function to critical points. The smooth theory has been adapted to discrete data through constructions such as the Morse-Smale complexes and the discrete Morse complex. Morse complexes have been applied to image processing, however, there are still challenges involving algorithms and practical considerations for computation and modeling of the complexes. Morse complexes can be used as means of defining the connectedness of interest points in images. Usually, interest points are considered as independent elements described by local information. Such an approach has its limitations since local information may not suffice for describing certain image regions. Minimum and maximum points are widely used as interest points in images, which can be obtained from Morse complexes, as well as their connectivity in the image space. This thesis presents an algorithmic and data structure driven approach to computing the discrete Morse complex of 2-dimensional images. The construction is optimal and allows easy manipulation of the complex. Theoretical and applied results are presented to show the effectiveness of the method. Applied experiments include the computation of persistent homology and hierarchies of complexes over elevation terrain data. Another contribution is the proposition of a topological operator, called Local Morse Context (LMC), computed over Morse complexes, for extracting neighborhoods of interest points to explore the structural information in images. The LMC is used in the development of a matching algorithm, which helps reducing the number of incorrect matches between images and obtaining a confidence measure of whether a correspondence is correct or incorrect. The approach is tested in synthetic and challenging underwater stereo pairs of images, for which available methods may obtain many incorrect correspondences / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

<p>Harnessing the power of data has been a driving force for computing in recently years. However, the non-vectorized or even non-Euclidean nature of certain data with complex structures also poses new challenges to the data science community. Topological data analysis (TDA) has proven effective in several scenarios for alleviating the challenges, by providing techniques that can reveal hidden structures and high-order connectivity for data. A central technique in TDA is called persistent homology, which provides intervals tracking the birth and death of topological features in a growing sequence of topological spaces. In this dissertation, we study the representative problem for persistent homology, motivated by the observation that persistent homology does not pinpoint a specific homology class or cycle born and dying with the persistence intervals. Furthermore, studying the representatives also leads us to new findings for related problems such as persistence computation.<br> </p> <p>First, we look into the representative problem for (standard) persistence homology and term the representatives as persistent cycles. We define persistent cycles as cycles born and dying with given persistence intervals and connect the definition to interval decomposition for persistence modules. We also look into the computation of optimal (minimum) persistent cycles which have guaranteed quality. We prove that it is NP-hard to compute minimum persistent p-cycles for the two types of intervals in persistent homology in general dimensions (p>1). In view of the NP-hardness results, we then identify a special but important class of inputs called weak (p+1)-pseudomanifolds whose minimum persistent p-cycles can be computed in polynomial time. The algorithms are based on a reduction to minimum (s,t)-cuts on dual graphs.<br> </p> <p>Second, we propose alternative persistent cycles capturing the dynamic changes of homological features born and dying with persistence intervals, which the previous persistent cycles do not reveal. We focus on persistent homology generated by piecewise linear (PL) functions and base our definition on an extension of persistence called the levelset zigzag persistence. We define a sequence of cycles called levelset persistent cycles containing a cycle between each consecutive critical points within the persistence interval. Due to the NP-harness results proven previously, we propose polynomial-time algorithms computing optimal sequences of levelset persistent p-cycles for weak (p+1)-pseudomanifolds. Our algorithms draw upon the idea of relating optimal cycles to min-cuts in a graph that we exploited earlier for standard persistent cycles. Note that levelset zigzag poses non-trivial challenges for the approach because a sequence of optimal cycles instead of a single one needs to be computed in this case.<br> </p> <p>Third, we investigate the computation of zigzag persistence on graph inputs, motivated by the fact that graphs model real-world circumstances in many applications where they may constantly change to capture dynamic behaviors of phenomena. Zigzag persistence, an extension of the standard persistence incorporating both insertions and deletions of simplices, is one appropriate instrument for analyzing such changing graph data. However, unlike standard persistence which admits nearly linear-time algorithms for graphs, such results for the zigzag version improving the general $O(m^\omega)$ time complexity are not known, where $\omega< 2.37286$ is the matrix multiplication exponent. We propose algorithms for zigzag persistence on graphs which run in near-linear time. Specifically, given a filtration of length m on a graph of size n, the algorithm for 0-dimension runs in $O(m\log^2 n+m\log m)$ time and the algorithm for 1-dimension runs in $O(m\log^4 n)$ time. The algorithm for 0-dimension draws upon another algorithm designed originally for pairing critical points of Morse functions on 2-manifolds. The correctness proof of the algorithm, which is a major contribution, is achieved with the help of representatives. The algorithm for 1-dimension pairs a negative edge with the earliest positive edge so that a representative 1-cycle containing both edges resides in all intermediate graphs.</p>

<p>Recent innovations in combinatorial dynamical systems permit them to be studied with algorithmic methods. One such method from topological data analysis, called persistent homology, allows one to summarize the changing homology of a sequence of simplicial complexes. This dissertation explicates three methods for capturing and summarizing changes in combinatorial dynamical systems through the lens of persistent homology. The first places the Conley index in the persistent homology setting. This permits one to capture the persistence of salient features of a combinatorial dynamical system. The second shows how to capture changes in combinatorial dynamical systems at different resolutions by computing the persistence of the Conley-Morse graph. Finally, the third places Conley's notion of continuation in the combinatorial setting and permits the tracking of isolated invariant sets across a sequence of combinatorial dynamical systems. </p>

No description available.

Stable rank has recently been proposed as an invariant to encode the result of persistent homology, a method used in topological data analysis. In this thesis we develop methods for statistical analysis as well as machine learning methods based on stable rank. As stable rank may be viewed as a mapping to a Hilbert space, a kernel can be constructed from the inner product in this space. First, we investigate this kernel in the context of kernel learning methods such as support-vector machines. Next, using the theory of kernel embedding of probability distributions, we give a statistical treatment of the kernel by showing some of its properties and develop a two-sample hypothesis test based on the kernel. As an alternative approach, a mapping to a Euclidean space with learnable parameters can be conceived, serving as an input layer to a neural network. The developed methods are first evaluated on synthetic data. Then the two-sample hypothesis test is applied on the OASIS open access brain imaging dataset. Finally a graph classification task is performed on a dataset collected from Reddit. / Stable rank har föreslagits som en sammanfattning på datanivå av resultatet av persistent homology, en metod inom topologisk dataanalys. I detta examensarbete utvecklar vi metoder inom statistisk analys och maskininlärning baserade på stable rank. Eftersom stable rank kan ses som en avbildning i ett Hilbertrum kan en kärna konstrueras från inre produkten i detta rum. Först undersöker vi denna kärnas egenskaper när den används inom ramen för maskininlärningsmetoder som stödvektormaskin (SVM). Därefter, med grund i teorin för inbäddning av sannolikhetsfördelningar i reproducing kernel Hilbertrum, undersöker vi hur kärnan kan användas för att utveckla ett test för statistisk hypotesprövning. Slutligen, som ett alternativ till metoder baserade på kärnor, utvecklas en avbildning i ett euklidiskt rum med optimerbara parametrar, som kan användas som ett ingångslager i ett neuralt nätverk. Metoderna utvärderas först på syntetisk data. Vidare utförs ett statistiskt test på OASIS, ett öppet dataset inom neuroradiologi. Slutligen utvärderas metoderna på klassificering av grafer, baserat på ett dataset insamlat från Reddit. / <p>QC 20200523</p>

<p dir="ltr">Topological Data Analysis (TDA) with its roots embedded in the field of algebraic topology has successfully found its applications in computational biology, drug discovery, machine learning and in many diverse areas of science. One of its cornerstones, persistent homology, captures topological features latent in the data. Recent progress in TDA allows us to integrate these finer topological features into traditional machine learning and deep learning pipelines. However, the utilization of topological methods within a conventional deep learning framework remains relatively uncharted. This thesis presents four scenarios where computational topology tools are employed to advance machine learning.</p><p dir="ltr">The first one involves integrating persistent homology to explore high-dimensional cytometry data. The second one incorporates Extended persistence in a supervised graph classification framework and demonstrates leveraging TDA in cases where data naturally aligns with higher-order elements by extending graph neural networks to higher-order networks, applied specifically in non-manifold mesh classification. The third and fourth scenarios delve into enhancing graph neural networks through multiparameter persistence.</p>

No description available.

La topologie algébrique, bien que domaine abstrait des mathématiques, apporte de nouveaux concepts pour le traitement d'images. En effet, ces tâches sont complexes et restent limitées par différents facteurs tels que la nécessité d’utiliser un paramétrage, l'influence de l'arrière-plan ou la superposition d'objets. Nous proposons ici des méthodes dérivées de la topologie algébrique qui diffèrent des méthodes classiques de traitement d'images par l’intégration d’informations locales vers des échelles globales grâce à des invariants topologiques. Une première méthode de segmentation d'images a été développée en ajoutant aux caractéristiques statistiques classiques d’autres de nature topologique calculées par homologie persistante. Une autre méthode basée sur des complexes topologiques a été développée dans le but de segmenter les objets dans des images 2D et 3D. Cette méthode segmente des objets dans des images multidimensionnelles et fournit une réponse à certains problèmes habituels en restant robuste vis à vis du bruit et de la variabilité de l'arrière-plan. Son application aux images de grande taille peut se faire en utilisant des superpixels. Nous avons également montré que l'homologie relative détecte le mouvement d’objets dans une séquence d'images qui apparaissent et disparaissent du début à la fin. Enfin, nous posons les bases d’un ensemble de méthodes d'analyse d'images basé sur la théorie des faisceaux qui permet de fusionner des données locales en un ensemble cohérent. De plus, nous proposons une seconde approche qui permet de comprendre et d'interpréter la structure d’une image en utilisant les invariants fournis par la cohomologie des faisceaux. / Algebraic topology, which is often appears as an abstract domain of mathematics, can bring new concepts in the execution of the image processing tasks. Indeed, these tasks might be complex and limited by different factors such as the need of prior parameters, the influence of the background, the superposition of objects. In this thesis, we propose methods derived from algebraic topology that differ from classical image processing methods by integrating local information at global scales through topological invariants. A first method of image segmentation was developed by adding topological characteristics calculated through persistent homology to classical statistical characteristics. Another method based on topological complexes built from pixels was developed with the purpose to segment objects in 2D and 3D images. This method allows to segment objects in multidimensional images but also to provide an answer to known issues in object segmentation remaining robust regarding the noise and the variability of the background. Our method can be extended to large scale images by using the superpixels concept. We also showed that the relative version of homology can be used effectively to detect the movement of objects in image sequences. This method can detect and follow objects that appear and disappear in a video sequence from the beginning to the end of the sequence. Finally, we lay the foundations of a set of methods of image analysis based on sheaf theory that allows the merging of local data into a coherent whole. Moreover, we propose a second approach that allows to understand and interpret scale analysis and localization by using the sheaves cohomology.

This thesis presents a series of algorithmic innovations in Combinatorial Compressed Sensing and Persistent Homology. The unifying strategy across these contributions is in translating structural patterns in the underlying data into specific algorithmic designs in order to achieve: better guarantees in computational complexity, the ability to operate on more complex data, highly efficient parallelisations, or any combination of these.