×

On \(\varepsilon \) approximations of persistence diagrams. (English) Zbl 1420.55011

Summary: Biological and physical systems often exhibit distinct structures at different spatial/temporal scales. Persistent homology is an algebraic tool that provides a mathematical framework for analyzing the multi-scale structures frequently observed in nature. In this paper a theoretical framework for the algorithmic computation of an arbitrarily good approximation of the persistent homology is developed. We study the filtrations generated by sub-level sets of a function \( f: X \rightarrow \mathbb{R}\), where \( X\) is a CW-complex. In the special case \( X = [0,1]^N\), \( N \in \mathbb{N}\), we discuss implementation of the proposed algorithms. We also investigate a priori and a posteriori bounds of the approximation error introduced by our method.

MSC:

55N35 Other homology theories in algebraic topology
55-04 Software, source code, etc. for problems pertaining to algebraic topology
55N99 Homology and cohomology theories in algebraic topology

Software:

CHomP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Carlsson:2009:ZPH:1542362.1542408 G. Carlsson, V. de Silva, and D. Morozov, Zigzag persistent homology and real-valued functions, Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry (New York, NY, USA), SCG ’09, ACM, 2009, pp. 247-256. · Zbl 1380.68385
[2] S-P-Modules F. Chazal, V. de Silva, M. Glisse, and S. Oudot, The Structure and Stability of Persistence Modules, SpringerBriefs in Mathematics, Springer International Publishing, Switzerland, 2016. DOI 10.1007/978-3-319-42545-0. · Zbl 1362.55002
[3] Cochran, Gregory S.; Wanner, Thomas; D{\l }otko, Pawe{\l }, A randomized subdivision algorithm for determining the topology of nodal sets, SIAM J. Sci. Comput., 35, 5, B1034-B1054 (2013) · Zbl 1348.55002 · doi:10.1137/120903154
[4] Cohen-Steiner, David; Edelsbrunner, Herbert; Harer, John, Stability of persistence diagrams, Discrete Comput. Geom., 37, 1, 103-120 (2007) · Zbl 1117.54027 · doi:10.1007/s00454-006-1276-5
[5] Day, Sarah; Kalies, William D.; Wanner, Thomas, Verified homology computations for nodal domains, Multiscale Model. Simul., 7, 4, 1695-1726 (2009) · Zbl 1201.60034 · doi:10.1137/080735722
[6] D{\l }otko, Pawe{\l }; Kaczynski, Tomasz; Mrozek, Marian; Wanner, Thomas, Coreduction homology algorithm for regular CW-complexes, Discrete Comput. Geom., 46, 2, 361-388 (2011) · Zbl 1229.55001 · doi:10.1007/s00454-010-9303-y
[7] Edelsbrunner, Herbert; Harer, John, Persistent homology-a survey. Surveys on Discrete and Computational Geometry, Contemp. Math. 453, 257-282 (2008), Amer. Math. Soc., Providence, RI · Zbl 1145.55007 · doi:10.1090/conm/453/08802
[8] Edelsbrunner, Herbert; Harer, John L., Computational Topology, xii+241 pp. (2010), American Mathematical Society, Providence, RI · Zbl 1193.55001
[9] Gameiro, Marcio; Mischaikow, Konstantin; Kalies, William, Topological characterization of spatial-temporal chaos, Phys. Rev. E (3), 70, 3, 035203, 4 pp. (2004) · doi:10.1103/PhysRevE.70.035203
[10] Gameiro05evolutionof M. Gameiro, K. Mischaikow, and T. Wanner, Evolution of pattern complexity in the Cahn-Hilliard theory of phase separation, Acta Materialia 53 (2005).
[11] Hansen, Eldon; Walster, G. William, Global Optimization Using Interval Analysis, Monographs and Textbooks in Pure and Applied Mathematics 264, xviii+489 pp. (2004), Marcel Dekker, Inc., New York · Zbl 1103.90092
[12] Hatcher, Allen, Algebraic Topology, xii+544 pp. (2002), Cambridge University Press, Cambridge · Zbl 1044.55001
[13] website:jaquette-kramar J. Jaquette and M. Kramar, C++ code available at: http://chomp.rutgers.edu/Projects/Rigorous_Computational_Dynamics/Approximating_Persistence_Diagrams.html.
[14] Kaczynski, Tomasz; Mischaikow, Konstantin; Mrozek, Marian, Computational Homology, Applied Mathematical Sciences 157, xviii+480 pp. (2004), Springer-Verlag, New York · Zbl 1039.55001 · doi:10.1007/b97315
[15] epl12 L. Kondic, A. Goullet, C. S. O’Hern, M. Kramar, K. Mischaikow, and R. P. Behringer, Topology of force networks in compressed granular media, Europhys. Lett. 97 (2012), 54001.
[16] pre13 M. Kramar, A. Goullet, L. Kondic, and K. Mischaikow, Persistence of force networks in compressed granular media, Phys. Rev. E 87 (2013), 042207.
[17] Kramar, Miroslav; Goullet, Arnaud; Kondic, Lou; Mischaikow, Konstantin, Quantifying force networks in particulate systems, Phys. D, 283, 37-55 (2014) · Zbl 1349.74083 · doi:10.1016/j.physd.2014.05.009
[18] Kram{\'a}r, Miroslav; Levanger, Rachel; Tithof, Jeffrey; Suri, Balachandra; Xu, Mu; Paul, Mark; Schatz, Michael F.; Mischaikow, Konstantin, Analysis of Kolmogorov flow and Rayleigh-B\'enard convection using persistent homology, Phys. D, 334, 82-98 (2016) · Zbl 1415.76582 · doi:10.1016/j.physd.2016.02.003
[19] KKSGMM07 K. Krishan, H. Kurtuldu, M. Schatz, M. Gameiro, K. Mischaikow, and S. Madruga, Homology and symmetry breaking in Rayleigh-Benard convection: Experiments and simulations, Physics of Fluids 19 (2007). · Zbl 1182.76403
[20] FLM:8352228 H. Kurtuldu, K. Mischaikow, and M. F. Schatz, Measuring the departures from the Boussinesq approximation in Rayleigh-Benard convection experiments, Journal of Fluid Mechanics 682 (2011), 543-557. · Zbl 1241.76186
[21] MTSV06Evolution R. Mendoza, K. Thornton, I. Savin, and P. W. Voorhees, The evolution of interfacial topology during coarsening, Acta Materialia 54 (2006), 743-750.
[22] Mileyko, Yuriy; Mukherjee, Sayan; Harer, John, Probability measures on the space of persistence diagrams, Inverse Problems, 27, 12, 124007, 22 pp. (2011) · Zbl 1247.68310 · doi:10.1088/0266-5611/27/12/124007
[23] Mischaikow, Konstantin; Nanda, Vidit, Morse theory for filtrations and efficient computation of persistent homology, Discrete Comput. Geom., 50, 2, 330-353 (2013) · Zbl 1278.57030 · doi:10.1007/s00454-013-9529-6
[24] Mischaikow, Konstantin; Wanner, Thomas, Topology-guided sampling of nonhomogeneous random processes, Ann. Appl. Probab., 20, 3, 1068-1097 (2010) · Zbl 1213.60072 · doi:10.1214/09-AAP652
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.