LIPIcs.SoCG.2022.60.pdf
- Filesize: 0.78 MB
- 15 pages
Document
Nearly-Doubling Spaces of Persistence Diagrams
Authors
-
Part of:
Volume:
38th International Symposium on Computational Geometry (SoCG 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-01
Cite AsGet BibTex
Donald R. Sheehy and Siddharth S. Sheth. Nearly-Doubling Spaces of Persistence Diagrams. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.60
https://doi.org/10.4230/LIPIcs.SoCG.2022.60
Abstract
The space of persistence diagrams under bottleneck distance is known to have infinite doubling dimension. Because many metric search algorithms and data structures have bounds that depend on the dimension of the search space, the high-dimensionality makes it difficult to analyze and compare asymptotic running times of metric search algorithms on this space.
We introduce the notion of nearly-doubling metrics, those that are Gromov-Hausdorff close to metric spaces of bounded doubling dimension and prove that bounded k-point persistence diagrams are nearly-doubling. This allows us to prove that in some ways, persistence diagrams can be expected to behave like a doubling metric space. We prove our results in great generality, studying a large class of quotient metrics (of which the persistence plane is just one example). We also prove bounds on the dimension of the k-point bottleneck space over such metrics.
The notion of being nearly-doubling in this Gromov-Hausdorff sense is likely of more general interest. Some algorithms that have a dependence on the dimension can be analyzed in terms of the dimension of the nearby metric rather than that of the metric itself. We give a specific example of this phenomenon by analyzing an algorithm to compute metric nets, a useful operation on persistence diagrams.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Topological Data Analysis
- Persistence Diagrams
- Gromov-Hausdorff Distance
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd International Conference on Machine Learning, ICML '06, pages 97-104, New York, NY, USA, 2006. Association for Computing Machinery. URL: https://doi.org/10.1145/1143844.1143857.
- Peter Bubenik and Alex Elchesen. Universality of persistence diagrams and the bottleneck and wasserstein distances, 2021. URL: http://arxiv.org/abs/1912.02563.
- Peter Bubenik and Alex Elchesen. Virtual persistence diagrams, signed measures, wasserstein distances, and banach spaces, 2021. URL: http://arxiv.org/abs/2012.10514.
-
Mathieu Carrière and Steve Oudot. Structure and stability of the 1-dimensional mapper. In SoCG, 2016.
-
Aruni Choudhary and Michael Kerber. Local doubling dimension of point sets. In CCCG 2015 Proceedings, 2015.
-
Kenneth L. Clarkson. Nearest neighbor searching in metric spaces: Experimental results for `sb(s)`. Preliminary version presented at ALENEX99, 2003.
- A. Efrat, A. Itai, and M. J. Katz. Geometry Helps in Bottleneck Matching and Related Problems. Algorithmica, 31(1):1-28, September 2001. URL: https://doi.org/10.1007/s00453-001-0016-8.
- Brittany Terese Fasy, Xiaozhou He, Zhihui Liu, Samuel Micka, David L. Millman, and Binhai Zhu. Approximate Nearest Neighbors in the Space of Persistence Diagrams. arXiv:1812.11257 [cs], March 2021. URL: http://arxiv.org/abs/1812.11257.
-
Misha Gromov. Metric Structure for Riemannian and Non-Riemannian Spaces. Birkhauser, 1999.
- Sariel Har-Peled and Manor Mendel. Fast Construction of Nets in Low-Dimensional Metrics and Their Applications. SIAM Journal on Computing, 35(5):1148-1184, January 2006. URL: https://doi.org/10.1137/S0097539704446281.
- Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu. Epsilon-coresets for clustering (with outliers) in doubling metrics. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 814-825, 2018. URL: https://doi.org/10.1109/FOCS.2018.00082.
- Michael Kerber, Dmitriy Morozov, and Arnur Nigmetov. Geometry Helps to Compare Persistence Diagrams. ACM Journal of Experimental Algorithmics, 22:1-20, December 2017. URL: https://doi.org/10.1145/3064175.
- Michael Kerber and Arnur Nigmetov. Metric spaces with expensive distances. International Journal of Computational Geometry and Applications, 30(02):141-165, June 2020. URL: https://doi.org/10.1142/S0218195920500077.
-
Robert Krauthgamer and James R. Lee. Navigating nets: Simple algorithms for proximity search. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '04, pages 798-807, USA, 2004. Society for Industrial and Applied Mathematics.
- G. G. Lorentz. Metric entropy and approximation. Bulletin of the American Mathematical Society, 72(6):903-937, 1966. URL: https://doi.org/bams/1183528486.
-
Arnur Nigmetov. Comparison of Topological Summaries. PhD thesis, TU Graz, 2019.
-
Don Sheehy and Siddharth Sheth. Sketching persistence diagrams. In SoCG, 2021.
- Donald R. Sheehy. greedypermutations, 2020. URL: https://github.com/donsheehy/greedypermutation.
-
Donald R. Sheehy. One hop greedy permutations. In Proceedings of the 32nd Canadian Conference on Computational Geometry, pages 221-225, 2020.