Document Open Access Logo

Efficient Approximation of the Matching Distance for 2-Parameter Persistence

Authors Michael Kerber , Arnur Nigmetov

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.53.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Michael Kerber
  • Graz University of Technology, Austria
Arnur Nigmetov
  • Graz University of Technology, Austria

Funding

  • Kerber, Michael: Supported by Austrian Science Fund (FWF) grant number P 29984-N35.

Cite AsGet BibTex

Michael Kerber and Arnur Nigmetov. Efficient Approximation of the Matching Distance for 2-Parameter Persistence. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.53

Abstract

In topological data analysis, the matching distance is a computationally tractable metric on multi-filtered simplicial complexes. We design efficient algorithms for approximating the matching distance of two bi-filtered complexes to any desired precision ε>0. Our approach is based on a quad-tree refinement strategy introduced by Biasotti et al., but we recast their approach entirely in geometric terms. This point of view leads to several novel observations resulting in a practically faster algorithm. We demonstrate this speed-up by experimental comparison and provide our code in a public repository which provides the first efficient publicly available implementation of the matching distance.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • multi-parameter persistence
  • matching distance
  • approximation algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Ulrich Bauer, Michael Kerber, Jan Reininghaus, and Hubert Wagner. Phat - persistent homology algorithms toolbox. J. Symb. Comput., 78:76-90, 2017. URL: https://doi.org/10.1016/j.jsc.2016.03.008.
  2. Silvia Biasotti, Andrea Cerri, Patrizio Frosini, and Daniela Giorgi. A new algorithm for computing the 2-dimensional matching distance between size functions. Pattern Recognition Letters, 32(14):1735-1746, 2011. Google Scholar
  3. Håvard Bjerkevik, Magnus Botnan, and Michael Kerber. Computing the interleaving distance is NP-hard. URL: http://arxiv.org/abs/1811.09165.
  4. G. Carlsson. Topology and data. Bulletin of the AMS, 46:255-308, 2009. Google Scholar
  5. G. Carlsson and A. Zomorodian. The theory of multidimensional persistence. Discrete & Computational Geometry, 42(1):71-93, 2009. URL: https://doi.org/10.1007/s00454-009-9176-0.
  6. A. Cerri, B. Di Fabio, M. Ferri, P. Frosini, and C. Landi. Betti numbers in multidimensional persistent homology are stable functions. Mathematical Methods in the Applied Sciences, 36(12):1543-1557, 2013. Google Scholar
  7. D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37:103-120, 2007. Google Scholar
  8. Tamal Dey and Cheng Xin. Generalized persistence algorithm for decomposing multi-parameter persistence modules. URL: http://arxiv.org/abs/1904.03766.
  9. H. Edelsbrunner and J. Harer. Computational Topology. An Introduction. American Mathematical Society, 2010. Google Scholar
  10. H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete & Computational Geometry, 28(4):511-533, 2002. URL: https://doi.org/10.1007/s00454-002-2885-2.
  11. Bryn Keller, Michael Lesnick, and Theodore L Willke. Persistent homology for virtual screening, 2018. Google Scholar
  12. M. Kerber, D. Morozov, and A. Nigmetov. Geometry helps to compare persistence diagrams. Journal of Experimental Algorithms, 22:1.4:1-1.4:20, September 2017. Google Scholar
  13. Michael Kerber, Michael Lesnick, and Steve Oudot. Exact computation of the matching distance on 2-parameter persistence modules. In 35th International Symposium on Computational Geometry (SoCG 2019), pages 46:1-46:15, 2019. Google Scholar
  14. Michael Kerber and Arnur Nigmetov. Efficient approximation of the matching distance for 2-parameter persistence. arXiv preprint, 2019. URL: http://arxiv.org/abs/1912.05826.
  15. Claudia Landi. The rank invariant stability via interleavings. In Research in Computational Topology, pages 1-10. Springer, 2018. Google Scholar
  16. Michael Lesnick and Matthew Wright. Computing minimal presentations and bigraded betti numbers of 2-parameter persistent homology. URL: http://arxiv.org/abs/1902.05708.
  17. Michael Lesnick and Matthew Wright. Interactive visualization of 2-D persistence modules persistence modules. arXiv, 2015. URL: http://arxiv.org/abs/1512.00180.
  18. S. Oudot. Persistence theory: From Quiver Representation to Data Analysis, volume 209 of Mathematical Surveys and Monographs. American Mathematical Society, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact