Extensions and applications of persistence based algorithms in computational topology
- In this thesis, we discuss various extensions and applications of the seminal idea of persistent homology applied to metric datasets. In the first part, we discuss the computation of certain classes of maps between chains on simplicial complexes. It turns out that the parameterization of appropriately functorial maps may be found by computing the homology of the hom-complex of two chain complexes. We also discuss the selection of geometrically meaningful maps through optimization procedures. In particular, one would be interested in computing maps between chains on the complexes that are bisimplicial - meaning that the images and preimages of simplices contain either zero or one simplices. We also develop a relaxation of this problem that can be framed as a linear program. The theory of zigzag persistence has opened new doors in topological data analysis. Hypothetical applications were discussed in a paper by Carlsson and de Silva. In the second part we discuss in detail algorithms and the implementation of these applications, and demonstrate their use on various datasets. The applications include topological bootstrapping, parameter thresholding, and the comparison of witness complexes. In the third part we discuss some theoretical and algorithmic results on the probabilistic nature of random matroids, random subgraphs and random subcomplexes. First, we discuss some background information regarding sampling matroids, and provide some connections to existing literature on computational complexity and combinatorics. We close with a discussion regarding the randomized computation of the Tutte polynomial of certain dense graphs as well as the extension of these results to sampling the higher skeleta of simplicial complexes.
|Type of resource
|electronic; electronic resource; remote
|1 online resource.
|Tausz, Andrew Paul
|Stanford University, Institute for Computational and Mathematical Engineering.
|Guibas, Leonidas J
|Guibas, Leonidas J
|Statement of responsibility
|Submitted to the Institute for Computational and Mathematical Engineering.
|Thesis (Ph.D.)--Stanford University, 2012.
- © 2012 by Andrew Paul Tausz
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...