Distributing Persistent Homology via Spectral Sequences
Pages 580 - 619
Abstract
We set up the theory for a distributed algorithm for computing persistent homology. For this purpose we develop linear algebra of persistence modules. We present bases of persistence modules, together with an operation that leads to a method for obtaining images, kernels and cokernels of tame persistence morphisms. Our focus is on developing efficient methods for the computation of homology of chains of persistence modules. Later we give a brief, self-contained presentation of the Mayer–Vietoris spectral sequence. Then we study the Persistent Mayer–Vietoris spectral sequence and present a solution to the extension problem. This solution is given by finding coefficients that indicate gluings between bars on the same dimension. Finally, we review PerMaViss, an algorithm that computes all pages in the spectral sequence and solves the extension problem. This procedure distributes computations on subcomplexes, while focusing on merging homological information. Additionally, some computational bounds are found which confirm the distribution of the method.
References
[1]
Adams, H., Emerson, T., Kirby, M., Neville, R., Peterson, C., Shipman, P., Chepushtanova, S., Han-son, E., Motta, F., Ziegelmeier, L.: Persistence images: a stable vector representation of persistent homology. J. Mach. Learn. Res. 18, # 8 (2017)
[2]
Bauer, U., Kerber, M., Reininghaus, J.: Clear and compress: computing persistent homology in chunks. In: Topological Methods in Data Analysis and Visualization III (Davis 2013), pp. 103–117. Springer, Berlin (2014)
[3]
Bott R and Tu LW Differential Forms in Algebraic Topology. Graduate Texts in Mathematics 1982 New York Springer
[4]
Bredon GE Sheaf Theory. Graduate Texts in Mathematics 1997 New York Springer
[5]
Carlsson G Topology and data Bull. Am. Math. Soc. 2009 46 2 255-308
[6]
Chazal F, de Silva V, Glisse M, and Oudot S The Structure and Stability of Persistence Modules. SpringerBriefs in Mathematics 2016 Cham Springer
[7]
Chen, C., Kerber, M.: Persistent homology computation with a twist. In: 27th European Workshop on Computational Geometry (Morschach 2011), pp. 197–200 (2011). https://eurocg11.inf.ethz.ch/docs/Booklet.pdf
[8]
Chen C and Kerber M An output-sensitive algorithm for persistent homology Comput. Geom. 2013 46 4 435-447
[9]
Chow TY You could have invented spectral sequences Not. Am. Math. Soc. 2006 53 1 15-19
[10]
Cohen-Steiner, D., Edelsbrunner, H., Harer, J., Morozov, D.: Persistent homology for kernels, images, and cokernels. In: 20th Annual ACM-SIAM Symposium on Discrete Algorithms (New York 2009), pp. 1011–1020. SIAM, Philadelphia (2009)
[11]
Curry J, Ghrist R, and Nanda V Discrete Morse theory for computing cellular sheaf cohomology Found. Comput. Math. 2016 16 4 875-897
[12]
Delfinado CJA and Edelsbrunner H An incremental algorithm for Betti numbers of simplicial complexes on the -sphere Comput. Aided Geom. Des. 1995 12 7 771-784
[13]
Di Fabio B and Landi C Persistent homology and partial similarity of shapes Pattern Recognit. Lett. 2012 33 11 1445-1450
[14]
Edelsbrunner H and Harer JL Computational Topology: An Introduction 2010 Providence American Mathematical Society
[15]
Edelsbrunner H, Letscher D, and Zomorodian A Topological persistence and simplification Discrete Comput. Geom. 2002 28 4 511-533
[16]
Ghrist, R.: Elementary Applied Topology. Createspace (2014)
[17]
Govc D and Skraba P An approximate nerve theorem Found. Comput. Math. 2018 18 5 1245-1297
[18]
Lewis, R., Morozov, D.: Parallel computation of persistent homology using the blowup complex. In: 27th ACM Symposium on Parallelism in Algorithms and Architectures (Portland 2015), pp. 323–331. ACM, New York (2015)
[19]
Lipsky, D., Skraba, P., Vejdemo-Johansson, M.: A spectral sequence for parallelized persistence (2011). arXiv:1112.1245
[20]
McCleary J A User’s Guide to Spectral Sequences. Cambridge Studies in Advanced Mathematics 2001 Cambridge Cambridge University Press
[21]
Milosavljević, N., Morozov, D., Škraba, P.: Zigzag persistent homology in matrix multiplication time. In: 27th Annual Symposium on Computational Geometry (Paris 2011), pp. 216–225. ACM, New York (2011)
[22]
Munkres JR Elements of Algebraic Topology 2018 San Francisco Addison-Wesley
[23]
Robins V and Turner K Principal component analysis of persistent homology rank functions with case studies of spatial point patterns, sphere packing and colloids Physica D 2016 334 99-117
[24]
Robinson M Topological Signal Processing. Mathematical Engineering 2014 Heidelberg Springer
[25]
de Silva, V., Ghrist, R.: Coverage in sensor networks via persistent homology. Algebr. Geom. Topol. 7(1), 339–358 (2007)
[26]
de Silva, V., Morozov, D., Vejdemo-Johansson, M.: Dualities in persistent (co)homology. Inverse Probl. 27(12), # 124003 (2011)
[27]
Singh, G., Mémoli, F., Carlsson, G.: Topological methods for the analysis of high dimensional data sets and 3D object recognition. In: Eurographics Symposium on Point-Based Graphics (Prague 2007), pp. 91–100. Eurographics Association (2007)
[28]
Skraba, P., Vejdemo-Johansson, M.: Persistence modules: algebra and algorithms (2013). arXiv:1302.2015
[29]
Torras Casas, Á.: PerMaViss: persistence Mayer Vietoris spectral sequence (2020).
[30]
Weibel CA An Introduction to Homological Algebra. Cambridge Studies in Advanced Mathematics 1994 Cambridge Cambridge University Press
[31]
Yoon, H.R.: Cellular Sheaves and Cosheaves for Distributed Topological Data Analysis. PhD thesis, University of Pennsylvania (2018). https://repository.upenn.edu/edissertations/2936
[32]
Yoon, H.R., Ghrist, R.: Persistence by parts: multiscale feature detection via distributed persistent homology (2020). arXiv:2001.01623
[33]
Zomorodian A and Carlsson G Localized homology Comput. Geom. 2008 41 3 126-148
Recommendations
Computation of cubical homology, cohomology, and (co)homological operations via chain contraction
We introduce algorithms for the computation of homology, cohomology, and related operations on cubical cell complexes, using the technique based on a chain contraction from the original chain complex to a reduced one that represents its homology. This ...
A Mayer---Vietoris Formula for Persistent Homology with an Application to Shape Recognition in the Presence of Occlusions
In algebraic topology it is well known that, using the Mayer---Vietoris sequence, the homology of a space X can be studied by splitting X into subspaces A and B and computing the homology of A, B, and AźB. A natural question is: To what extent does ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s) 2023.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 20 September 2023
Accepted: 12 November 2022
Revision received: 27 October 2022
Received: 11 August 2020
Author Tags
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in