Document Open Access Logo

Edge Collapse and Persistence of Flag Complexes

Authors Jean-Daniel Boissonnat, Siddharth Pritam

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.19.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).

Acknowledgements

We want to thank Marc Glisse for useful discussions and Vincent Rouvreau for his help with Gudhi.

Cite AsGet BibTex

Jean-Daniel Boissonnat and Siddharth Pritam. Edge Collapse and Persistence of Flag Complexes. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.19

Abstract

In this article, we extend the notions of dominated vertex and strong collapse of a simplicial complex as introduced by J. Barmak and E. Miniam. We say that a simplex (of any dimension) is dominated if its link is a simplicial cone. Domination of edges appears to be a very powerful concept, especially when applied to flag complexes. We show that edge collapse (removal of dominated edges) in a flag complex can be performed using only the 1-skeleton of the complex. Furthermore, the residual complex is a flag complex as well. Next we show that, similar to the case of strong collapses, we can use edge collapses to reduce a flag filtration ℱ to a smaller flag filtration ℱ^c with the same persistence. Here again, we only use the 1-skeletons of the complexes. The resulting method to compute ℱ^c is simple and extremely efficient and, when used as a preprocessing for persistence computation, leads to gains of several orders of magnitude w.r.t the state-of-the-art methods (including our previous approach using strong collapse). The method is exact, irrespective of dimension, and improves performance of persistence computation even in low dimensions. This is demonstrated by numerous experiments on publicly available data.

Subject Classification

ACM Subject Classification
  • Mathematics of computing
  • Theory of computation → Computational geometry
  • Mathematics of computing → Topology
Keywords
  • Computational Topology
  • Topological Data Analysis
  • Edge Collapse
  • Simple 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. Dominique Attali and André Lieutier. Geometry-driven collapses for converting a čech complex into a triangulation of a nicely triangulable shape. Discrete & Computational Geometry, 54(4):798-825, 2015. Google Scholar
  4. Dominique Attali, André Lieutier, and David Salinas. Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes. Computational Geometry, 46(4):448-465, 2013. Google Scholar
  5. J. A. Barmak and E. G. Minian. Strong homotopy types, nerves and collapses. Discrete and Computational Geometry, 47:301-328, 2012. Google Scholar
  6. U. Bauer. Ripser. URL: https://github.com/Ripser/ripser.
  7. 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
  8. U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner. PHAT – persistent homology algorithms toolbox. Journal of Symbolic Computation, 78, 2017. Google Scholar
  9. J-D. Boissonnat and C. S. Karthik. An efficient representation for filtrations of simplicial complexes. In ACM Transactions on Algorithms, 2018. Google Scholar
  10. J-D. Boissonnat, C. S. Karthik, and S. Tavenas. Building efficient and compact data structures for simplicial complexes. Algorithmica, 79:530-567, 2017. Google Scholar
  11. J-D. Boissonnat and S. Pritam. Computing persistent homology of flag complexes via strong collapses. International Symposium on Computational Geometry (SoCG), 2019. Google Scholar
  12. 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
  13. 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
  14. G. Carlsson and V. de Silva. Zigzag persistence. Found Comput Math, 10, 2010. Google Scholar
  15. G. Carlsson, V. de Silva, and D. Morozov. Zigzag persistent homology and real-valued functions. International Symposium on Computational Geometry (SoCG), pages 247-256, 2009. Google Scholar
  16. 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
  17. 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
  18. F. Chazal and S. Oudot. Towards persistence-based reconstruction in Euclidean spaces. International Symposium on Computational Geometry (SoCG), 2008. Google Scholar
  19. C. Chen and M. Kerber. Persistent homology computation with a twist. In European Workshop on Computational Geometry (EuroCG), pages 197-200, 2011. Google Scholar
  20. 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: https://doi.org/10.4230/LIPIcs.SoCG.2016.31.
  21. H. Edelsbrunner D. Cohen-Steiner and J. Harer. Stability of persistence diagrams. Discrete and Compututaional Geometry, 37:103-120, 2007. Google Scholar
  22. Datasets. URL: https://github.com/n-otter/PH-roadmap/.
  23. V. de Silva and R. Ghrist. Coverage in sensor networks via persistent homology. In: Algebraic and Geometric Topology, 7:339 – 358, 2007. Google Scholar
  24. H. Derksen and J. Weyman. Quiver representations. Notices of the American Mathematical Society, 52(2):200–206, February 2005. Google Scholar
  25. 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
  26. T. K. Dey, F. Fan, and Y. Wang. Computing topological persistence for simplicial maps. In International Symposium on Computational Geometry (SoCG), pages 345-354, 2014. Google Scholar
  27. 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
  28. 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
  29. C. H. Dowker. Homology groups of relations. The Annals of Mathematics, 56:84-95, 1952. Google Scholar
  30. P. Dłotko and H. Wagner. Simplification of complexes for persistent homology computations,. Homology, Homotopy and Applications, 16:49-63, 2014. Google Scholar
  31. H. Edelsbrunner and J. Harer. Computational Topology: An Introduction. American Mathematical Society, 2010. Google Scholar
  32. H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete and Compututational Geometry, 28:511–533, 2002. Google Scholar
  33. Omer Egecioglu and Teofilo F. Gonzalez. A computationally intractable problem on simplicial complexes. Computational Geometry, 6:85-98, 1996. Google Scholar
  34. B. T. Fasy, J. Kim, F. Lecci, and C. Maria:. Introduction to the R-package tda. CoRR abs/1411.1830, 2014. URL: http://arxiv.org/abs/1411.1830.
  35. E. Fieux and J. Lacaze. Foldings in graphs and relations with simplicial complexes and posets. Discrete Mathematics, 312(17):2639-2651, 2012. Google Scholar
  36. F. Le Gall. Powers of tensors and fast matrix multiplication. ISSAC ', 14:296-303, 2014. Google Scholar
  37. Gudhi: Geometry understanding in higher dimensions. URL: http://gudhi.gforge.inria.fr/.
  38. A. Hatcher. Algebraic Topology. Univ. Press Cambridge, 2001. Google Scholar
  39. Benoît Hudson, Gary L. Miller, Steve Oudot, and Donald R. Sheehy. Topological inference via meshing. International Symposium on Computational Geometry (SoCG), 2010. Google Scholar
  40. M. Kerber and H. Schreiber:. Barcodes of towers and a streaming algorithm for persistent homology. International Symposium on Computational Geometry (SoCG), 2017. URL: http://arxiv.org/abs/1701.02208.
  41. 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
  42. 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
  43. N. Milosavljevic, D. Morozov, and P. Skraba. Zigzag persistent homology in matrix multiplication time. In International Symposium on Computational Geometry (SoCG), 2011. Google Scholar
  44. 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
  45. D. Mozozov. Dionysus. URL: http://www.mrzv.org/software/dionysus/.
  46. J. Munkres. Elements of Algebraic Topology. Perseus Publishing, 1984. Google Scholar
  47. 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
  48. Steve Y. Oudot and Donald R. Sheehy. Zigzag zoology: Rips zigzags for homology inference. Foundations of Computational Mathematics, 15, 2015. Google Scholar
  49. 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
  50. H. Schreiber. Sophia. URL: https://bitbucket.org/schreiberh/sophia/.
  51. D. Sheehy. Linear-size approximations to the Vietoris-Rips filtration. Discrete and Computational Geometry, 49:778-796, 2013. Google Scholar
  52. M. Tancer. Recognition of collapsible complexes is NP-complete. Discrete and Computational Geometry, 55:21-38, 2016. Google Scholar
  53. Volkmar Welker. Constructions preserving evasiveness and collapsibility. Discrete Mathematics, 207(1):243-255, 1999. Google Scholar
  54. J. H. C Whitehead. Simplicial spaces nuclei and m-groups. Proc. London Math. Soc, 45:243-327, 1939. Google Scholar
  55. 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
  56. 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
  57. A. Zomorodian. The tidy set: A minimal simplicial set for computing homology of clique complexes. In International Symposium on Computational Geometry (SoCG), pages 257-266, 2010. Google Scholar
  58. 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