Document Open Access Logo

Exact Computation of the Matching Distance on 2-Parameter Persistence Modules

Authors Michael Kerber , Michael Lesnick , Steve Oudot

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2019.46.pdf
  • Filesize: 461 kB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Algebraic topology
  • Mathematics of computing → Mathematical optimization
Keywords
  • Topological Data Analysis
  • Multi-Parameter Persistence
  • Line arrangements

Metrics

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

Abstract

The matching distance is a pseudometric on multi-parameter persistence modules, defined in terms of the weighted bottleneck distance on the restriction of the modules to affine lines. It is known that this distance is stable in a reasonable sense, and can be efficiently approximated, which makes it a promising tool for practical applications. In this work, we show that in the 2-parameter setting, the matching distance can be computed exactly in polynomial time. Our approach subdivides the space of affine lines into regions, via a line arrangement. In each region, the matching distance restricts to a simple analytic function, whose maximum is easily computed. As a byproduct, our analysis establishes that the matching distance is a rational number, if the bigrades of the input modules are rational.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.46

Author Details

Michael Kerber
  • Graz University of Technology, Graz, Austria
Michael Lesnick
  • University at Albany, SUNY, United States
Steve Oudot
  • Inria Saclay - Île-de-France, Palaiseau, France

Funding

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

Acknowledgements

This work was initiated at the BIRS workshop "Multiparameter Persistent Homology" (18w55140) in Oaxaca, Mexico (Aug. 2018). We thank Jan Reininghaus and the other members of the discussion group on this topic for fruitful initial exchanges. We thank Matthew Wright for helpful discussions about line arrangements, slices, and the computational aspects of 2-parameter persistence.

References

  1. J. Bentley and T. Ottmann. Algorithms for Reporting and Counting Geometric Intersections. IEEE Transactions on Computers, 28:643-647, 1979. Google Scholar
  2. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, Santa Clara, CA, USA, 3rd ed. edition, 2008. Google Scholar
  3. S. Biasotti, A. Cerri, P. Frosini, and D. Giorgi. A new algorithm for computing the 2-dimensional matching distance between size functions. Pattern Recognition Letters, 32(14):1735-1746, 2011. Google Scholar
  4. H. Bjerkevik, M. Botnan, and M. Kerber. Computing the interleaving distance is NP-hard. arXiv, abs/1811.09165, 2018. URL: http://arxiv.org/abs/1811.09165.
  5. G. Carlsson and A. Zomorodian. The theory of multidimensional persistence. Discrete &Computational Geometry, 42(1):71-93, 2009. Google Scholar
  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. R. Corbet and M. Kerber. The representation theorem of persistence revisited and generalized. Journal of Applied and Computational Topology, 2(1):1-31, 2018. Google Scholar
  8. W. Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules. Journal of Algebra and its Applications, 14(05):1550066, 2015. Google Scholar
  9. The RIVET Developers. RIVET: Software for visualization and analysis of 2-parameter persistent homology. http://repo.rivet.online/, 2014-2018.
  10. T. Dey and C. Xin. Computing Bottleneck Distance for 2-D Interval Decomposable Modules. In International Symposium on Computational Geometry (SoCG), pages 32:1-32:15, 2018. Google Scholar
  11. H. Edelsbrunner and J. Harer. Computational Topology: An Introduction. American Mathematical Society, Providence, RI, USA, 2010. Google Scholar
  12. A. Efrat, A. Itai, and M. Katz. Geometry Helps in Bottleneck Matching and Related Problems. Algorithmica, 31(1):1-28, 2001. URL: http://dx.doi.org/10.1007/s00453-001-0016-8.
  13. B. Keller, M. Lesnick, and T. L. Willke. Persistent Homology for Virtual Screening. ChemRxiv preprint, October 2018. Google Scholar
  14. M. Kerber, M. Lesnick, and S. Oudot. Exact computation of the matching distance on 2-parameter persistence modules. CoRR, abs/1812.09085, 2018. Google Scholar
  15. 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
  16. C. Landi. The Rank Invariant Stability via Interleavings. In Research in Computational Topology, pages 1-10. Springer International Publishing, 2018. Google Scholar
  17. M. Lesnick. The theory of the interleaving distance on multidimensional persistence modules. Foundations of Computational Mathematics, 15(3):613-650, 2015. Google Scholar
  18. M. Lesnick and M. Wright. Interactive visualization of 2-D persistence modules. arXiv:1512.00180, 2015. URL: http://arxiv.org/abs/1512.00180.
  19. M. Lesnick and M. Wright. Computing Minimal Presentations and Betti Numbers of 2-Parameter Persistent Homology. arXiv:1902.05708, 2019. URL: http://arxiv.org/abs/1902.05708.
  20. N. Milosavljevic, D. Morozov, and P. Skraba. Zigzag persistent homology in matrix multiplication time. In ACM Symposium on Computational Geometry (SoCG), pages 216-225, 2011. Google Scholar
  21. S. Oudot. Persistence theory: From Quiver Representation to Data Analysis, volume 209 of Mathematical Surveys and Monographs. American Mathematical Society, 2015. Google Scholar
  22. A. Zomorodian and G. Carlsson. Computing persistent homology. Discrete and Computational Geometry, 33(2):249-274, 2005. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact