Topological data analysis and, more specifically, persistent homology have received significant attention as a method of describing the shape of complex data. Persistent homology measures the persistence (i.e., "relative size'') of topological features such as connected components, holes, voids, etc. as a space is filtered. The persistence is often plotted in what is referred to as a persistence diagram. Persistence diagrams encode both topological and geometric information about shapes. Moreover, certain parameterized sets of persistence diagrams are sufficient for representing particular classes of shapes. In other words, a set of persistence diagrams can be substituted for the shape. Shape representation using persistence diagrams has shown promise in several learning and classification tasks on shape data. However, choosing a sufficient parameterized set of persistence diagrams is challenging. Previous solutions utilize exhaustive sampling approaches based on assumptions on the geometry of the shape and algebraic results. We consider the inverse problem of "reconstructing'' the shape, using (augmented) persistence diagrams. Developing algorithms for reconstruction provides an alternative method of finding descriptors for representation that is optimized to minimize the number of diagrams and time complexity. In this work, we provide deterministic algorithms for reconstructing simplicial complexes in R^d and discuss challenges in reconstruction using other topological descriptors.
Shape reconstruction, and several other areas of research utilizing the persistence diagram, are predisposed to generating large numbers of diagrams. As such, developing efficient methods for searching in the space of persistence diagrams is also of great importance. We consider the bottleneck distance in the space of persistence diagrams. The bottleneck distance is used often in practice for comparing one diagram to another. However, the cost of computing the bottleneck distance can grow prohibitive for large sets of diagrams using a brute-force approach. We offer a data structure and algorithm for identifying the approximate nearest neighbor (and approximate k-nearest neighbors) in the space of persistence diagrams in less time than the brute-force approach for large sets of diagrams.
|Advisor:||Fasy, Brittany T|
|Commitee:||Wittie, Mike P, Wenk, Carola, Zhu, Binhai, Millman, David L|
|School:||Montana State University|
|School Location:||United States -- Montana|
|Source:||DAI-B 81/11(E), Dissertation Abstracts International|
|Keywords:||Algorithms, Bottleneck distance, Montana State University, Nearest neighbor, Persistence diagram search, Shape reconstruction|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be