Document Open Access Logo

Efficient Computation of Image Persistence

Authors Ulrich Bauer , Maximilian Schmahl

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.14.pdf
  • Filesize: 0.72 MB
  • 14 pages

Document Identifiers

Author Details

Ulrich Bauer
  • Department of Mathematics, TUM School of Computation, Information and Technology, and Munich Data Science Institute, Technical University of Munich, Germany
  • www.ulrich-bauer.org
Maximilian Schmahl
  • Universität Heidelberg, Germany

Funding

  • Bauer, Ulrich: Supported by the German Research Foundation (DFG) through the Collaborative Research Center SFB/TRR 109 Discretization in Geometry and Dynamics - 195170736.
  • Schmahl, Maximilian: Supported by the German Research Foundation (DFG) through the Collaborative Research Center SFB/TRR 191 Symplectic Structures in Geometry, Algebra and Dynamics - 281071066, the Cluster of Excellence EXC 2181 STRUCTURES - 390900948, and the Research Training Group RTG 2229 Asymptotic Invariants and Limits of Groups and Spaces - 281869850.

Cite As Get BibTex

Ulrich Bauer and Maximilian Schmahl. Efficient Computation of Image Persistence. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.14

Abstract

We present an algorithm for computing the barcode of the image of a morphism in persistent homology induced by an inclusion of filtered finite-dimensional chain complexes. The algorithm makes use of the clearing optimization and can be applied to inclusion-induced maps in persistent absolute homology and persistent relative cohomology for filtrations of pairs of simplicial complexes. The clearing optimization works particularly well in the context of relative cohomology, and using previous duality results we can translate the barcodes of images in relative cohomology to those in absolute homology. This forms the basis for an implementation of image persistence computations for inclusions of filtrations of Vietoris-Rips complexes in the framework of the software Ripser.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Algebraic topology
  • Theory of computation → Computational geometry
Keywords
  • Persistent homology
  • image persistence
  • barcode computation

Metrics

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

Related Versions

Supplementary Materials

References

  1. Ulrich Bauer. Ripser: efficient computation of Vietoris-Rips persistence barcodes. J. Appl. Comput. Topol., 5(3):391-423, 2021. URL: https://doi.org/10.1007/s41468-021-00071-5.
  2. Ulrich Bauer and Michael Lesnick. Induced matchings and the algebraic stability of persistence barcodes. J. Comput. Geom., 6(2):162-191, 2015. URL: https://doi.org/10.20382/jocg.v6i2a9.
  3. Ulrich Bauer and Michael Lesnick. Persistence diagrams as diagrams: A categorification of the stability theorem. In Nils A. Baas, Gunnar E. Carlsson, Gereon Quick, Markus Szymik, and Marius Thaule, editors, Topological Data Analysis, pages 67-96, Cham, 2020. Springer. URL: https://doi.org/10.1007/978-3-030-43408-3_3.
  4. Ulrich Bauer and Maximilian Schmahl. Efficient computation of image persistence. Preprint, 2022. URL: https://arxiv.org/abs/2201.04170.
  5. Ulrich Bauer and Maximilian Schmahl. Lifespan functors and natural dualities in persistent homology. Homology Homotopy Appl., 2023. To appear. URL: https://arxiv.org/abs/2012.12881.
  6. Ulrich Bauer and Maximilian Schmahl. Ripser for image persistence, 2023. GitHub. URL: https://github.com/Ripser/ripser/tree/image-persistence-simple.
  7. Michael Bleher, Lukas Hahn, Juan Angel Patino-Galindo, Mathieu Carriere, Ulrich Bauer, Raul Rabadan, and Andreas Ott. Topology identifies emerging adaptive mutations in sars-cov-2. Preprint, 2021. URL: https://arxiv.org/abs/2106.07292.
  8. Frédéric Chazal, Vin de Silva, Marc Glisse, and Steve Oudot. The structure and stability of persistence modules. SpringerBriefs in Mathematics. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-42545-0.
  9. Chao Chen and Michael Kerber. Persistent homology computation with a twist. In Proceedings of the 27th European Workshop on Computational Geometry, 2011. URL: https://eurocg11.inf.ethz.ch/abstracts/22.pdf.
  10. James Clough, Nicholas Byrne, Ilkay Oksuz, Veronika Zimmer, Julia Schnabel, and Andrew King. A topological loss function for deep-learning based image segmentation using persistent homology. IEEE transactions on pattern analysis and machine intelligence, PP, September 2020. URL: https://doi.org/10.1109/TPAMI.2020.3013679.
  11. David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete Comput. Geom., 37(1):103-120, 2007. URL: https://doi.org/10.1007/s00454-006-1276-5.
  12. David Cohen-Steiner, Herbert Edelsbrunner, John Harer, and Dmitriy Morozov. Persistent homology for kernels, images, and cokernels. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1011-1020. SIAM, Philadelphia, PA, 2009. URL: https://doi.org/10.1137/1.9781611973068.110.
  13. David Cohen-Steiner, Herbert Edelsbrunner, and Dmitriy Morozov. Vines and vineyards by updating persistence in linear time. In Computational geometry (SCG'06), pages 119-126. ACM, New York, 2006. URL: https://doi.org/10.1145/1137856.1137877.
  14. William Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules. J. Algebra Appl., 14(5):1550066, 8, 2015. URL: https://doi.org/10.1142/S0219498815500668.
  15. Y. Dabaghian, F. Mémoli, L. Frank, and G. Carlsson. A topological paradigm for hippocampal spatial map formation using persistent homology. PLOS Computational Biology, 8(8):1-14, August 2012. URL: https://doi.org/10.1371/journal.pcbi.1002581.
  16. Vin de Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson. Dualities in persistent (co)homology. Inverse Problems, 27(12):124003, 17, 2011. URL: https://doi.org/10.1088/0266-5611/27/12/124003.
  17. Inés García-Redondo, Anthea Monod, and Anna Song. Fast topological signal identification and persistent cohomological cycle matching. Preprint, 2022. URL: https://arxiv.org/abs/2209.15446.
  18. Xiaoling Hu, Fuxin Li, Dimitris Samaras, and Chao Chen. Topology-preserving deep image segmentation. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL: https://proceedings.neurips.cc/paper/2019/file/2d95666e2649fcfc6e3af75e09f5adb9-Paper.pdf.
  19. Dmitriy Morozov. Dionysus. URL: https://mrzv.org/software/dionysus/.
  20. Takenobu Nakamura, Yasuaki Hiraoka, Akihiko Hirata, Emerson G Escolar, and Yasumasa Nishiura. Persistent homology and many-body atomic structure for medium-range order in the glass. Nanotechnology, 26(30):304001, 2015. URL: https://doi.org/10.1088/0957-4484/26/30/304001.
  21. Y. Reani and O. Bobrowski. Cycle registration in persistent homology with applications in topological bootstrap. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2022. URL: https://doi.org/10.1109/TPAMI.2022.3217443.
  22. Nico Stucki, Johannes C. Paetzold, Suprosanna Shit, Bjoern Menze, and Ulrich Bauer. Topologically faithful image segmentation via induced matching of persistence barcodes. To appear in the proceedings of ICML 2023. Preprint, 2022. URL: https://arxiv.org/abs/2211.15272.
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