Document Open Access Logo

Strong Collapse for Persistence

Authors Jean-Daniel Boissonnat, Siddharth Pritam, Divyansh Pareek

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.67.pdf
  • Filesize: 490 kB
  • 13 pages

Document Identifiers

Author Details

Jean-Daniel Boissonnat
  • Université Côte d'Azur, INRIA, France
Siddharth Pritam
  • Université Côte d'Azur, INRIA, France
Divyansh Pareek
  • Indian Institute of Technology Bombay, India

Funding

This research has received funding from the European Research Council (ERC) under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement No. 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions).

Cite As Get BibTex

Jean-Daniel Boissonnat, Siddharth Pritam, and Divyansh Pareek. Strong Collapse for Persistence. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 67:1-67:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.67

Abstract

We introduce a fast and memory efficient approach to compute the persistent homology (PH) of a sequence of simplicial complexes. The basic idea is to simplify the complexes of the input sequence by using strong collapses, as introduced by J. Barmak and E. Miniam [DCG (2012)], and to compute the PH of an induced sequence of reduced simplicial complexes that has the same PH as the initial one. Our approach has several salient features that distinguishes it from previous work. It is not limited to filtrations (i.e. sequences of nested simplicial subcomplexes) but works for other types of sequences like towers and zigzags. To strong collapse a simplicial complex, we only need to store the maximal simplices of the complex, not the full set of all its simplices, which saves a lot of space and time. Moreover, the complexes in the sequence can be strong collapsed independently and in parallel. As a result and as demonstrated by numerous experiments on publicly available data sets, our approach is extremely fast and memory efficient in practice.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Algebraic topology
Keywords
  • Computational Topology
  • Topological Data Analysis
  • Strong Collapse
  • Persistent homology

Metrics

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

References

  1. M. Adamaszek and J. Stacho. Complexity of simplicial homology and independence complexes of chordal graphs. Computational Geometry: Theory and Applications, 57:8-18, 2016. Google Scholar
  2. J. A. Barmak and E. G. Minian. Strong homotopy types, nerves and collapses. Discrete and Computational Geometry, 47:301-328, 2012. Google Scholar
  3. Jean-Daniel Boissonnat, C. S. Karthik, and Sébastien Tavenas. Building efficient and compact data structures for simplicial complexes. Algorithmica, 79:530-567, 2017. Google Scholar
  4. Jean-Daniel Boissonnat and Karthik C. S. An efficient representation for filtrations of simplicial complexes. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017. Google Scholar
  5. M. Botnan and G Spreemann. Approximating persistent homology in euclidean space through collapses. In: Applicable Algebra in Engineering, Communication and Computing, 26:73-101, 2014. Google Scholar
  6. Gunnar Carlsson and Vin de Silva. Zigzag persistence. Found Comput Math, 10, 2010. Google Scholar
  7. Gunnar Carlsson, Vin de Silva, and Dmitriy Morozov. Zigzag persistent homology and real-valued functions. SOCG, pages 247-256, 2009. Google Scholar
  8. F. Chazal and S. Oudot. Towards persistence-based reconstruction in euclidean spaces. SOCG, 2008. Google Scholar
  9. Aruni Choudhary, Michael Kerber, and Sharath Raghvendra:. Polynomial-sized topological approximations using the permutahedron. In 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  10. Datasets. URL: https://github.com/n-otter/PH-roadmap/''.
  11. Harm Derksen and Jerzy Weyman. Quiver representations. Notices of the American Mathematical Society, 52(2):200–206, February 2005. Google Scholar
  12. Tamal Dey, Dayu Shi, and Yusu Wang. SimBa: An efficient tool for approximating Rips-filtration persistence via Simplicial Batch-collapse. In European Symp. on Algorithms (ESA), pages 35:1-35:16, 2016. Google Scholar
  13. Dionysus. URL: http://www.mrzv.org/software/dionysus/.
  14. P. Dłotko and H. Wagner. Simplification of complexes for persistent homology computations,. Homology, Homotopy and Applications, 16:49-63, 2014. Google Scholar
  15. François Le Gall. Powers of tensors and fast matrix multiplication. ISSAC ', 14:296-303, 2014. Google Scholar
  16. Gudhi: Geometry understanding in higher dimensions. URL: http://gudhi.gforge.inria.fr/.
  17. A. Hatcher. Algebraic Topology. Univ. Press Cambridge, 2001. Google Scholar
  18. Michael Kerber and Hannah Schreiber:. Barcodes of towers and a streaming algorithm for persistent homology. 33rd International Symposium on Computational Geometry, 2017. URL: http://arxiv.org/abs/1701.02208.
  19. Michael Kerber and R. Sharathkumar. Approximate cech complex in low and high dimensions. In Algorithms and Computation, pages 666-676. by Leizhen Cai, Siu-Wing Cheng, and Tak-Wah Lam. Vol. 8283. Lecture Notes in Computer Science, 2013. Google Scholar
  20. Nikola Milosavljevic, Dmitriy Morozov, and Primoz Skraba. Zigzag persistent homology in matrix multiplication time. In Symposium on Computational Geometry (SoCG), 2011. Google Scholar
  21. K. Mischaikow and V. Nanda. Morse theory for filtrations and efficient computation of persistent homology. DCG, 50:330-353, September 2013. Google Scholar
  22. J. Munkres. Elements of Algebraic Topology. Perseus Publishing, 1984. Google Scholar
  23. N. Otter, M. Porter, U. Tillmann, P. Grindrod, and H. Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, Springer Nature, page 6:17, 2017. Google Scholar
  24. Ripser. URL: https://github.com/Ripser/ripser.
  25. Donald Sheehy. Linear-size approximations to the vietoris-rips filtration. Discrete and Computational Geometry, 49:778-796, 2013. Google Scholar
  26. Sophia. URL: https://bitbucket.org/schreiberh/sophia/.
  27. J.Reininghausc U. Bauer, M. Kerber and Hagner:. Phat – persistent homology algorithms toolbox. Journal of Symbolic Computation, 78, 2017. Google Scholar
  28. J. H. C Whitehead. Simplicial spaces nuclei and m-groups. Proc. London Math. Soc, 45:243-327, 1939. Google Scholar
  29. A. C. Wilkerson, H. Chintakunta, and H. Krim. Computing persistent features in big data: A distributed dimension reduction approach. ICASSP - Proceedings, pages 11-15, 2014. Google Scholar
  30. A. C. Wilkerson, T. J. Moore, and and A. H. Krim A. Swami. Simplifying the homology of networks via strong collapses. ICASSP - Proceedings, 2013. Google Scholar
  31. A. Zomorodian and G. Carlsson. Computing persistent homology. Discrete Comput. Geom, 33:249–274, 2005. 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