×

zbMATH — the first resource for mathematics

Rigorous cubical approximation and persistent homology of continuous functions. (English) Zbl 1409.41014
Summary: The interaction between discrete and continuous mathematics lies at the heart of many fundamental problems in applied mathematics and computational sciences. In this paper we discuss the problem of discretizing vector-valued functions defined on finite-dimensional Euclidean spaces in such a way that the discretization error is bounded by a pre-specified small constant. While the approximation scheme has a number of potential applications, we consider its usefulness in the context of computational homology. More precisely, we demonstrate that our approximation procedure can be used to rigorously compute the persistent homology of the original continuous function on a compact domain, up to small explicitly known and verified errors. In contrast to other work in this area, our approach requires minimal smoothness assumptions on the underlying function.
MSC:
41A63 Multidimensional problems (should also be assigned at least one other classification number from Section 41-XX)
55N35 Other homology theories in algebraic topology
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Moore, R. E.; Kearfott, R. B.; Cloud, M. J., Introduction to Interval Analysis, (2009), SIAM
[2] de Figueiredo, L. H.; Stolfi, J., Affine arithmetic: concepts and applications, Numer. Algorithms, 37, 1-4, 147-158, (2004) · Zbl 1074.65050
[3] Hansen, E. R., A generalized interval arithmetic, (Interval Mathematics, The Series Lecture Notes in Computer Science, vol. 29, (2005)), 7-18
[4] Edelsbrunner, H.; Letscher, D.; Zomorodian, A., Topological persistence and simplification, Discrete Comput. Geom., 29, 4, 511-533, (2002) · Zbl 1011.68152
[5] Carlsson, G.; Zomorodian, A., The theory of multidimensional persistence, Discrete Comput. Geom., 42, 1, 71-93, (2009) · Zbl 1187.55004
[6] Wylie, S.; Hilton, P. J., Homology Theory. An Introduction to Algebraic Topology, (1994), Springer
[7] Jaquette, J.; Kramar, M., Rigorous computation of persistent homology, Math. Comp., 86, 1887-1912, (2017) · Zbl 1420.55011
[8] Mrozek, M.; Wanner, T., Coreduction homology algorithm for inclusions and persistent homology, Comput. Math. Appl., 60, 10, 2812-2833, (2010) · Zbl 1207.57001
[9] Cochran, G. S.; Wanner, T.; Dłotko, P., A randomized subdivision algorithm for determining the topology of nodal sets, SIAM J. Sci. Comput., 35, 5, B1034-B1054, (2013) · Zbl 1348.55002
[10] Day, S.; Kalies, W. D.; Wanner, T., Verified homology computations for nodal domains, SIAM J. Multiscale Model. Simul., 7, 4, 1695-1726, (2009) · Zbl 1201.60034
[11] Bendich, P.; Edelsbrunner, H.; Kerber, M., Computing robustness and persistence for images, IEEE Trans. Vis. Comput. Graphics, 16, 6, 1251-1260, (2010)
[12] Bendich, P.; Edelsbrunner, H.; Kerber, M.; Patel, A., Persistent homology under non-uniform error, (Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 6281, (2010)), 12-23 · Zbl 1287.65039
[13] Massey, W. S., A Basic Course in Algebraic Topology, (1991), Springer
[14] Edelsbrunner, H.; Harer, J., Computational Topology, (2010), American Mathematical Society · Zbl 1193.55001
[15] Dłotko, P.; Kaczynski, T.; Mrozek, M.; Wanner, T., Coreduction homology algorithm for regular CW-complexes, Discrete Comput. Geom., 46, 2, 361-388, (2011) · Zbl 1229.55001
[16] Dłotko, P.; Wanner, T., Topological microstructure analysis using persistence landscapes, Physica D, 334, 1, 60-81, (2016) · Zbl 1415.35035
[17] Cohen-Steiner, D.; Edelsbrunner, H.; Harer, J., Stability of persistence diagrams, Discrete Comput. Geom., 37, 1, 103-120, (2007) · Zbl 1117.54027
[18] F. Chazal, D. Cohen-Steiner, M. Glisse, L.J. Guibas, S. Oudot, Proximity of persistence modules and their diagrams, in: Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry, ACM SCG ’09, 2009, pp. 237-246. · Zbl 1380.68387
[19] Chazal, F.; de Silva, V.; Glisse, M.; Oudot, S., (The Structure and Stability of Persistence Modules, SpringerBriefs in Mathematics, (2016)), (in press) · Zbl 1362.55002
[20] D. Morozov, Dionysus, http://www.mrzv.org/software/dionysus/.
[21] U. Bauer, M. Kerber, J. Reininghaus, PHAT (Persistent Homology Algorithm Toolbox), v1.3.0, https://code.google.com/p/phat/. · Zbl 1402.65187
[22] V. Nanda, Perseus, the Persistent Homology Software, http://www.sas.upenn.edu/ vnanda/perseus/index.html.
[23] GUDHI: User and Reference Manual, http://gudhi.gforge.inria.fr/doc/latest/.
[24] Mischaikow, K.; Nanda, V., Morse theory for filtrations and efficient computation of persistent homology, Discrete Comput. Geom., 50, 2, 330-353, (2013) · Zbl 1278.57030
[25] Cerri, A.; di Fabio, B.; Ferri, M.; Frosini, P.; Landi, C., Betti numbers in multidimensional persistent homology are stable functions, Math. Methods Appl. Sci., 36, 12, 1543-1557, (2013) · Zbl 1278.55012
[26] Cerri, A.; Landi, C., Hausdorff stability of persistence spaces, Found. Comput. Math., 16, 2, 343-367, (2016) · Zbl 1358.55005
[27] Neumaier, A., Interval Methods for Systems of Equations, (1990), Cambridge University Press · Zbl 0706.15009
[28] Chazelle, B., An optimal convex hull algorithm in any fixed dimension, Discrete Comput. Geom., 10, 4, 377-409, (1993) · Zbl 0786.68091
[29] Day, S.; Vandervorst, R.; Wanner, T., Topology in dynamics, differential equations, and data, Physica D, 334, 1, 1-3, (2016) · Zbl 1415.00011
[30] Wanner, T., Topological analysis of the diblock copolymer equation, (Nishiura, Y.; Kotani, M., Mathematical Challenges in a New Phase of Materials Science, Springer Proceedings in Mathematics & Statistics, vol. 166, (2016), Springer-Verlag), 27-51
[31] Bubenik, P.; Dłotko, P., A persistence landscapes toolbox for topological statistics, J. Symbolic Comput., (2017) · Zbl 1348.68186
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.