On 𝜖 approximations of persistence diagrams

Jaquette, Jonathan; Kramár, Miroslav

doi:10.1090/mcom/3137

On $\varepsilon$ approximations of persistence diagrams
HTML articles powered by AMS MathViewer

by Jonathan Jaquette and Miroslav Kramár PDF

Math. Comp. 86 (2017), 1887-1912 Request permission

Abstract:

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 \colon X \to \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.

References

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.
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.
Gregory S. Cochran, Thomas Wanner, and PawełDłotko, A randomized subdivision algorithm for determining the topology of nodal sets, SIAM J. Sci. Comput. 35 (2013), no. 5, B1034–B1054. MR 3106488, DOI 10.1137/120903154
David Cohen-Steiner, Herbert Edelsbrunner, and John Harer, Stability of persistence diagrams, Discrete Comput. Geom. 37 (2007), no. 1, 103–120. MR 2279866, DOI 10.1007/s00454-006-1276-5
Sarah Day, William D. Kalies, and Thomas Wanner, Verified homology computations for nodal domains, Multiscale Model. Simul. 7 (2009), no. 4, 1695–1726. MR 2539195, DOI 10.1137/080735722
PawełDłotko, Tomasz Kaczynski, Marian Mrozek, and Thomas Wanner, Coreduction homology algorithm for regular CW-complexes, Discrete Comput. Geom. 46 (2011), no. 2, 361–388. MR 2812514, DOI 10.1007/s00454-010-9303-y
Herbert Edelsbrunner and John Harer, Persistent homology—a survey, Surveys on discrete and computational geometry, Contemp. Math., vol. 453, Amer. Math. Soc., Providence, RI, 2008, pp. 257–282. MR 2405684, DOI 10.1090/conm/453/08802
Herbert Edelsbrunner and John L. Harer, Computational topology, American Mathematical Society, Providence, RI, 2010. An introduction. MR 2572029, DOI 10.1090/mbk/069
Marcio Gameiro, Konstantin Mischaikow, and William Kalies, Topological characterization of spatial-temporal chaos, Phys. Rev. E (3) 70 (2004), no. 3, 035203, 4. MR 2129999, DOI 10.1103/PhysRevE.70.035203
M. Gameiro, K. Mischaikow, and T. Wanner, Evolution of pattern complexity in the Cahn-Hilliard theory of phase separation, Acta Materialia 53 (2005).
Eldon Hansen and G. William Walster, Global optimization using interval analysis, Monographs and Textbooks in Pure and Applied Mathematics, vol. 264, Marcel Dekker, Inc., New York, 2004. Second edition, revised and expanded; With a foreword by Ramon Moore. MR 2025041
Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. MR 1867354
J. Jaquette and M. Kramar, C++ code available at: http://chomp.rutgers.edu/Projects/Rigorous_Computational_Dynamics/Approximating_Persistence_Diagrams.html.
Tomasz Kaczynski, Konstantin Mischaikow, and Marian Mrozek, Computational homology, Applied Mathematical Sciences, vol. 157, Springer-Verlag, New York, 2004. MR 2028588, DOI 10.1007/b97315
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.
M. Kramar, A. Goullet, L. Kondic, and K. Mischaikow, Persistence of force networks in compressed granular media, Phys. Rev. E 87 (2013), 042207.
Miroslav Kramár, Arnaud Goullet, Lou Kondic, and Konstantin Mischaikow, Quantifying force networks in particulate systems, Phys. D 283 (2014), 37–55. MR 3228988, DOI 10.1016/j.physd.2014.05.009
Miroslav Kramár, Rachel Levanger, Jeffrey Tithof, Balachandra Suri, Mu Xu, Mark Paul, Michael F. Schatz, and Konstantin Mischaikow, Analysis of Kolmogorov flow and Rayleigh-Bénard convection using persistent homology, Phys. D 334 (2016), 82–98. MR 3545971, DOI 10.1016/j.physd.2016.02.003
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).
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.
R. Mendoza, K. Thornton, I. Savin, and P. W. Voorhees, The evolution of interfacial topology during coarsening, Acta Materialia 54 (2006), 743–750.
Yuriy Mileyko, Sayan Mukherjee, and John Harer, Probability measures on the space of persistence diagrams, Inverse Problems 27 (2011), no. 12, 124007, 22. MR 2854323, DOI 10.1088/0266-5611/27/12/124007
Konstantin Mischaikow and Vidit Nanda, Morse theory for filtrations and efficient computation of persistent homology, Discrete Comput. Geom. 50 (2013), no. 2, 330–353. MR 3090522, DOI 10.1007/s00454-013-9529-6
Konstantin Mischaikow and Thomas Wanner, Topology-guided sampling of nonhomogeneous random processes, Ann. Appl. Probab. 20 (2010), no. 3, 1068–1097. MR 2680558, DOI 10.1214/09-AAP652