Document Open Access Logo

Computing Bottleneck Distance for 2-D Interval Decomposable Modules

Authors Tamal K. Dey, Cheng Xin

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.32.pdf
  • Filesize: 0.8 MB
  • 15 pages

Document Identifiers

Author Details

Tamal K. Dey
Cheng Xin

Cite As Get BibTex

Tamal K. Dey and Cheng Xin. Computing Bottleneck Distance for 2-D Interval Decomposable Modules. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.32

Abstract

Computation of the interleaving distance between persistence modules is a central task in topological data analysis. For 1-D persistence modules, thanks to the isometry theorem, this can be done by computing the bottleneck distance with known efficient algorithms. The question is open for most n-D persistence modules, n>1, because of the well recognized complications of the indecomposables. Here, we consider a reasonably complicated class called 2-D interval decomposable modules whose indecomposables may have a description of non-constant complexity. We present a polynomial time algorithm to compute the bottleneck distance for these modules from indecomposables, which bounds the interleaving distance from above, and give another algorithm to compute a new distance called dimension distance that bounds it from below.

Subject Classification

Keywords
  • Persistence modules
  • bottleneck distance
  • interleaving distance

Metrics

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

References

  1. Michael Atiyah. On the krull-schmidt theorem with application to sheaves. Bulletin de la Société Mathématique de France, 84:307-317, 1956. URL: http://eudml.org/doc/86907.
  2. Ulrich Bauer and Michael Lesnick. Induced matchings of barcodes and the algebraic stability of persistence. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG'14, pages 355:355-355:364, 2014. Google Scholar
  3. 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
  4. Håvard Bjerkevik. Stability of higher-dimensional interval decomposable persistence modules. arXiv preprint arXiv:1609.02086, 2016. Google Scholar
  5. Håvard Bjerkevik and Magnus Botnan. Computational complexity of the interleaving distance. arXiv preprint arXiv:1712.04281, 2017. Google Scholar
  6. Magnus Botnan, Justin Curry, and Elizabeth Munch. The poset interleaving distance, 2016. URL: https://jointmathematicsmeetings.org/amsmtgs/2180_abstracts/1125-55-1151.pdf.
  7. Magnus Botnan and Michael Lesnick. Algebraic stability of zigzag persistence modules. arXiv preprint arXiv:1604.00655, 2016. Google Scholar
  8. Peter Bubenik and Jonathan Scott. Categorification of persistent homology. Discrete & Computational Geometry, 51(3):600-627, 2014. Google Scholar
  9. Gunnar Carlsson and Afra Zomorodian. The theory of multidimensional persistence. Discrete & Computational Geometry, 42(1):71-93, Jul 2009. Google Scholar
  10. Andrea Cerri, Barbara Di Fabio, Massimo Ferri, Patrizio Frosini, and Claudia Landi. Betti numbers in multidimensional persistent homology are stable functions. Mathematical Methods in the Applied Sciences, 36(12):1543-1557, 2013. Google Scholar
  11. Andrea Cerri and Patrizio Frosini. A new approximation algorithm for the matching distance in multidimensional persistence. Technical report, February 2011. URL: http://amsacta.unibo.it/2971.
  12. Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas Guibas, and Steve Oudot. Proximity of persistence modules and their diagrams. In Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry, SCG '09, pages 237-246, 2009. Google Scholar
  13. Frédéric Chazal, Vin de Silva, Marc Glisse, and Steve Oudot. The structure and stability of persistence modules. arXiv preprint arXiv:1207.3674, 2012. Google Scholar
  14. Jérémy Cochoy and Steve Oudot. Decomposition of exact pfd persistence bimodules. arXiv preprint arXiv:1605.09726, 2016. Google Scholar
  15. David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete &Computational Geometry, 37(1):103-120, 2007. Google Scholar
  16. William Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules. Journal of Algebra and Its Applications, 14(05):1550066, 2015. URL: http://dx.doi.org/10.1142/S0219498815500668.
  17. Vin de Silva, Elizabeth Munch, and Amit Patel. Categorified reeb graphs. Discrete & Computational Geometry, 55(4):854-906, Jun 2016. Google Scholar
  18. Tamal Dey and Cheng Xin. Computing bottleneck distance for 2-d interval decomposable modules, 2018. URL: http://arxiv.org/abs/1803.02869.
  19. Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. Applied Mathematics. American Mathematical Society, 2010. Google Scholar
  20. Michael Kerber, Dmitriy Morozov, and Arnur Nigmetov. Geometry helps to compare persistence diagrams. Journal of Experimental Algorithmics (JEA), 22(1):1-4, 2017. Google Scholar
  21. Claudia Landi. The rank invariant stability via interleavings. arXiv preprint arXiv:1412.3374, 2014. Google Scholar
  22. Michael Lesnick. The theory of the interleaving distance on multidimensional persistence modules. Foundations of Computational Mathematics, 15(3):613-650, 2015. Google Scholar
  23. Klaus Lux and Magdolna Sźoke. Computing decompositions of modules over finite-dimensional algebras. Experimental Mathematics, 16(1):1-6, 2007. Google Scholar
  24. Steve Oudot. Persistence theory: from quiver representations to data analysis, volume 209. American Mathematical Society, 2015. Google Scholar
  25. Amit Patel. Generalized persistence diagrams. arXiv preprint arXiv:1601.03107, 2016. Google Scholar
  26. Carry Webb. Decomposition of graded modules. Proc. American Math. Soc., 94(4):565-571, 1985. 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 About DROPS Imprint Privacy Contact