Sheehy, Donald R. ;
Sheth, Siddharth S.
NearlyDoubling Spaces of Persistence Diagrams
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 highdimensionality makes it difficult to analyze and compare asymptotic running times of metric search algorithms on this space.
We introduce the notion of nearlydoubling metrics, those that are GromovHausdorff close to metric spaces of bounded doubling dimension and prove that bounded kpoint persistence diagrams are nearlydoubling. 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 kpoint bottleneck space over such metrics.
The notion of being nearlydoubling in this GromovHausdorff 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.
BibTeX  Entry
@InProceedings{sheehy_et_al:LIPIcs.SoCG.2022.60,
author = {Sheehy, Donald R. and Sheth, Siddharth S.},
title = {{NearlyDoubling Spaces of Persistence Diagrams}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {60:160:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16068},
URN = {urn:nbn:de:0030drops160686},
doi = {10.4230/LIPIcs.SoCG.2022.60},
annote = {Keywords: Topological Data Analysis, Persistence Diagrams, GromovHausdorff Distance}
}
01.06.2022
Keywords: 

Topological Data Analysis, Persistence Diagrams, GromovHausdorff Distance 
Seminar: 

38th International Symposium on Computational Geometry (SoCG 2022)

Issue date: 

2022 
Date of publication: 

01.06.2022 