Algorithms to Find Topological Descriptors for Shape Reconstruction and How to Search Them
- Monday, April 6, 2020 from 3:00pm to 6:00pm
- Webex: https://montana-student.webex.com/montana-student/j.php?MTID=m684f8e24e305e3b8cd6b8aa408499097
Samuel Micka will present "Algorithms to Find Topological Descriptors for Shape Reconstruction and How to Search Them" as part of his doctoral defense via WebEx at https://montana-student.webex.com/montana-student/j.php?MTID=m684f8e24e305e3b8cd6b8aa408499097.
Micka is a doctoral candidate in computer science in the Gianforte School of Computing in the Norm Asbjornson College of Engineering at Montana State University. He is advised by Brittany Fasy.
Topological data analysis and, more specifically, persistent homology has 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 the extended plane 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 the geometry of the shape and algebraic results. We consider the inverse problem of "reconstructing'' the shape, using (augmented) persistence diagrams, as a method of determining sufficiency. Developing algorithms for reconstruction provides an alternative method of solving the problem that strives to minimize the number of diagrams and time complexity. In this work, we describe deterministic algorithms for reconstructing simplicial complexes in Euclidean d-space and discuss challenges in reconstruction using other topological descriptors. However, a sufficient set of persistence diagrams for determining a shape typically has very large cardinality. Thus, 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, a metric in the space of persistence diagrams, and used frequently 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 determining the approximate nearest neighbor (and approximate k-nearest neighbors) in the space of persistence diagrams in less time that the brute-force approach for large sets of diagrams.
- Gianforte School of Computing
Gianforte School of Computing