<p>In this thesis, we explore techniques in statistics and persistent homology, which detect features among data sets such as graphs, triangulations and point cloud. We accompany our theorems with algorithms and experiments, to demonstrate their effectiveness in practice.</p><p></p><p>We start with the derivation of graph scan statistics, a measure useful to assess the statistical significance of a subgraph in terms of edge density. We cluster graphs into densely-connected subgraphs based on this measure. We give algorithms for finding such clusterings and experiment on real-world data.</p><p></p><p>We next study statistics on persistence, for piecewise-linear functions defined on the triangulations of topological spaces. We derive persistence pairing probabilities among vertices in the triangulation. We also provide upper bounds for total persistence in expectation. </p><p></p><p>We continue by examining the elevation function defined on the triangulation of a surface. Its local maxima obtained by persistence pairing are useful in describing features of the triangulations of protein surfaces. We describe an algorithm to compute these local maxima, with a run-time ten-thousand times faster in practice than previous method. We connect such improvement with the total Gaussian curvature of the surfaces.</p><p></p><p>Finally, we study a stratification learning problem: given a point cloud sampled from a stratified space, which points belong to the same strata, at a given scale level? We assess the local structure of a point in relation to its neighbors using kernel and cokernel persistent homology. We prove the effectiveness of such assessment through several inference theorems, under the assumption of dense sample. The topological inference theorem relates the sample density with the homological feature size. The probabilistic inference theorem provides sample estimates to assess the local structure with confidence. We describe an algorithm that computes the kernel and cokernel persistence diagrams and prove its correctness. We further experiment on simple synthetic data.</p> / Dissertation

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

<p>Applied topology is a rapidly growing discipline aiming at using ideas coming from algebraic topology to solve problems in the real world, including analyzing point cloud data, shape analysis, etc. Semi-algebraic geometry deals with studying properties of semi-algebraic sets that are subsets of $\mathbb{R}^n$ and defined in terms of polynomial inequalities. Semi-algebraic sets are ubiquitous in applications in areas such as modeling, motion planning, etc. Developing efficient algorithms for computing topological invariants of semi-algebraic sets is a rich and well-developed field.</p> <p>However, applied topology has thrown up new invariants---such as persistent homology and barcodes---which give us new ways of looking at the topology of semi-algebraic sets. In this thesis, we investigate the interplay between these two areas. We aim to develop new efficient algorithms for computing topological invariants of semi-algebraic sets, such as persistent homology, and to develop new mathematical tools to make such algorithms possible.</p>

No description available.

Artificial neural networks at the present time gain notable popularity and show astounding results in many machine learning tasks. This, however, also results in a drawback that the understanding of the processes happening inside of learning algorithms decreases. In many cases, the process of choosing a neural network architecture for a problem comes down to selection of network layers by intuition and to manual tuning of network parameters. Therefore, it is important to build a strong theoretical base in this area, both to try to reduce the amount of manual work in the future and to get a better understanding of capabilities of neural networks. In this master thesis, the ideas of applying different topological and geometric methods for the analysis of neural networks were investigated. Despite the difficulties which arise from the novelty of the approach, such as limited amount of related studies, some promising methods of network analysis were established and tested on baseline machine learning datasets. One of the most notable results of the study reveals how neural networks preserve topological features of the data when it is projected into space with low dimensionality. For example, the persistence for MNIST dataset with added rotations of images gets preserved after the projection into 3D space with the use of simple autoencoders; on the other hand, autoencoders with a relatively high weight regularization parameter might be losing this ability. / Artificiella neuronnät har för närvarande uppnått märkbar popularitet och visar häpnadsväckande resultat i många maskininlärningsuppgifter. Dock leder detta också till nackdelen att förståelsen av de processer som sker inom inlärningsalgoritmerna minskar. I många fall måste man använda intuition och ställa in parametrar manuellt under processen att välja en nätverksarkitektur. Därför är det viktigt att bygga en stark teoretisk bas inom detta område, både för att försöka minska manuellt arbete i framtiden och för att få en bättre förståelse för kapaciteten hos neuronnät. I detta examensarbete undersöktes idéerna om att tillämpa olika topologiska och geometriska metoder för analys av neuronnät. Många av svårigheterna härrör från det nya tillvägagångssättet, såsom en begränsad mängd av relaterade studier, men några lovande nätverksanalysmetoder upprättades och testades på standarddatauppsättningar för maskininlärning. Ett av de mest anmärkningsvärda resultaten av examensarbetet visar hur neurala nätverk bevarar de topologiska egenskaperna hos data när den projiceras till vektorrum med låg dimensionalitet. Till exempel bevaras den topologiska persistensen för MNIST-datasetet med tillagda rotationer av bilder efter projektion i ett tredimensionellt vektorrum med användning av en basal autoencoder; å andra sidan kan autoencoders med en relativt hög viktregleringsparameter förlora denna egenskap.

No description available.

[pt] Pesquisas na área de estrutura de dados são fundamentais para aumentar a generalidade e eficiência computacional da representacão de modelos geometricos. Neste trabalho, apresentamos duas estruturas de dados topológicas escalonáveis, uma para superfícies triânguladas, chamada CHE (Compact Half--Edge), e outra para malhas de tetraedros, chamada CHF (Compact Half--Face). Tais estruturas são compostas de diferentes níveis, que nos possibilitam alterar a quantidade de dados armazenados com objetivo de melhorar sua eficiência computacional. O uso de APIs baseadas no conceito de objeto, e de haran»ca de classes, possibilitam uma interface única para cada função em todos os níveis das estruturas. A CHE e a CHF requerem pouca memória e são simples de implementar já que substituem o uso de ponteiros pelo de contêineres genéricos e regras aritméticas. / [en] Research in data structure area are essential to increase the generality and computational effciency of geometric models` representation. In this work, we present two new scalable topological data structures, one for triangulated surfaces, called CHE (Compact Half { Edge ), and the another for tetrahedral meshes, called CHF (Compact Half { Face ). Such structures are composed of different levels, that enable us to modify the amount of data stored with the objective to improve its computational effciency. The use of APIs based in the object concept and class inheritance, makes possible an unique interface for each function at any level. CHE and CHF requires very few memory and are simple to implement since they substitute the use of pointers by generic containeres and arithmetical rules.

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

No description available.

Scientific phenomena are often studied through collections of related scalar fields such as data generated by simulation experiments that are parameter or time dependent . Exploration of such data requires robust measures to compare them in a feature aware and intuitive manner. Topological data analysis is a growing area that has had success in analyzing and visualizing scalar fields in a feature aware manner based on the topological features. Various data structures such as contour and merge trees, Morse-Smale complexes and extremum graphs have been developed to study scalar fields. The extremum graph is a topological data structure based on either the maxima or the minima of a scalar field. It preserves local geometrical structure by maintaining relative locations of extrema and their neighborhoods. It provides a suitable abstraction to study a collection of datasets where features are expressed by descending or ascending manifolds and their proximity is of importance. In this thesis, we design a measure to understand the similarity between scalar fields based on the extremum graph abstraction. We propose a topological structure called the complete extremum graph and define a distance measure on it that compares scalar fields in a feature aware manner. We design an algorithm for computing the distance and show its applications in analyzing time varying data such as understanding periodicity, feature correspondence and tracking, and identifying key frames.