Document Open Access Logo

On Rectangle-Decomposable 2-Parameter Persistence Modules

Authors Magnus Bakke Botnan, Vadim Lebovici, Steve Oudot

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.22.pdf
  • Filesize: 0.55 MB
  • 16 pages

Document Identifiers

Author Details

Magnus Bakke Botnan
  • Vrije Universiteit Amsterdam, The Netherlands
Vadim Lebovici
  • École Normale Supérieure, Paris, France
Steve Oudot
  • Inria Saclay, Palaiseau, France

Cite As Get BibTex

Magnus Bakke Botnan, Vadim Lebovici, and Steve Oudot. On Rectangle-Decomposable 2-Parameter Persistence Modules. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.22

Abstract

This paper addresses two questions: (1) can we identify a sensible class of 2-parameter persistence modules on which the rank invariant is complete? (2) can we determine efficiently whether a given 2-parameter persistence module belongs to this class? We provide positive answers to both questions, and our class of interest is that of rectangle-decomposable modules. Our contributions include: (a) a proof that the rank invariant is complete on rectangle-decomposable modules, together with an inclusion-exclusion formula for counting the multiplicities of the summands; (b) algorithms to check whether a module induced in homology by a bifiltration is rectangle-decomposable, and to decompose it in the affirmative, with a better complexity than state-of-the-art decomposition methods for general 2-parameter persistence modules. Our algorithms are backed up by a new structure theorem, whereby a 2-parameter persistence module is rectangle-decomposable if, and only if, its restrictions to squares are. This local condition is key to the efficiency of our algorithms, and it generalizes previous conditions from the class of block-decomposable modules to the larger one of rectangle-decomposable modules. It also admits an algebraic formulation that turns out to be a weaker version of the one for block-decomposability. Our analysis focuses on the case of modules indexed over finite grids, the more general cases are left as future work.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Algebraic topology
Keywords
  • topological data analysis
  • multiparameter persistence
  • rank invariant

Metrics

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

Related Versions

References

  1. Gorô Azumaya. Corrections and supplementaries to my paper concerning Krull-Remak-Schmidt’s theorem. Nagoya Mathematical Journal, 1:117-124, 1950. Google Scholar
  2. Ulrich Bauer, Magnus B Botnan, Steffen Oppermann, and Johan Steen. Cotorsion torsion triples and the representation theory of filtered hierarchical clustering. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.07322.
  3. Paul Bendich, Herbert Edelsbrunner, Dmitriy Morozov, Amit Patel, et al. Homology and robustness of level and interlevel sets. Homology, Homotopy and Applications, 15(1):51-72, 2013. Google Scholar
  4. Magnus Bakke Botnan. Interval decomposition of infinite zigzag persistence modules. Proceedings of the American Mathematical Society, 145(8):3571-3577, 2017. Google Scholar
  5. Magnus Bakke Botnan and William Crawley-Boevey. Decomposition of persistence modules. To appear in the Proceedings of the AMS, 2018. URL: http://arxiv.org/abs/1811.08946.
  6. Magnus Bakke Botnan, Vadim Lebovici, and Steve Oudot. On rectangle-decomposable 2-parameter persistence modules, 2020. URL: http://arxiv.org/abs/2002.08894.
  7. Gunnar Carlsson and Vin De Silva. Zigzag persistence. Foundations of computational mathematics, 10(4):367-405, 2010. Google Scholar
  8. Gunnar Carlsson, Vin De Silva, and Dmitriy Morozov. Zigzag persistent homology and real-valued functions. In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 247-256. ACM, 2009. Google Scholar
  9. Frédéric Chazal, Vin De Silva, Marc Glisse, and Steve Oudot. The structure and stability of persistence modules. Springer, 2016. Google Scholar
  10. Jérémy Cochoy and Steve Oudot. Decomposition of exact pfd persistence bimodules. Discrete and Computational Geometry, 2019. To appear, currently available as arXiv preprint URL: https://arxiv.org/abs/1605.09726.
  11. David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103-120, 2007. Google Scholar
  12. William Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules. Journal of Algebra and its Applications, 14(05):1550066, 2015. Google Scholar
  13. Tamal K Dey and Cheng Xin. Generalized persistence algorithm for decomposing multi-parameter persistence modules. arXiv preprint arXiv:1904.03766, 2019. Google Scholar
  14. Herbert Edelsbrunner and John Harer. Persistent homology-a survey. Contemporary mathematics, 453:257-282, 2008. Google Scholar
  15. Emerson G Escolar and Yasuaki Hiraoka. Persistence modules on commutative ladders of finite type. Discrete & Computational Geometry, 55(1):100-157, 2016. Google Scholar
  16. Peter Gabriel. Unzerlegbare Darstellungen I. manuscripta mathematica, 6(1):71-103, March 1972. URL: https://doi.org/10.1007/BF01298413.
  17. Woojin Kim and Facundo Memoli. Generalized persistence diagrams for persistence modules over posets. arXiv preprint arXiv:1810.11517, 2018. Google Scholar
  18. Michael Lesnick and Matthew Wright. Computing minimal presentations and betti numbers of 2-parameter persistent homology. arXiv preprint arXiv:1902.05708, 2019. Google Scholar
  19. 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. ACM, 2011. Google Scholar
  20. Steve Y Oudot. Persistence theory: from quiver representations to data analysis, volume 209. American Mathematical Society Providence, RI, 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 About DROPS Imprint Privacy Contact