×

A fractal dimension for measures via persistent homology. (English) Zbl 1448.62211

Baas, Nils (ed.) et al., Topological data analysis. Proceedings of the Abel symposium 2018, Geiranger, Norway, June 4–8, 2018. Cham: Springer. Abel Symp. 15, 1-31 (2020).
Summary: We use persistent homology in order to define a family of fractal dimensions, denoted \(\dim_{\text{PH}}^i(\mu)\) for each homological dimension \(i\geq 0\), assigned to a probability measure \(\mu\) on a metric space. The case of zero-dimensional homology \((i = 0)\) relates to work by J. M. Steele [Ann. Probab. 16, No. 4, 1767–1787 (1988; Zbl 0655.60023)] studying the total length of a minimal spanning tree on a random sampling of points. Indeed, if \(\mu\) is supported on a compact subset of Euclidean space \(\mathbb{R}^m\) for \(m \geq 2\), then Steele’s work implies that \(\dim_{\text{PH}}^0(\mu )=m\) if the absolutely continuous part of \(\mu\) has positive mass, and otherwise \(\dim_{\text{PH}}^0(\mu )<m\). Experiments suggest that similar results may be true for higher-dimensional homology \(0<i<m\), though this is an open question. Our fractal dimension is defined by considering a limit, as the number of points \(n\) goes to infinity, of the total sum of the \(i\)-dimensional persistent homology interval lengths for \(n\) random points selected from \(\mu\) in an i.i.d. fashion. To some measures \(\mu\), we are able to assign a finer invariant, a curve measuring the limiting distribution of persistent homology interval lengths as the number of points goes to infinity. We prove this limiting curve exists in the case of zero-dimensional homology when \(\mu\) is the uniform distribution over the unit interval, and conjecture that it exists when \(\mu\) is the rescaled probability measure for a compact set in Euclidean space with positive Lebesgue measure.
For the entire collection see [Zbl 1448.62008].

MSC:

62R40 Topological data analysis
62R20 Statistics on metric spaces
55N31 Persistent homology and applications, topological data analysis
60B05 Probability measures on topological spaces
37F35 Conformal densities and Hausdorff dimension for holomorphic dynamical systems
60F15 Strong limit theorems

Citations:

Zbl 0655.60023

References:

[1] Henry Adams, Sofya Chepushtanova, Tegan Emerson, Eric Hanson, Michael Kirby, Francis Motta, Rachel Neville, Chris Peterson, Patrick Shipman, and Lori Ziegelmeier. Persistence images: A stable vector representation of persistent homology. The Journal of Machine Learning Research, 18(1):218-252, 2017. · Zbl 1431.68105
[2] Aaron Adcock, Daniel Rubin, and Gunnar Carlsson. Classification of hepatic lesions using the matching metric. Computer Vision and Image Understanding, 121:36-42, 2014. · doi:10.1016/j.cviu.2013.10.014
[3] Robert J Adler, Omer Bobrowski, Matthew S Borman, Eliran Subag, and Shmuel Weinberger. Persistent homology for random fields and complexes. In Borrowing strength: theory powering applications—a Festschrift for Lawrence D. Brown, pages 124-143. Institute of Mathematical Statistics, 2010.
[4] Robert J Adler, Omer Bobrowski, and Shmuel Weinberger. Crackle: The persistent homology of noise. arXiv preprint arXiv:1301.1466, 2013. · Zbl 1350.60010
[5] David Aldous and J Michael Steele. Asymptotics for Euclidean minimal spanning trees on random points. Probability Theory and Related Fields, 92(2):247-258, 1992. · Zbl 0767.60005
[6] David Aldous and J Michael Steele. The objective method: probabilistic combinatorial optimization and local weak convergence. In Probability on discrete structures, pages 1-72. Springer, 2004. · Zbl 1037.60008
[7] Kenneth S Alexander. The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees. The Annals of Applied Probability, 6(2):466-494, 1996. · Zbl 0855.60009
[8] Mark A Armstrong. Basic topology. Springer Science & Business Media, 2013.
[9] Ulrich Bauer. Ripser: A lean C+ + code for the computation of Vietoris-Rips persistence barcodes. Software available athttps://github.com/Ripser/ripser, 2017.
[10] Paul Bendich, J S Marron, Ezra Miller, Alex Pieloch, and Sean Skwerer. Persistent homology analysis of brain artery trees. The Annals of Applied Statistics, 10(1):198-218, 2016.
[11] Martin Bilodeau and David Brenner. Theory of multivariate statistics. Springer Science & Business Media, 2008. · Zbl 0930.62054
[12] Omer Bobrowski and Matthew Strom Borman. Euler integration of Gaussian random fields and persistent homology. Journal of Topology and Analysis, 4(01):49-70, 2012. · Zbl 1260.60070
[13] Omer Bobrowski and Matthew Kahle. Topology of random geometric complexes: A survey. Journal of Applied and Computational Topology, 2018. · Zbl 1402.60015
[14] Omer Bobrowski, Matthew Kahle, and Primoz Skraba. Maximally persistent cycles in random geometric complexes. arXiv preprint arXiv:1509.04347, 2015. · Zbl 1377.60024
[15] Paul Breiding, Sara Kalisnik Verovsek, Bernd Sturmfels, and Madeleine Weinstein. Learning algebraic varieties from samples. arXiv preprint arXiv:1802.09436, 2018. · Zbl 1481.13040
[16] Gunnar Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46(2):255-308, 2009. · Zbl 1172.62002 · doi:10.1090/S0273-0979-09-01249-X
[17] Frédéric Chazal, Vin de Silva, and Steve Oudot. Persistence stability for geometric complexes. Geometriae Dedicata, pages 1-22, 2013. · Zbl 1320.55003
[18] Frédéric Chazal and Vincent Divol. The density of expected persistence diagrams and its kernel based estimation. arXiv preprint arXiv:1802.10457, 2018. · Zbl 1473.55002
[19] Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. Power-law distributions in empirical data. SIAM review, 51(4):661-703, 2009. · Zbl 1176.62001
[20] Anne Collins, Afra Zomorodian, Gunnar Carlsson, and Leonidas J. Guibas. A barcode shape descriptor for curve point cloud data. Computers & Graphics, 28(6):881-894, 2004. · Zbl 1092.68688 · doi:10.1016/j.cag.2004.08.015
[21] Jose A Costa and Alfred O Hero. Determining intrinsic dimension and entropy of high-dimensional shape spaces. In Statistics and Analysis of Shapes, pages 231-252. Springer, 2006. · Zbl 1160.94303
[22] Justin Michael Curry. Topological data analysis and cosheaves. Japan Journal of Industrial and Applied Mathematics, 32(2):333-371, 2015. · Zbl 1323.55002
[23] Colleen D Cutler. Some results on the behavior and estimation of the fractal dimensions of distributions on attractors. Journal of Statistical Physics, 62(3-4):651-708, 1991. · Zbl 0738.58029
[24] Colleen D Cutler. A review of the theory and estimation of fractal dimension. In Dimension estimation and models, pages 1-107. World Scientific, 1993.
[25] Yuri Dabaghian, Facundo Mémoli, Loren Frank, and Gunnar Carlsson. A topological paradigm for hippocampal spatial map formation using persistent homology. PLoS computational biology, 8(8):e1002581, 2012.
[26] Vincent Divol and Wolfgang Polonik. On the choice of weight functions for linear representations of persistence diagrams. arXiv preprint arXiv: arXiv:1807.03678, 2018. · Zbl 1422.60024
[27] Herbert Edelsbrunner and John L Harer. Computational Topology: An Introduction. American Mathematical Society, Providence, 2010. · Zbl 1193.55001
[28] Herbert Edelsbrunner, A Ivanov, and R Karasev. Current open problems in discrete and computational geometry. Modelirovanie i Analiz Informats. Sistem, 19(5):5-17, 2012.
[29] Herbert Edelsbrunner, Anton Nikitenko, and Matthias Reitzner. Expected sizes of Poisson-Delaunay mosaics and their discrete Morse functions. Advances in Applied Probability, 49(3):745-767, 2017. · Zbl 1425.60013 · doi:10.1017/apr.2017.20
[30] Kenneth Falconer. Fractal geometry: mathematical foundations and applications; 3rd ed. Wiley, Hoboken, NJ, 2013. · Zbl 1285.28011
[31] J.D. Farmer. Information dimension and the probabilistic structure of chaos. Zeitschrift für Naturforschung A, 37(11):1304-1326, 1982. · doi:10.1515/zna-1982-1117
[32] J.D. Farmer, Edward Ott, and James Yorke. The dimension of chaotic attractors. Physica D: Nonlinear Phenomena, 7(1):153-180, 1983. · Zbl 0561.58032
[33] Gerald Folland. Real Analysis. John Wiley & Sons, 1999. · Zbl 0924.28001
[34] Robert Ghrist. Barcodes: The persistent topology of data. Bulletin of the American Mathematical Society, 45(1):61-75, 2008. · Zbl 1391.55005 · doi:10.1090/S0273-0979-07-01191-3
[35] Peter Grassberger and Itamar Procaccia. Characterization of strange attractors. Physics Review Letters, 50(5):346-349, 1983. · Zbl 0593.58024 · doi:10.1103/PhysRevLett.50.346
[36] Peter Grassberger and Itamar Procaccia. Measuring the Strangeness of Strange Attractors. In The Theory of Chaotic Attractors, pages 170-189. Springer, New York, NY, 2004. · Zbl 0593.58024
[37] Allen Hatcher. Algebraic Topology. Cambridge University Press, Cambridge, 2002. · Zbl 1044.55001
[38] Patrick Jaillet. On properties of geometric random problems in the plane. Annals of Operations Research, 61(1):1-20, 1995. · Zbl 0839.90133 · doi:10.1007/BF02098279
[39] Matthew Kahle. Random geometric complexes. Discrete & Computational Geometry, 45(3):553-573, 2011. · Zbl 1219.05175 · doi:10.1007/s00454-010-9319-3
[40] Albrecht M Kellerer. On the number of clumps resulting from the overlap of randomly placed figures in a plane. Journal of Applied Probability, 20(1):126-135, 1983. · Zbl 0505.60020
[41] Harry Kesten and Sungchul Lee. The central limit theorem for weighted minimal spanning trees on random points. The Annals of Applied Probability, pages 495-527, 1996. · Zbl 0862.60008
[42] Gady Kozma, Zvi Lotker, and Gideon Stupp. The minimal spanning tree and the upper box dimension. Proceedings of the American Mathematical Society, 134(4):1183-1187, 2006. · Zbl 1083.68137 · doi:10.1090/S0002-9939-05-08061-5
[43] Joseph B Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society, 7(1):48-50, 1956. · Zbl 0070.18404
[44] H Lee, H Kang, M K Chung, B N Kim, and D S Lee. Persistent brain network homology from the perspective of dendrogram. IEEE Transactions on Medical Imaging, 31(12):2267-2277, 2012.
[45] Javier Lamar Leon, Andrea Cerri, Edel Garcia Reyes, and Rocio Gonzalez Diaz. Gait-based gender classification using persistent homology. In José Ruiz-Shulcloper and Gabriella Sanniti di Baja, editors, Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, pages 366-373, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
[46] Robert MacPherson and Benjamin Schweinhart. Measuring shape with topology. Journal of Mathematical Physics, 53(7):073516, 2012. · Zbl 1278.82073
[47] Pertti Mattila, Manuel Morán, and José-Manuel Rey. Dimension of a measure. Studia Math, 142(3):219-233, 2000. · Zbl 1008.28005 · doi:10.4064/sm-142-3-219-233
[48] Pat A .P. Moran. Additive functions of intervals and Hausdorff measure. Proceedings of the Cambridge Philosophical Society, 42(1):15-23, 1946. · Zbl 0063.04088
[49] Heinz-Otto Peitgen, Hartmut Jürgens, and Dietmar Saupe. Chaos and fractals: New frontiers of science. Springer Science & Business Media, 2006. · Zbl 1036.37001
[50] Mathew Penrose. Random geometric graphs, volume 5. Oxford University Press, Oxford, 2003. · Zbl 1029.60007 · doi:10.1093/acprof:oso/9780198506263.001.0001
[51] Mathew D Penrose. The longest edge of the random minimal spanning tree. The annals of applied probability, pages 340-361, 1997. · Zbl 0884.60042
[52] Mathew D Penrose et al. A strong law for the longest edge of the minimal spanning tree. The Annals of Probability, 27(1):246-260, 1999. · Zbl 0944.60015
[53] Mathew D Penrose and Joseph E Yukich. Central limit theorems for some graphs in computational geometry. Annals of Applied probability, pages 1005-1041, 2001. · Zbl 1044.60016
[54] Yakov B Pesin. Dimension theory in dynamical systems: contemporary views and applications. University of Chicago Press, 2008. · Zbl 0895.58033
[55] Robert Clay Prim. Shortest connection networks and some generalizations. Bell Labs Technical Journal, 36(6):1389-1401, 1957.
[56] Alfréd Rényi. On the dimension and entropy of probability distributions. Acta Mathematica Hungarica, 10(1-2):193-215, 1959. · Zbl 0088.10702
[57] Alfréd Rényi. Probability Theory. North Holland, Amsterdam, 1970. · Zbl 0233.60001
[58] Vanessa Robins. Computational topology at multiple resolutions: foundations and applications to fractals and dynamics. PhD thesis, University of Colorado, 2000.
[59] M.J. Schervish. Theory of Statistics. Springer Series in Statistics. Springer New York, 1996. · Zbl 0859.62087
[60] Benjamin Schweinhart. Persistent homology and the upper box dimension. arXiv preprint arXiv:1802.00533, 2018. · Zbl 1450.28007
[61] Benjamin Schweinhart. The persistent homology of random geometric complexes on fractals. arXiv preprint arXiv:1808.02196, 2018. · Zbl 1450.28007
[62] Benjamin Schweinhart. Weighted persistent homology sums of random Čech complexes. arXiv preprint arXiv:1807.07054, 2018. · Zbl 1450.28007
[63] J Michael Steele. Growth rates of Euclidean minimal spanning trees with power weighted edges. The Annals of Probability, pages 1767-1787, 1988. · Zbl 0655.60023
[64] J Michael Steele. Probability and problems in Euclidean combinatorial optimization. Statistical Science, pages 48-56, 1993.
[65] J Michael Steele. Minimal spanning trees for graphs with random edge lengths. In Mathematics and Computer Science II, pages 223-245. Springer, 2002. · Zbl 1032.60007
[66] J Michael Steele, Lawrence A Shepp, and William F Eddy. On the number of leaves of a Euclidean minimal spanning tree. Journal of Applied Probability, 24(4):809-826, 1987. · Zbl 0639.60014
[67] J Michael Steele and Luke Tierney. Boundary domination and the distribution of the largest nearest-neighbor link in higher dimensions. Journal of Applied Probability, 23(2):524-528, 1986. · Zbl 0612.60010
[68] Andrew Tausz, Mikael Vejdemo-Johansson, and Henry Adams. Javaplex: A research software package for persistent (co)homology. In International Congress on Mathematical Software, pages 129-136, 2014. Software available at http://appliedtopology.github.io/javaplex/. · Zbl 1402.65186
[69] James Theiler. Estimating fractal dimension. JOSA A, 7(6):1055-1073, 1990. · doi:10.1364/JOSAA.7.001055
[70] Robert W Vallin. The elements of Cantor sets: with applications. John Wiley & Sons, 2013. · Zbl 1276.28001
[71] Kelin Xia and Guo-Wei Wei. Multidimensional persistence in biomolecular data. Journal of Computational Chemistry, 36(20):1502-1520, 2015. · doi:10.1002/jcc.23953
[72] Joseph E Yukich. Probability theory of classical Euclidean optimization problems. Springer, 2006. · Zbl 0902.60001
[73] Xiaojin Zhu.
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.