×

Crackle: the homology of noise. (English) Zbl 1350.60010

Let \({\mathcal X}_n\) be a set of \(n\) points in \({\mathbb R}^d\) sampled from either a power-law, exponential, or Gaussian probability distribution, i.e., a distribution of the form \((1+\|x\|^\alpha)^{-1}\), \(e^{-\|x\|}\), or \(e^{-\|x\|^2/2}\). This paper examines the homology of the union \(U\) of closed balls \(B_\varepsilon(x)\) of radius \(\varepsilon\) centered at the points \(x\) from \({\mathcal X}_n\). This is done by computing the expectation values, for large \(n\), of the Betti numbers of the Čech complex formed from these closed balls – a space that is homotopy equivalent to \(U\). Specifically, let \(\{R_n\}_{n=1}^\infty\) be an increasing sequence of positive numbers. For each of the three distributions, the authors find the core radius: the largest value of \(R_n\) for which the probability that \(B_{R_n}(0)\) is covered by closed balls of the form \(B_1(x)\), with \(x\in{\mathcal X}_n\cap B_{R_n}(0)\), approaches unity for large \(n\). For the Gaussian distribution, the homology outside of the core is shown to be trivial. That is, let \(\beta_{k,n}\) denote the \(k\)-th Betti number of the Čech complex constructed from the points of \({\mathcal X}_n\) that lie outside of \(B_{R_n}(0)\). The authors find a sequence of radial values \(\{R_n\}_{n=1}^\infty\) such that the expectation values \({\mathbb E}(\beta_{k,n})\) approach \(0\) for large \(n\). On the other hand, for the power-law and exponential distributions, the homology is nontrivial, and exhibits what the authors term crackle. Sequences \(\{R_n\}_{n=1}^\infty\) are found such that the expectation values \({\mathbb E}(\beta_{k,n})\) are either trivial, finite, or infinite for large \(n\). In particular, outside of the core the homology can be organized by annuli of increasing radius, but decreasing homological complexity. For the first annulus outside of the core, the Betti numbers in dimensions less than \(d\) are infinite, and zero otherwise. For the second annulus, the Betti numbers are infinite in dimensions less than \(d-1\), finite in dimension \(d-1\), and trivial otherwise. The pattern repeats until the Betti numbers are trivial in all dimensions.

MSC:

60D05 Geometric probability and stochastic geometry
55U10 Simplicial sets and complexes in algebraic topology
57Q99 PL-topology
05C80 Random graphs (graph-theoretic aspects)
60F15 Strong limit theorems
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Adler, R.J., Bobrowski, O., Borman, M.S., Subag, E., Weinberger, S.: Persistent homology for random fields and complexes. In: Borrowing Strength: Theory Powering Applications—A Festschrift for Lawrence D. Brown, p. 124-143. Institute of Mathematical Statistics, Beachwood (2010)
[2] Aronshtam, L; Linial, N; Łuczak, T; Meshulam, R, Collapsibility and vanishing of top homology in random simplicial complexes, Discrete Comput. Geom., 49, 317-334, (2013) · Zbl 1260.05171
[3] Babson, E; Hoffman, C; Kahle, M, The fundamental group of random 2-complexes, J. Am. Math. Soc., 24, 1-28, (2011) · Zbl 1270.20042
[4] Bobrowski, O.: Algebraic Topology of Random Fields and Complexes. Ph.D. thesis, Faculty of Electrical Engineering, Technion-Israel Institute of Technology (2012). http://www.graduate.technion.ac.il/Theses/Abstracts.asp?Id=26908
[5] Bobrowski, O., Adler, R.J.: Distance functions, critical points, and topology for some random complexes (2011). arXiv:1107.4775
[6] Bobrowski, O., Mukherjee, S.: The topology of probability distributions on manifolds. Probab. Theory Relat. Fields. 1-36 (2014). doi: 10.1007/s00440-014-0556-x
[7] Borsuk, K, On the imbedding of systems of compacta in simplicial complexes, Fundam. Math., 35, 217-234, (1948) · Zbl 0032.12303
[8] Carlsson, G, Topology and data, Bull. Am. Math. Soc., 46, 255-308, (2009) · Zbl 1172.62002
[9] Cohen, D.C., Farber, M., Kappeler, T.: The homotopical dimension of random 2-complexes (2010). arXiv:1005.3383
[10] Edelsbrunner, H; Harer, J, Persistent homology—a survey, Contemp. Math., 453, 257-282, (2008) · Zbl 1145.55007
[11] Edelsbrunner, H., Harer, J.L.: Computational Topology: An Introduction. American Mathematical Society, Providence, RI (2010) · Zbl 1193.55001
[12] Ghrist, R, Barcodes: the persistent topology of data, Bull. Am. Math. Soc., 45, 61-75, (2008) · Zbl 1391.55005
[13] Kahle, M, Random geometric complexes, Discrete Comput. Geom., 45, 553-573, (2011) · Zbl 1219.05175
[14] Kahle, M; Meckes, E, Limit the theorems for Betti numbers of random simplicial complexes, Homol. Homotopy Appl., 15, 343-374, (2013) · Zbl 1268.05180
[15] Meshulam, R; Wallach, N, Homological connectivity of random k-dimensional complexes, Random Struct. Algorithms, 34, 408-417, (2009) · Zbl 1177.55011
[16] Niyogi, P; Smale, S; Weinberger, S, Finding the homology of submanifolds with high confidence from random samples, Discrete Comput. Geom., 39, 419-441, (2008) · Zbl 1148.68048
[17] Niyogi, P; Smale, S; Weinberger, S, A topological view of unsupervised learning from noisy data, SIAM J. Comput., 40, 646-663, (2011) · Zbl 1230.62085
[18] Penrose, M.: Random Geometric Graphs. Oxford Studies in Probability, vol. 5. Oxford University Press, Oxford (2003) · Zbl 1029.60007
[19] Pippenger, N; Schleich, K, Topological characteristics of random triangulated surfaces, Random Struct. Algorithms, 28, 247-288, (2006) · Zbl 1145.52009
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.