Document Open Access Logo

Barcodes of Towers and a Streaming Algorithm for Persistent Homology

Authors Michael Kerber, Hannah Schreiber

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.57.pdf
  • Filesize: 0.62 MB
  • 16 pages

Document Identifiers

Author Details

Michael Kerber
Hannah Schreiber

Cite AsGet BibTex

Michael Kerber and Hannah Schreiber. Barcodes of Towers and a Streaming Algorithm for Persistent Homology. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.57

Abstract

A tower is a sequence of simplicial complexes connected by simplicial maps. We show how to compute a filtration, a sequence of nested simplicial complexes, with the same persistent barcode as the tower. Our approach is based on the coning strategy by Dey et al. (SoCG 2014). We show that a variant of this approach yields a filtration that is asymptotically only marginally larger than the tower and can be efficiently computed by a streaming algorithm, both in theory and in practice. Furthermore, we show that our approach can be combined with a streaming algorithm to compute the barcode of the tower via matrix reduction. The space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower. Experimental evaluations show that our approach can efficiently handle towers with billions of complexes.
Keywords
  • Persistent Homology
  • Topological Data Analysis
  • Matrix reduction
  • Streaming algorithms
  • Simplicial Approximation

Metrics

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

References

  1. 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
  2. U. Bauer, M. Kerber, and J. Reininghaus. Distributed Computation of Persistent Homology. In Workshop on Algorithm Engineering and Experiments (ALENEX), pages 31-38, 2014. Google Scholar
  3. U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner. Phat - Persistent Homology Algorithms Toolbox. Journal of Symbolic Computation, 78:76-90, 2017. Google Scholar
  4. J.-D. Boissonnat, T. Dey, and C. Maria. The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology. In European Symp. on Algorithms (ESA), pages 695-706, 2013. Google Scholar
  5. M. Botnan and G. Spreemann. Approximating Persistent Homology in Euclidean space through collapses. Applied Algebra in Engineering, Communication and Computing, 26:73-101, 2015. Google Scholar
  6. G. Carlsson. Topology and Data. Bulletin of the AMS, 46:255-308, 2009. Google Scholar
  7. G. Carlsson, V. de Silva, and D. Morozov. Zigzag Persistent Homology and Real-valued Functions. In ACM Symp. on Computational Geometry (SoCG), pages 247-256, 2009. Google Scholar
  8. C. Chen and M. Kerber. Persistent Homology Computation With a Twist. In European Workshop on Computational Geometry (EuroCG), pages 197-200, 2011. Google Scholar
  9. C. Chen and M. Kerber. An output-sensitive algorithm for persistent homology. Computational Geometry: Theory and Applications, 46:435-447, 2013. Google Scholar
  10. A. Choudhary, M. Kerber, and S. Raghvendra. Polynomial-Sized Topological Approximations Using The Permutahedron. In 32nd Int. Symp. on Computational Geometry (SoCG), pages 31:1-31:16, 2016. Google Scholar
  11. T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to algorithms. The MIT press, 3rd edition, 2009. Google Scholar
  12. V. de Silva, D. Morozov, and M. Vejdemo-Johansson. Dualities in persistent (co)homology. Inverse Problems, 27:124003, 2011. Google Scholar
  13. T. Dey, F. Fan, and Y. Wang. Computing Topological Persistence for Simplicial Maps. In ACM Symp. on Computational Geometry (SoCG), pages 345-354, 2014. Google Scholar
  14. T. 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
  15. H. Edelsbrunner and J. Harer. Computational Topology: an introduction. American Mathematical Society, 2010. Google Scholar
  16. H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological Persistence and Simplification. Discrete &Computational Geometry, 28:511-533, 2002. Google Scholar
  17. H. Edelsbrunner and S. Parsa. On the Computational Complexity of Betti Numbers: Reductions from Matrix Rank. In ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 152-160, 2014. Google Scholar
  18. M. Kerber. Persistent Homology: State of the art and challenges. Internationale Mathematische Nachrichten, 231:15-33, 2016. Google Scholar
  19. M. Kerber and H. Schreiber. Barcodes of Towers and a Streaming Algorithm for Persistent Homology. arXiv, abs/1701.02208, 2017. URL: http://arxiv.org/abs/1701.02208.
  20. M. Kerber and R. Sharathkumar. Approximate Čech Complex in Low and High Dimensions. In Int. Symp. on Algortihms and Computation (ISAAC), pages 666-676, 2013. Google Scholar
  21. C. Maria, J.-D. Boissonnat, M. Glisse, and M. Yvinec. The Gudhi Library: Simplicial Complexes and Persistent Homology. In Int. Congress on Mathematical Software (ICMS), volume 8592 of Lecture Notes in Computer Science, pages 167-174, 2014. Google Scholar
  22. C. Maria and S. Oudot. Zigzag Persistence via Reflections and Transpositions. In ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 181-199, 2015. Google Scholar
  23. N. Milosavljevic, D. Morozov, and P. Skraba. Zigzag persistent homology in matrix multiplication time. In ACM Symp. on Computational Geometry (SoCG), pages 216-225, 2011. Google Scholar
  24. N. Otter, M. Porter, U. Tillmann, P. Grindrod, and H. Harrington. A roadmap for the computation of persistent homology. arXiv, abs/1506.08903, 2015. Google Scholar
  25. S. Oudot. Persistence theory: From Quiver Representation to Data Analysis, volume 209 of Mathematical Surveys and Monographs. American Mathematical Society, 2015. Google Scholar
  26. D. Sheehy. Linear-size approximation to the Vietoris-Rips Filtration. Discrete &Computational Geometry, 49:778-796, 2013. Google Scholar
  27. A. Zomorodian and G. Carlsson. Computing Persistent Homology. Discrete & 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