Dissertation
A NORMALIZED BOTTLENECK DISTANCE FOR PERSISTENCE DIAGRAMS AND OCTREE SPATIAL PARTITIONING FOR DISCRETE OPTIMAL TRANSPORT
Washington State University
Doctor of Philosophy (PhD), Washington State University
01/2022
DOI:
https://doi.org/10.7273/000004637
Handle:
https://hdl.handle.net/2376/124949
Abstract
In this work, we address two topics: a normalized bottleneck distance for persistencediagrams, and octree spatial partitioning schemes for discrete optimal transport. In the first part of this work, our focus is the bottleneck distance for persistence diagrams. Persistent homology is a powerful tool in topological data analysis (TDA) [3, 8]. For point-cloud data, persistence diagrams allows us to observe “holes” in data when it is reasonable or advantageous to assume that the data has been sampled from a manifold. On top of this, the bottleneck-distance allows us to compare data sets by directly comparing their persistence diagrams. One potential drawback of this approach for comparing data sets is that point clouds sampled from homeomorphic manifolds can have an arbitrarily large bottleneck distance when there is a large degree of scaling. In the first part of this work, we will look at a possible remediation to this problem via appropriate metric normalization and associated bottleneck distance. We define a new distance between persistence diagrams, termed the normalized bottleneck distance, and study its properties, as well as look at some specific examples from dimension reduction in which the scaled bottleneck may be a better choice in comparing the original and reduced data. In the second part of this work, our focus is octree spatial partitioning for discrete optimal transport. Intuitively, optimal transport seeks to find a transport scheme from one probability distribution to another, that “moves the mass” from one distribution to the other in the most “efficient” manner possible. Finding optimal transport plans can be quite computationally costly, however, especially when the histogram supports are grids in R3. In this work, we propose a coarsening scheme that aims to alleviate computational cost without introducing too much error with respect to the pth Wasserstein distance. We show that under sufficient conditions, optimal transport plans on octree coarsened histograms do approximate the true optimal transports with respect to Wp.
Metrics
Details
- Title
- A NORMALIZED BOTTLENECK DISTANCE FOR PERSISTENCE DIAGRAMS AND OCTREE SPATIAL PARTITIONING FOR DISCRETE OPTIMAL TRANSPORT
- Creators
- Nathan Howard May
- Contributors
- Bala Krishnamoorthy (Advisor)Xueying Wang (Committee Member)Kevin Vixie (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Mathematics and Statistics, Department of
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Publisher
- Washington State University
- Number of pages
- 58
- Identifiers
- OCLC#: 1365772768; 99900898734801842
- Language
- English
- Resource Type
- Dissertation