Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

On $ \varepsilon$ approximations of persistence diagrams


Authors: Jonathan Jaquette and Miroslav Kramár
Journal: Math. Comp. 86 (2017), 1887-1912
MSC (2010): Primary 55-04, 55N99
DOI: https://doi.org/10.1090/mcom/3137
Published electronically: October 26, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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.
  • [2] 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.
  • [3] 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, https://doi.org/10.1137/120903154
  • [4] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer, Stability of persistence diagrams, Discrete Comput. Geom. 37 (2007), no. 1, 103-120. MR 2279866 (2008i:68130), https://doi.org/10.1007/s00454-006-1276-5
  • [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 (2010i:60156), https://doi.org/10.1137/080735722
  • [6] 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 (2012j:57001), https://doi.org/10.1007/s00454-010-9303-y
  • [7] 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 (2009h:55003), https://doi.org/10.1090/conm/453/08802
  • [8] Herbert Edelsbrunner and John L. Harer, Computational Topology: An Introduction, American Mathematical Society, Providence, RI, 2010. MR 2572029 (2011e:00001)
  • [9] 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 (2005k:37063), https://doi.org/10.1103/PhysRevE.70.035203
  • [10] M. Gameiro, K. Mischaikow, and T. Wanner, Evolution of pattern complexity in the Cahn-Hilliard theory of phase separation, Acta Materialia 53 (2005).
  • [11] 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 (2004j:90004)
  • [12] Allen Hatcher, Algebraic Topology, Cambridge University Press, Cambridge, 2002. MR 1867354 (2002k:55001)
  • [13] J. Jaquette and M. Kramar, C++ code available at: http://chomp.rutgers.edu/Projects/Rigorous_Computational_Dynamics/Approximating_Persistence_Diagrams.html.
  • [14] Tomasz Kaczynski, Konstantin Mischaikow, and Marian Mrozek, Computational Homology, Applied Mathematical Sciences, vol. 157, Springer-Verlag, New York, 2004. MR 2028588 (2005g:55001)
  • [15] 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] M. Kramar, A. Goullet, L. Kondic, and K. Mischaikow, Persistence of force networks in compressed granular media, Phys. Rev. E 87 (2013), 042207.
  • [17] Miroslav Kramar, Arnaud Goullet, Lou Kondic, and Konstantin Mischaikow, Quantifying force networks in particulate systems, Phys. D 283 (2014), 37-55. MR 3228988, https://doi.org/10.1016/j.physd.2014.05.009
  • [18] 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, https://doi.org/10.1016/j.physd.2016.02.003
  • [19] 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).
  • [20] 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.
  • [21] R. Mendoza, K. Thornton, I. Savin, and P. W. Voorhees, The evolution of interfacial topology during coarsening, Acta Materialia 54 (2006), 743-750.
  • [22] 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 (2012k:60008), https://doi.org/10.1088/0266-5611/27/12/124007
  • [23] 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, https://doi.org/10.1007/s00454-013-9529-6
  • [24] Konstantin Mischaikow and Thomas Wanner, Topology-guided sampling of nonhomogeneous random processes, Ann. Appl. Probab. 20 (2010), no. 3, 1068-1097. MR 2680558 (2011g:60068), https://doi.org/10.1214/09-AAP652

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 55-04, 55N99

Retrieve articles in all journals with MSC (2010): 55-04, 55N99


Additional Information

Jonathan Jaquette
Affiliation: Department of Mathematics, Hill Center-Busch Campus, Rutgers University, 110 Frelinghusen Road, Piscataway, New Jersey 08854-8019
Email: jaquette@math.rutgers.edu

Miroslav Kramár
Affiliation: Department of Mathematics, Hill Center-Busch Campus, Rutgers University, 110 Frelinghusen Road, Piscataway, New Jersey 08854-8019
Address at time of publication: Advanced Institute for Material Research, Tohoku University, 2-1-1 Katahira, Aoba-ku, Sendai, 980-8577 Japan
Email: kramar.miroslav.e1@tohoku.ac.jp

DOI: https://doi.org/10.1090/mcom/3137
Received by editor(s): December 4, 2014
Received by editor(s) in revised form: September 15, 2015, and December 27, 2015
Published electronically: October 26, 2016
Additional Notes: The first author’s research was funded in part by AFOSR Grant FA9550-09-1-0148 and NSF Grant DMS-0915019.
The second author’s research was funded in part by NSF Grants DMS-1125174 and DMS-0835621.
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society