de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Geometry Helps to Compare Persistence Diagrams

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44759

Kerber,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Nigmetov,  Arnur
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1606.03357.pdf
(Preprint), 2MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Kerber, M., Morozov, D., & Nigmetov, A. (2016). Geometry Helps to Compare Persistence Diagrams. Retrieved from http://arxiv.org/abs/1606.03357.


Cite as: http://hdl.handle.net/11858/00-001M-0000-002B-029A-6
Abstract
Exploiting geometric structure to improve the asymptotic complexity of discrete assignment problems is a well-studied subject. In contrast, the practical advantages of using geometry for such problems have not been explored. We implement geometric variants of the Hopcroft--Karp algorithm for bottleneck matching (based on previous work by Efrat el al.) and of the auction algorithm by Bertsekas for Wasserstein distance computation. Both implementations use k-d trees to replace a linear scan with a geometric proximity query. Our interest in this problem stems from the desire to compute distances between persistence diagrams, a problem that comes up frequently in topological data analysis. We show that our geometric matching algorithms lead to a substantial performance gain, both in running time and in memory consumption, over their purely combinatorial counterparts. Moreover, our implementation significantly outperforms the only other implementation available for comparing persistence diagrams.