Document Open Access Logo

Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets

Authors Ángel Javier Alonso , Michael Kerber

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.7.pdf
  • Filesize: 0.83 MB
  • 16 pages

Document Identifiers

Author Details

Ángel Javier Alonso
  • Technische Universität Graz, Austria
Michael Kerber
  • Technische Universität Graz, Austria

Funding

This research has been supported by the Austrian Science Fund (FWF) grant P 33765-N.

Acknowledgements

The authors thank Jan Jendrysiak for helpful discussions. We are also grateful to the anonymous reviewers for their careful reading of our manuscript and their detailed comments and suggestions.

Cite AsGet BibTex

Ángel Javier Alonso and Michael Kerber. Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.7

Abstract

We study the decomposition of zero-dimensional persistence modules, viewed as functors valued in the category of vector spaces factorizing through sets. Instead of working directly at the level of vector spaces, we take a step back and first study the decomposition problem at the level of sets. This approach allows us to define the combinatorial notion of rooted subsets. In the case of a filtered metric space M, rooted subsets relate the clustering behavior of the points of M with the decomposition of the associated persistence module. In particular, we can identify intervals in such a decomposition quickly. In addition, rooted subsets can be understood as a generalization of the elder rule, and are also related to the notion of constant conqueror of Cai, Kim, Mémoli and Wang. As an application, we give a lower bound on the number of intervals that we can expect in the decomposition of zero-dimensional persistence modules of a density-Rips filtration in Euclidean space: in the limit, and under very general circumstances, we can expect that at least 25% of the indecomposable summands are interval modules.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Topology
  • Theory of computation → Computational geometry
Keywords
  • Multiparameter persistent homology
  • Clustering
  • Decomposition of persistence modules
  • Elder Rule

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. Computational Geometry, 105/106:Paper No. 101879, 33, 2022. URL: https://doi.org/10.1016/j.comgeo.2022.101879.
  2. 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, 51, 2020. URL: https://doi.org/10.1016/j.aim.2020.107171.
  3. Ulrich Bauer and Luis Scoccola. Generic two-parameter persistence modules are nearly indecomposable, November 2022. URL: https://arxiv.org/abs/2211.15306.
  4. Håvard Bakke Bjerkevik, Magnus Bakke Botnan, and Michael Kerber. Computing the interleaving distance is NP-hard. Foundations of Computational Mathematics, 20(5):1237-1271, 2020. URL: https://doi.org/10.1007/s10208-019-09442-y.
  5. Andrew J. Blumberg and Michael Lesnick. Stability of 2-parameter persistent homology. Foundations of Computational Mathematics, 2022. URL: https://doi.org/10.1007/s10208-022-09576-6.
  6. Magnus Bakke Botnan and William Crawley-Boevey. Decomposition of persistence modules. Proceedings of the American Mathematical Society, 148(11):4581-4596, 2020. URL: https://doi.org/10.1090/proc/14790.
  7. Magnus Bakke Botnan and Michael Lesnick. Algebraic stability of zigzag persistence modules. Algebraic & Geometric Topology, 18(6):3133-3204, 2018. URL: https://doi.org/10.2140/agt.2018.18.3133.
  8. Magnus Bakke Botnan, Steffen Oppermann, Steve Oudot, and Luis Scoccola. On the bottleneck stability of rank decompositions of multi-parameter persistence modules, July 2022. URL: https://arxiv.org/abs/2208.00300.
  9. Michel Brion. Representations of quivers. In Geometric methods in representation theory. I, volume 24 of Sémin. Congr., pages 103-144. Soc. Math. France, Paris, 2012. Google Scholar
  10. Jacek Brodzki, Matthew Burfitt, and Mariam Pirashvili. On the complexity of zero-dimensional multiparameter persistence, August 2020. URL: https://arxiv.org/abs/2008.11532.
  11. Mickaël Buchet, Frédéric Chazal, Tamal K. Dey, Fengtao Fan, Steve Y. Oudot, and Yusu Wang. Topological analysis of scalar fields with outliers. In 31st International Symposium on Computational Geometry, volume 34 of LIPIcs. Leibniz Int. Proc. Inform., pages 827-841, 2015. URL: https://doi.org/10.4230/LIPIcs.SOCG.2015.827.
  12. Mickaël Buchet and Emerson G. Escolar. Every 1D persistence module is a restriction of some indecomposable 2D persistence module. Journal of Applied and Computational Topology, 4(3):387-424, 2020. URL: https://doi.org/10.1007/s41468-020-00053-z.
  13. Mickaël Buchet and Emerson G. Escolar. Realizations of indecomposable persistence modules of arbitrarily large dimension. Journal of Computational Geometry, 13(1):298-326, 2022. URL: https://doi.org/10.20382/jocg.v13i1a12.
  14. 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. URL: https://doi.org/10.1137/20M1353605.
  15. Gunnar Carlsson and Facundo Mémoli. Characterization, stability and convergence of hierarchical clustering methods. Journal of Machine Learning Research, 11:1425-1470, 2010. Google Scholar
  16. Gunnar Carlsson and Facundo Mémoli. Multiparameter hierarchical clustering methods. In Classification as a tool for research, Stud. Classification Data Anal. Knowledge Organ., pages 63-70. Springer, Berlin, 2010. URL: https://doi.org/10.1007/978-3-642-10745-0_6.
  17. Gunnar Carlsson and Facundo Mémoli. Classifying clustering schemes. Foundations of Computational Mathematics, 13(2):221-252, 2013. URL: https://doi.org/10.1007/s10208-012-9141-9.
  18. Gunnar Carlsson and Afra Zomorodian. The theory of multidimensional persistence. Discrete & Computational Geometry, 42(1):71-93, 2009. URL: https://doi.org/10.1007/s00454-009-9176-0.
  19. Kenneth L. Clarkson. Fast algorithms for the all nearest neighbors problem. In 24th Annual Symposium on Foundations of Computer Science, pages 226-232. IEEE, 1983. URL: https://doi.org/10.1109/SFCS.1983.16.
  20. Anne Collins, Afra Zomorodian, Gunnar Carlsson, and Leonidas J. Guibas. A barcode shape descriptor for curve point cloud data. Computers & Graphics, 28(6):881-894, 2004. URL: https://doi.org/10.1016/j.cag.2004.08.015.
  21. Trevor F. Cox. Reflexive nearest neighbours. Biometrics, 37(2):367, 1981. URL: https://doi.org/10.2307/2530424.
  22. Justin Curry. The fiber of the persistence map for functions on the interval. Journal of Applied and Computational Topology, 2(3-4):301-321, 2018. URL: https://doi.org/10.1007/s41468-019-00024-z.
  23. Tamal K. Dey and Cheng Xin. Generalized persistence algorithm for decomposing multiparameter persistence modules. Journal of Applied and Computational Topology, 6(3):271-322, 2022. URL: https://doi.org/10.1007/s41468-022-00087-5.
  24. Herbert Edelsbrunner and John L. Harer. Computational topology: an introduction. American Mathematical Society, Providence, RI, 2010. URL: https://doi.org/10.1090/mbk/069.
  25. David Eppstein, Michael S. Paterson, and Frances F. Yao. On nearest-neighbor graphs. Discrete & Computational Geometry, 17(3):263-282, 1997. URL: https://doi.org/10.1007/PL00009293.
  26. Norbert Henze. On the probability that a random point is the j th nearest neighbour to its own k th nearest neighbour. Journal of Applied Probability, 23(1):221-226, 1986. URL: https://doi.org/10.2307/3214132.
  27. Norbert Henze. On the fraction of random points by specified nearest-neighbour interrelations and degree of attraction. Advances in Applied Probability, 19(4):873-895, 1987. URL: https://doi.org/10.2307/1427106.
  28. Jon Kleinberg. An impossibility theorem for clustering. In Advances in Neural Information Processing Systems, volume 15. MIT Press, 2002. Google Scholar
  29. Michael Lesnick and Matthew Wright. Interactive visualization of 2-d persistence modules, December 2015. URL: https://arxiv.org/abs/1512.00180.
  30. Saunders Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer New York, 1978. URL: https://doi.org/10.1007/978-1-4757-4721-8.
  31. Leland McInnes and John Healy. Accelerated hierarchical density clustering. In 2017 IEEE International Conference on Data Mining Workshops, pages 33-42, 2017. URL: https://doi.org/10.1109/ICDMW.2017.12.
  32. Samantha Moore. Hyperplane restrictions of indecomposable n-dimensional persistence modules. Homology, Homotopy and Applications, 24(2):291-305, 2022. URL: https://doi.org/10.4310/HHA.2022.v24.n2.a14.
  33. Alexander Rolle and Luis Scoccola. Persistable: Persistent and stable clustering. URL: https://github.com/LuisScoccola/persistable.
  34. Alexander Rolle and Luis Scoccola. Stable and consistent density-based clustering, July 2021. URL: https://arxiv.org/abs/2005.09048.
  35. Mark F. Schilling. Mutual and shared neighbor probabilities: finite- and infinite-dimensional results. Advances in Applied Probability, 18(2):388-405, 1986. URL: https://doi.org/10.2307/1427305.
  36. Bernard W. Silverman. Density estimation for statistics and data analysis. Monographs on Statistics and Applied Probability. Chapman & Hall, London, 1986. Google Scholar
  37. Pravin M. Vaidya. An O(nlog n) algorithm for the all-nearest-neighbors problem. Discrete & Computational Geometry, 4(2):101-115, 1989. URL: https://doi.org/10.1007/BF02187718.
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