## 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

## 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
- MR Author ID: 747856
- Email: kramar.miroslav.e1@tohoku.ac.jp
- 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. - © Copyright 2016 American Mathematical Society
- Journal: Math. Comp.
**86**(2017), 1887-1912 - MSC (2010): Primary 55-04, 55N99
- DOI: https://doi.org/10.1090/mcom/3137
- MathSciNet review: 3626542