Browsing by Subject "Computational topology"

This dissertation places intersection homology and local homology within the framework of persistence, which was originally developed for ordinary homology by Edelsbrunner, Letscher, and Zomorodian. The eventual goal, begun but not completed here, is to provide analytical tools for the study of embedded stratified spaces, as well as for high-dimensional and possibly noisy datasets for which the number of degrees of freedom may vary across the parameter space. Specifically, we create a theory of persistent intersection homology for a filtered stratified space and prove several structural theorems about the pair groups asso- ciated to such a filtration. We prove the correctness of a cubic algorithm which computes these pair groups in a simplicial setting. We also define a series of intersec- tion homology elevation functions for an embedded stratified space and characterize their local maxima in dimension one. In addition, we develop a theory of persistence for a multi-scale analogue of the local homology groups of a stratified space at a point. This takes the form of a series of local homology vineyards which allow one to assess the homological structure within a one-parameter family of neighborhoods of the point. Under the assumption of dense sampling, we prove the correctness of this assessment at a variety of radius scales.

This dissertation extends the theory of persistent homology to time varying systems. Most of the previous work has been dedicated to using this powerful tool in topological data analysis to study static point clouds. In particular, given a point cloud, we can construct its persistence diagram. Since the diagram varies continuously as the point cloud varies continuously, we study the space of time varying persistence diagrams, called vineyards when they were introduced by Cohen-Steiner, Edelsbrunner, and Morozov.

We will first show that with a good choice of metric, these vineyards are stable for small perturbations of their associated point clouds. We will also define a new mean for a set of persistence diagrams based on the work of Mileyko et al. which, unlike the previously defined mean, is continuous for geodesic vineyards.

Next, we study the sensor network problem posed by Ghrist and de Silva, and their application of persistent homology to understand when a set of sensors covers a given region. Giving each of these sensors a probability of failure over time, we show that an exact computation of the probability of failure of the whole system is NP-hard, but give an algorithm which can predict failure in the case of a monitored system.

Finally, we apply these methods to an automated system which can cluster agents moving in aerial images by their behaviors. We build a data structure for storing and querying the information in real-time, and define behavior vectors which quantify behaviors of interest. This clustering by behavior can be used to find groups of interest, for which we can also quantify behaviors in order to determine whether the group is working together to achieve a common goal, and we speculate that this work can be extended to improving tracking algorithms as well as behavioral predictors.

The work presented in this dissertation includes the study of cohomology and cohomological operations within the framework of Persistence. Although Persistence was originally defined for homology, recent research has developed persistent approaches to other algebraic topology invariants. The work in this document extends the field of persistence to include cohomology classes, cohomology operations and characteristic classes.

By starting with presenting a combinatorial formula to compute the Stiefel-Whitney homology class, we set up the groundwork for Persistent Characteristic Classes. To discuss persistence for the more general cohomology classes, we construct an algorithm that allows us to find the Poincar'{e} Dual to a homology class. Then, we develop two algorithms that compute persistent cohomology, the general case and one for a specific cohomology class. We follow this with defining and composing an algorithm for extended persistent cohomology.

In addition, we construct an algorithm for determining when a cohomology class is decomposible and compose it in the context of persistence. Lastly, we provide a proof for a concise formula for the first Steenrod Square of a given cohomology class and then develop an algorithm to determine when a cohomology class is a Steenrod Square of a lower dimensional cohomology class.

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.

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.

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.

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.

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.