Document Open Access Logo

Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications

Authors Tamal K. Dey, Woojin Kim, Facundo Mémoli

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.34.pdf
  • Filesize: 0.96 MB
  • 17 pages

Document Identifiers

Author Details

Tamal K. Dey
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA
Woojin Kim
  • Department of Mathematics, Duke University, Durham, NC, USA
Facundo Mémoli
  • Department of Mathematics and Department of Computer Science and Engineering, The Ohio State University, Columbus, OH, USA

Funding

This work is supported by NSF grants CCF-2049010, CCF-1740761, DMS-1547357, and IIS-1901360.

Acknowledgements

The authors thank the anonymous reviewers for constructive feedback and suggesting ideas that shortened the proof of Theorem 24.

Cite As Get BibTex

Tamal K. Dey, Woojin Kim, and Facundo Mémoli. Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.34

Abstract

The notion of generalized rank invariant in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. Naturally, computing these rank invariants efficiently is a prelude to computing any of these derived structures efficiently. We show that the generalized rank over a finite interval I of a 𝐙²-indexed persistence module M is equal to the generalized rank of the zigzag module that is induced on a certain path in I tracing mostly its boundary. Hence, we can compute the generalized rank over I by computing the barcode of the zigzag module obtained by restricting the bifiltration inducing M to that path. If the bifiltration and I have at most t simplices and points respectively, this computation takes O(t^ω) time where ω ∈ [2,2.373) is the exponent of matrix multiplication. Among others, we apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module M, determine whether M is interval decomposable and, if so, compute all intervals supporting its summands.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Topology
  • Theory of computation → Computational geometry
Keywords
  • Multiparameter persistent homology
  • Zigzag persistent homology
  • Generalized Persistence Diagrams
  • Möbius inversion

Metrics

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

Related Versions

References

  1. Hideto Asashiba, Mickaël Buchet, Emerson G Escolar, Ken Nakashima, and Michio Yoshiwaki. On interval decomposability of 2d persistence modules. arXiv preprint v2, 2018. URL: http://arxiv.org/abs/1812.05261.
  2. Hideto Asashiba, Emerson G Escolar, Ken Nakashima, and Michio Yoshiwaki. On approximation of 2d-persistence modules by interval-decomposables. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.01637.
  3. Gorô Azumaya. Corrections and supplementaries to my paper concerning Krull-Remak-schmidt’s theorem. Nagoya Mathematical Journal, 1:117-124, 1950. Google Scholar
  4. Ulrich Bauer, Magnus B Botnan, Steffen Oppermann, and Johan Steen. Cotorsion torsion triples and the representation theory of filtered hierarchical clustering. Advances in Mathematics, 369:107171, 2020. Google Scholar
  5. Leo Betthauser, Peter Bubenik, and Parker B Edwards. Graded persistence diagrams and persistence landscapes. Discrete & Computational Geometry, pages 1-28, 2021. Google Scholar
  6. Silvia Biasotti, Andrea Cerri, Patrizio Frosini, Daniela Giorgi, and Claudia Landi. Multidimensional size functions for shape comparison. Journal of Mathematical Imaging and Vision, 32(2):161-179, 2008. Google Scholar
  7. Magnus Botnan, Vadim Lebovici, and Steve Oudot. On Rectangle-Decomposable 2-Parameter Persistence Modules. In 36th International Symposium on Computational Geometry (SoCG 2020), volume 164, pages 22:1-22:16, 2020. Google Scholar
  8. Magnus Botnan and Michael Lesnick. Algebraic stability of zigzag persistence modules. Algebraic & geometric topology, 18(6):3133-3204, 2018. Google Scholar
  9. Magnus Botnan, Steffen Oppermann, and Steve Oudot. Signed barcodes for multi-parameter persistence via rank decompositions and rank-exact resolutions. arXiv preprint, 2021. URL: http://arxiv.org/abs/2107.06800.
  10. Peter Bubenik and Alex Elchesen. Virtual persistence diagrams, signed measures, and wasserstein distance. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.10514.
  11. Chen Cai, Woojin Kim, Facundo Mémoli, and Yusu Wang. Elder-rule-staircodes for augmented metric spaces. SIAM Journal on Applied Algebra and Geometry, 5(3):417-454, 2021. Google Scholar
  12. Gunnar Carlsson and Vin de Silva. Zigzag persistence. Foundations of computational mathematics, 10(4):367-405, 2010. Google Scholar
  13. Gunnar Carlsson and Facundo Mémoli. Multiparameter hierarchical clustering methods. In Classification as a Tool for Research, pages 63-70. Springer, 2010. Google Scholar
  14. Gunnar Carlsson and Afra Zomorodian. The theory of multidimensional persistence. Discrete & Computational Geometry, 42(1):71-93, 2009. Google Scholar
  15. Erin Chambers and David Letscher. Persistent homology over directed acyclic graphs. In Research in Computational Topology, pages 11-32. Springer, 2018. Google Scholar
  16. Jérémy Cochoy and Steve Oudot. Decomposition of exact pfd persistence bimodules. Discrete & Computational Geometry, 63(2):255-293, 2020. Google Scholar
  17. Tamal K. Dey and Tao Hou. Updating zigzag persistence and maintaining representatives over changing filtrations. CoRR, abs/2112.02352, 2021. URL: http://arxiv.org/abs/2112.02352.
  18. Tamal K. Dey, Woojin Kim, and Facundo Mémoli. Computing generalized rank invariant for 2-parameter persistence modules via zigzag persistence and its applications. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.15058.
  19. Tamal K. Dey and Yusu Wang. Computational Topology for Data Analysis. Cambridge University Press, 2022. URL: https://www.cs.purdue.edu/homes/tamaldey/book/CTDAbook/CTDAbook.pdf.
  20. Tamal K Dey and Cheng Xin. Generalized persistence algorithm for decomposing multiparameter persistence modules. Journal of Applied and Computational Topology, pages 1-52, 2022. Google Scholar
  21. Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. American Mathematical Society, January 2010. Google Scholar
  22. Emerson G Escolar and Yasuaki Hiraoka. Persistence modules on commutative ladders of finite type. Discrete & Computational Geometry, 55(1):100-157, 2016. Google Scholar
  23. Pierre Gabriel. Unzerlegbare darstellungen i. Manuscripta Mathematica, pages 71-103, 1972. Google Scholar
  24. Michael Kerber. Multi-parameter persistent homology is practical. In NeurIPS 2020 Workshop on Topological Data Analysis and Beyond, 2020. Google Scholar
  25. Woojin Kim and Facundo Mémoli. Rank invariant for zigzag modules. arXiv preprint v1, 2018. URL: http://arxiv.org/abs/1810.11517.
  26. Woojin Kim and Facundo Mémoli. Generalized persistence diagrams for persistence modules over posets. Journal of Applied and Computational Topology, 5(4):533-581, 2021. Google Scholar
  27. Woojin Kim and Facundo Mémoli. Spatiotemporal persistent homology for dynamic metric spaces. Discrete & Computational Geometry, 66(3):831-875, 2021. Google Scholar
  28. Woojin Kim and Samantha Moore. The generalized persistence diagram encodes the bigraded Betti numbers. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.02551.
  29. Michael Lesnick. Multidimensional interleavings and applications to topological inference. Stanford University, 2012. Google Scholar
  30. Michael Lesnick. The theory of the interleaving distance on multidimensional persistence modules. Foundations of Computational Mathematics, 15(3):613-650, 2015. Google Scholar
  31. Michael Lesnick and Matthew Wright. Interactive visualization of 2-d persistence modules. arXiv preprint, 2015. URL: http://arxiv.org/abs/1512.00180.
  32. Alexander McCleary and Amit Patel. Edit distance and persistence diagrams over lattices. arXiv preprint, 2020. URL: http://arxiv.org/abs/2010.07337.
  33. Ezra Miller. Modules over posets: commutative and homological algebra. arXiv preprint, 2019. URL: http://arxiv.org/abs/1908.09750.
  34. Nikola Milosavljević, Dmitriy Morozov, and Primoz Skraba. Zigzag persistent homology in matrix multiplication time. In Proceedings of the twenty-seventh Annual Symposium on Computational Geometry, pages 216-225, 2011. Google Scholar
  35. Amit Patel. Generalized persistence diagrams. Journal of Applied and Computational Topology, 1(3):397-419, 2018. Google Scholar
  36. Gian-Carlo Rota. On the foundations of combinatorial theory i. theory of Möbius functions. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 2(4):340-368, 1964. Google Scholar
  37. Richard P Stanley. Enumerative combinatorics volume 1 second edition. Cambridge studies in advanced mathematics, 2011. 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