Document Open Access Logo

Computing Persistent Homology of Flag Complexes via Strong Collapses

Authors Jean-Daniel Boissonnat, Siddharth Pritam

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.55.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Jean-Daniel Boissonnat
  • Université Côte d'Azur, INRIA, Sophia Antipolis, France
Siddharth Pritam
  • Université Côte d'Azur, INRIA, Sophia Antipolis, France

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 AsGet BibTex

Jean-Daniel Boissonnat and Siddharth Pritam. Computing Persistent Homology of Flag Complexes via Strong Collapses. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.55

Abstract

In this article, we focus on the problem of computing Persistent Homology of a flag tower, i.e. a sequence of flag complexes connected by simplicial maps. We show that if we restrict the class of simplicial complexes to flag complexes, we can achieve decisive improvement in terms of time and space complexities with respect to previous work. We show that strong collapses of flag complexes can be computed in time O(k^2v^2) where v is the number of vertices of the complex and k is the maximal degree of its graph. Moreover we can strong collapse a flag complex knowing only its 1-skeleton and the resulting complex is also a flag complex. When we strong collapse the complexes in a flag tower, we obtain a reduced sequence that is also a flag tower we call the core flag tower. We then convert the core flag tower to an equivalent filtration to compute its PH. Here again, we only use the 1-skeletons of the complexes. The resulting method is simple and extremely efficient.

Subject Classification

ACM Subject Classification
  • Mathematics of computing
  • Theory of computation → Computational geometry
  • 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. D. Attali, A. Lieutier, and D. Salinas. Efficient data structure for representing and simplifying simplicial complexes in high dimensions. International Journal of Computational Geometry and Applications (IJCGA), 22:279-303, 2012. Google Scholar
  3. J. A. Barmak and E. G. Minian. Strong homotopy types, nerves and collapses. Discrete and Computational Geometry, 47:301-328, 2012. Google Scholar
  4. U. Bauer. Ripser. URL: https://github.com/Ripser/ripser.
  5. U. Bauer, M. Kerber, and J. Reininghaus. Clear and compress: Computing persistent homology in chunks. In Topological Methods in Data Analysis and Visualization III, Mathematics and Visualization, pages 103-117. Springer, 2014. Google Scholar
  6. U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner. PHAT – persistent homology algorithms toolbox. Journal of Symbolic Computation, 78, 2017. Google Scholar
  7. J-D. Boissonnat and C. S. Karthik. An Efficient Representation for Filtrations of Simplicial Complexes. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017. Google Scholar
  8. J-D. Boissonnat, S.Pritam, and D. Pareek. Strong Collapse for Persistence. In 26th Annual European Symposium on Algorithms (ESA 2018), volume 112, 2018. Google Scholar
  9. M. Botnan and G. Spreemann. Approximating persistent homology in Euclidean space through collapses. Applicable Algebra in Engineering, Communication and Computing, 26:73-101, 2015. Google Scholar
  10. G. Carlsson and V. de Silva. Zigzag Persistence. Found Comput Math, 10, 2010. Google Scholar
  11. G. Carlsson, V. de Silva, and D. Morozov. Zigzag persistent homology and real-valued functions. SOCG, pages 247-256, 2009. Google Scholar
  12. G. Carlsson, T. Ishkhanov, V. de Silva, and A. Zomorodian. On the Local Behavior of Spaces of Natural Images. In: International Journal of Computer Vision, 76:1–12, 2008. Google Scholar
  13. J. M. Chan, G. Carlsson, and R. Rabadan. Topology of viral evolution. In: Proceedings of the National Academy of Sciences, 110:18566–18571, 2013. Google Scholar
  14. F. Chazal and S. Oudot. Towards Persistence-Based Reconstruction in Euclidean Spaces. SOCG, 2008. Google Scholar
  15. C. Chen and M. Kerber. Persistent homology computation with a twist. In European Workshop on Computational Geometry (EuroCG), pages 197-200, 2011. Google Scholar
  16. Aruni Choudhary, Michael Kerber, and Sharath Raghvendra. Polynomial-Sized Topological Approximations Using the Permutahedron. In Sándor Fekete and Anna Lubiw, editors, 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:16, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://drops.dagstuhl.de/opus/volltexte/2016/5923, URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.31.
  17. H. Edelsbrunner D. Cohen-Steiner and J. Harer. Stability of Persistence Diagrams. Discrete and Compututaional Geometry, 37:103-120, 2007. Google Scholar
  18. Datasets. URL: https://github.com/n-otter/PH-roadmap/''.
  19. V. de Silva and R. Ghrist. Coverage in sensor networks via persistent homology. In: Algebraic and Geometric Topology, 7:339 – 358, 2007. Google Scholar
  20. H. Derksen and J. Weyman. Quiver representations. Notices of the American Mathematical Society, 52(2):200–206, February 2005. Google Scholar
  21. T. K. Dey, H. Edelsbrunner, S. Guha, and D. Nekhayev. Topology preserving edge contraction. Publications de l'Institut Mathematique (Beograd), 60:23-45, 1999. Google Scholar
  22. T. K. Dey, F. Fan, and Y. Wang. Computing Topological Persistence for Simplicial Maps. In Symposium on Computational Geometry (SoCG, pages 345-354, 2014. Google Scholar
  23. T. K. Dey, D. Shi, and Y. 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
  24. T. K. Dey and R. Slechta. Filtration Simplification for Persistent Homology via Edge Contraction. International Conference on Discrete Geometry for Computer Imagery, 2019. Google Scholar
  25. C. H. Dowker. Homology groups of relations. The Annals of Mathematics, 56:84-95, 1952. Google Scholar
  26. P. Dłotko and H. Wagner. Simplification of complexes for persistent homology computations,. Homology, Homotopy and Applications, 16:49-63, 2014. Google Scholar
  27. H. Edelsbrunner and J. Harer. Computational Topology: An Introduction. American Mathematical Society, 2010. Google Scholar
  28. H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete and Compututational Geometry, 28:511–533, 2002. Google Scholar
  29. B. T. Fasy, J. Kim, F. Lecci, and C. Maria:. Introduction to the R package TDA. CoRR abs/1411.1830, 2014. Google Scholar
  30. E. Fieux and J. Lacaze. Foldings in graphs and relations with simplicial complexes and posets. Discrete Mathematics, 312(17):2639-2651, 2012. Google Scholar
  31. F. Le Gall. Powers of tensors and fast matrix multiplication. ISSAC ', 14:296-303, 2014. Google Scholar
  32. Gudhi: Geometry understanding in Higher Dimensions. URL: http://gudhi.gforge.inria.fr/.
  33. A. Hatcher. Algebraic Topology. Univ. Press Cambridge, 2001. Google Scholar
  34. C. S. Karthik J-D. Boissonnat and S. Tavenas. Building Efficient and Compact Data Structures for Simplicial Complexes. Algorithmica, 79:530-567, 2017. Google Scholar
  35. M. Kerber and H. 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.
  36. M. Kerber and R. Sharathkumar. Approximate Čech 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
  37. C. Maria and S. Oudot. Zigzag Persistence via Reflections and Transpositions. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 181–199, January 2015. Google Scholar
  38. N. Milosavljevic, D. Morozov, and P. Skraba. Zigzag persistent homology in matrix multiplication time. In Symposium on Computational Geometry (SoCG), 2011. Google Scholar
  39. K. Mischaikow and V. Nanda. Morse Theory for Filtrations and Efficient Computation of Persistent Homology. Discrete and Computational Geometry, 50:330-353, September 2013. Google Scholar
  40. D. Mozozov. Dionysus. URL: http://www.mrzv.org/software/dionysus/.
  41. J. Munkres. Elements of Algebraic Topology. Perseus Publishing, 1984. Google Scholar
  42. 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
  43. J. Perea and G. Carlsson. A Klein-Bottle-Based Dictionary for Texture Representation. In: International Journal of Computer Vision, 107:75–97, 2014. Google Scholar
  44. H. Schreiber. Sophia. URL: https://bitbucket.org/schreiberh/sophia/.
  45. D. Sheehy. Linear-Size Approximations to the Vietoris-Rips Filtration. Discrete and Computational Geometry, 49:778-796, 2013. Google Scholar
  46. M. Tancer. Recognition of collapsible complexes is NP-complete. Discrete and Computational Geometry, 55:21-38, 2016. Google Scholar
  47. J. H. C Whitehead. Simplicial spaces nuclei and m-groups. Proc. London Math. Soc, 45:243-327, 1939. Google Scholar
  48. A. C. Wilkerson, H. Chintakunta, and H. Krim. Computing persistent features in big data: A distributed dimension reduction approach. In International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pages 11-15, 2014. Google Scholar
  49. A. C. Wilkerson, T. J. Moore, A. Swami, and A. H. Krim. Simplifying the homology of networks via strong collapses. In International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pages 11-15, 2013. Google Scholar
  50. A. Zomorodian. The Tidy Set: A Minimal Simplicial Set for Computing Homology of Clique Complexes. In Proceedings of the Twenty-sixth Annual Symposium on Computational Geometry, pages 257-266, 2010. Google Scholar
  51. A. Zomorodian and G. Carlsson. Computing persistent homology. Discrete and Computational Geometry, 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 Imprint Privacy Contact