Abstract
In this paper, we establish explicit and broadly applicable relationships between persistence-based distances computed locally and globally. In particular, we show that the bottleneck distance and the Wasserstein distance between two zigzag persistence modules restricted to an interval is always bounded above by the distance between the unrestricted versions. While this result is not surprising, it could have potential practical implications. We give two related applications for metric graph distances, as well as an extension for the matching distance between multi-parameter persistence modules. We also prove a similar restriction inequality for the interleaving distance between two multi-parameter persistence modules.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aanjaneya, M., Chazal, F., Chen, D., Glisse, M., Guibas, L., Morozov, D.: Metric graph reconstruction from noisy data. Int. J. Comput. Geom. Appl. 22(4), 305–325 (2012)
Ahmed, M., Fasy, B.T., Wenk, C.: Local persistent homology based distance between maps. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 43–52 (2014)
Bendich, P., Cohen-Steiner, D., Edelsbrunner, H., Harer, J., Morozov, D.: Inferring local homology from sampled stratified spaces. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 536–546 (2007)
Bendich, P., Gasparovic, E., Harer, J., Izmailov, R., Ness, L.: Multi-scale local shape analysis and feature selection in machine learning applications. In: International Joint Conference on Neural Networks, pp. 1–8 (2015)
Bendich, P., Wang, B., Mukherjee, S.: Local homology transfer and stratification learning. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 1355–1370 (2012)
Bille, P.: A survey on tree edit distance and related problems. Theor. Comput. Sci. 337(1–3), 217–239 (2005)
Carlsson, G., de Silva, V.: Zigzag persistence. Found. Comput. Math. 10(4), 367–405 (2010)
Carlsson, G., de Silva, V., Morozov, D.: Zigzag persistent homology and real-valued functions. In: Proceedings of the 25th Annual Symposium on Computational Geometry, pp. 247–256 (2009)
Carlsson, G., Zomorodian, A.: The theory of multidimensional persistence. Discrete Comput. Geom. 42(1), 71–93 (2009)
Chazal, F., De Silva, V., Glisse, M., Oudot, S.: The Structure and Stability of Persistence Modules. Springer, Berlin (2016)
Chernov, A., Kurlin, V.: Reconstructing persistent graph structures from noisy images. Image-a 3(5), 19–22 (2013)
Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discrete Comput. Geom. 37, 103–120 (2007)
Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Extending persistence using poincaré and lefschetz duality. Found. Comput. Math. 9(1), 79–103 (2009)
Cohen-Steiner, D., Edelsbrunner, H., Harer, J., Mileyko, Y.: Lipschitz functions have l p-stable persistence. Found. Comput. Math. 10(2), 127–139 (2010)
Dey, T.K., Shi, D., Wang, Y.: Comparing graphs via persistence distortion. In: Proceedings of the 31st International Symposium on Computational Geometry, vol. 34, pp. 491–506 (2015)
Dey, T.K., Wang, Y.: Computational Topology for Data Analysis. Cambridge University Press (forthcoming)
Edelsbrunner, H., Harer, J.: Persistent homology—a survey. Contemp. Math. 453, 257–282 (2008)
Edelsbrunner, H., Morozov, D.: Persistent homology. In: Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.) Handbook of Discrete and Computational Geometry, chap. 24. CRC Press, Boca Raton (2017)
Harshaw, C.R., Bridges, R.A., Lannacone, M.D., Reed, J.W., Goodall, J.R.: Graphprints: towards a graph analytic method for network anomaly detection. In: Proceedings of the 11th Annual Cyber and Information Security Research Conference, p. 15 (2016)
Landi, C.: The rank invariant stability via interleavings. In: Chambers, E.W., Fasy, B.T., Ziegelmeier, L. (eds.) Research in Computational Topology, pp. 1–10. Springer, Cham (2018)
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: Simple building blocks of complex networks. Science 298(5594), 824–827 (2002)
Milosavljević, N., Morozov, D., Skraba, P.: Zigzag persistent homology in matrix multiplication time. In: Proceedings of the 20th Annual Symposium on Computational Geometry, pp. 216–225 (2011)
Shen-Orr, S.S., Milo, R., Mangan, S., Alon, U.: Network motifs in the transcriptional regulation network of Escherichia coli. Nat. Genet. 31(1), 64 (2002)
Wang, B., Summa, B., Pascucci, V., Vejdemo-Johansson, M.: Branching and circular features in high dimensional data. IEEE Trans. Visualization Comput. Graph. 17(12), 1902–1911 (2011)
Acknowledgements
We are grateful for the Women in Computational Topology (WinCompTop) workshop for initiating our research collaboration. In particular, participant travel support was made possible through the grant NSF-DMS-1619908. Our group was also supported by the American Institute of Mathematics (AIM) Structured Quartet Research Ensembles (SQuaRE) program. E.P. was supported by the High Performance Data Analytics (HPDA) program at Pacific Northwest National Laboratory. RS was partially supported by NSF grant DMS-1854705 and the SIMONS Collaboration grant 318086. B.W. was partially funded by NSF-IIS-1513616, NSF-DBI-1661375, and NIH-R01-1R01EB022876-01. Y.W. was supported by NSF grants CCF-1740761 and DMS-1547357. L.Z. was supported by NSF grant CDS&E-MSS-1854703.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s) and the Association for Women in Mathematics
About this chapter
Cite this chapter
Gasparovic, E. et al. (2022). Local Versus Global Distances for Zigzag and Multi-Parameter Persistence Modules. In: Gasparovic, E., Robins, V., Turner, K. (eds) Research in Computational Topology 2. Association for Women in Mathematics Series, vol 30. Springer, Cham. https://doi.org/10.1007/978-3-030-95519-9_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-95519-9_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-95518-2
Online ISBN: 978-3-030-95519-9
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)