Topology of random geometric complexes: a survey <s> Introduction <s> Let Δn−1 denote the (n − 1)-dimensional simplex. Let Y be a random 2-dimensional subcomplex of Δn−1 obtained by starting with the full 1-dimensional skeleton of Δn−1 and then adding each 2−simplex independently with probability p. Let $$H_{1} {\left( {Y;{\Bbb F}_{2} } \right)}$$ denote the first homology group of Y with mod 2 coefficients. It is shown that for any function ω(n) that tends to infinity $${\mathop {\lim }\limits_{n \to \infty } }{\kern 1pt} {\kern 1pt} {\text{Prob}}{\left[ {H_{1} {\left( {Y;{\Bbb F}_{2} } \right)} = 0} \right]} = \left\{ {\begin{array}{*{20}c}{{0p = \frac{{2\log n - \omega {\left( n \right)}}}{n}}} \\ {{1p = \frac{{2\log n + \omega {\left( n \right)}}}{n}}} \\ \end{array} } \right.$$ <s> BIB001 </s> Topology of random geometric complexes: a survey <s> Introduction <s> 1. Introduction 2. Probabilistic ingredients 3. Subgraph and component counts 4. Typical vertex degrees 5. Geometrical ingredients 6. Maximum degree, cliques and colourings 7. Minimum degree: laws of large numbers 8. Minimum degree: convergence in distribution 9. Percolative ingredients 10. Percolation and the largest component 11. The largest component for a binomial process 12. Ordering and partitioning problems 13. Connectivity and the number of components References Index <s> BIB002 </s> Topology of random geometric complexes: a survey <s> Introduction <s> Recently there has been a lot of interest in geometrically motivated approaches to data analysis in high-dimensional spaces. We consider the case where data are drawn from sampling a probability distribution that has support on or near a submanifold of Euclidean space. We show how to “learn” the homology of the submanifold with high confidence. We discuss an algorithm to do this and provide learning-theoretic complexity bounds. Our bounds are obtained in terms of a condition number that limits the curvature and nearness to self-intersection of the submanifold. We are also able to treat the situation where the data are “noisy” and lie near rather than on the submanifold in question. <s> BIB003 </s> Topology of random geometric complexes: a survey <s> Introduction <s> We study Linial-Meshulam random 2-complexes, which are two-dimensional analogues of Erd\H{o}s-R\'enyi random graphs. We find the threshold for simple connectivity to be p = n^{-1/2}. This is in contrast to the threshold for vanishing of the first homology group, which was shown earlier by Linial and Meshulam to be p = 2 log(n)/n. We use a variant of Gromov's local-to-global theorem for linear isoperimetric inequalities to show that when p = O(n^{-1/2 -\epsilon}) the fundamental group is word hyperbolic. Along the way we classify the homotopy types of sparse 2-dimensional simplicial complexes and establish isoperimetric inequalities for such complexes. These intermediate results do not involve randomness and may be of independent interest. <s> BIB004 </s> Topology of random geometric complexes: a survey <s> Introduction <s> This article surveys recent work of Carlsson and collaborators on applications of computational algebraic topology to problems of feature detection and shape recognition in high-dimensional data. The primary mathematical tool considered is a homology theory for point-cloud data sets — persistent homology — and a novel representation of this algebraic characterization — barcodes. We sketch an application of these techniques to the classification of natural images. 1. The shape of data When a topologist is asked, “How do you visualize a four-dimensional object?” the appropriate response is a Socratic rejoinder: “How do you visualize a threedimensional object?” We do not see in three spatial dimensions directly, but rather via sequences of planar projections integrated in a manner that is sensed if not comprehended. We spend a significant portion of our first year of life learning how to infer three-dimensional spatial data from paired planar projections. Years of practice have tuned a remarkable ability to extract global structure from representations in a strictly lower dimension. The inference of global structure occurs on much finer scales as well, with regards to converting discrete data into continuous images. Dot-matrix printers, scrolling LED tickers, televisions, and computer displays all communicate images via arrays of discrete points which are integrated into coherent, global objects. This also is a skill we have practiced from childhood. No adult does a dot-to-dot puzzle with anything approaching anticipation. 1.1. Topological data analysis. Problems of data analysis share many features with these two fundamental integration tasks: (1) how does one infer high dimensional structure from low dimensional representations; and (2) how does one assemble discrete points into global structure. The principal themes of this survey of the work of Carlsson, de Silva, Edelsbrunner, Harer, Zomorodian, and others are the following: (1) It is beneficial to replace a set of data points with a family of simplicial complexes, indexed by a proximity parameter. This converts the data set into global topological objects. (2) It is beneficial to view these topological complexes through the lens of algebraic topology — specifically, via a novel theory of persistent homology adapted to parameterized families. (3) It is beneficial to encode the persistent homology of a data set in the form of a parameterized version of a Betti number: a barcode. The author gratefully acknowledges the support of DARPA # HR0011-07-1-0002. The work reviewed in this article is funded by the DARPA program TDA: Topological Data Analysis. <s> BIB005 </s> Topology of random geometric complexes: a survey <s> Introduction <s> Let Δn-1 denote the (n - 1)-dimensional simplex. Let Y be a random k-dimensional subcomplex of Δn-1 obtained by starting with the full (k - 1)-dimensional skeleton of Δn-1 and then adding each k-simplex independently with probability p. Let Hk-1(Y; R) denote the (k - 1)-dimensional reduced homology group of Y with coefficients in a finite abelian group R. It is shown that for any fixed R and k ≥ 1 and for any function ω(n) that tends to infinity $${\mathop{\rm lim}\limits_{n \rightarrow \infty}}{\Pr}[H_{k-1} \; (Y;R)= 0]=\left\{ \eqalign {&{0 \quad p= {k\; {\rm log}\;n-\omega(n) \over n }} \cr & 1 \quad p={k\; {\rm log}\; n + \omega (n) \over n}. } \right. $$ © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009 <s> BIB006 </s> Topology of random geometric complexes: a survey <s> Introduction <s> In this paper, we take a topological view of unsupervised learning. From this point of view, clustering may be interpreted as trying to find the number of connected components of any underlying geometrically structured probability distribution in a certain sense that we will make precise. We construct a geometrically structured probability distribution that seems appropriate for modeling data in very high dimensions. A special case of our construction is the mixture of Gaussians where there is Gaussian noise concentrated around a finite set of points (the means). More generally we consider Gaussian noise concentrated around a low dimensional manifold and discuss how to recover the homology of this underlying geometric core from data that do not lie on it. We show that if the variance of the Gaussian noise is small in a certain sense, then the homology can be learned with high confidence by an algorithm that has a weak (linear) dependence on the ambient dimension. Our algorithm has a natural interpretation as a spectral learning algorithm using a combinatorial Laplacian of a suitable data-derived simplicial complex. <s> BIB007 </s> Topology of random geometric complexes: a survey <s> Introduction <s> Cech and Vietoris-Rips complexes. In particular, we obtain results about homology, as measured via the growth of Betti numbers, when the vertices are the points of a general stationary point process. This significantly extends earlier results in which the points were either iid observations or the points of a Poisson process. In dealing with general point processes, in which the points exhibit dependence such as attraction, or repulsion, we find phenomena quantitatively different from those observed in the iid and Poisson cases. From the point of view of topological data analysis, our results seriously impact on considerations of model (non) robustness for statistical inference. <s> BIB008 </s> Topology of random geometric complexes: a survey <s> Introduction <s> The homology groups of a manifold are important topological invariants that provide an algebraic summary of the manifold. These groups contain rich topological information, for instance, about the connected components, holes, tunnels and sometimes the dimension of the manifold. In earlier work, we have considered the statistical problem of estimating the homology of a manifold from noiseless samples and from noisy samples under several different noise models. We derived upper and lower bounds on the minimax risk for this problem. In this note we revisit the noiseless case. In previous work we used Le Cam's lemma to establish a lower bound that differed from the upper bound of Niyogi, Smale and Weinberger by a polynomial factor in the condition number. In this note we use a different construction based on the direct analysis of the likelihood ratio test to show that the upper bound of Niyogi, Smale and Weinberger is in fact tight, thus establishing rate optimal asymptotic minimax bounds for the problem. The techniques we use here extend in a straightforward way to the noisy settings considered in our earlier work. <s> BIB009 </s> Topology of random geometric complexes: a survey <s> Introduction <s> We introduce a consistent estimator for the homology (an algebraic structure representing connected components and cycles) of level sets of both density and regression functions. Our method is based on kernel estimation. We apply this procedure to two problems: 1) inferring the homology structure of manifolds from noisy observations, 2) inferring the persistent homology (a multi-scale extension of homology) of either density or regression functions. We prove consistency for both of these problems. In addition to the theoretical results we demonstrate these methods on simulated data for binary regression and clustering applications. <s> BIB010
In this expository article, we survey the rapidly emerging area of random geometric simplicial complexes. Random simplicial complexes may be viewed as higherdimensional generalizations of random graphs. Perhaps the most studied model of random graph is the Erdős-Rényi model G(n, p), where every edge appears independently with probability p. Textbooks overviewing this subject include those by Bollobás  and Janson, Luczak, and Rucinski  . Simplicial complex analogues of G(n, p) and their topological properties have been the subject of a lot of activity in recent years. See for example BIB001 , BIB006 , BIB004 , [31] , and the references in the survey article [32] . For certain applications, however, and especially for modeling real-world networks such as social networks, the edge-independent model G(n, p) is not considered to be particularly realistic. For example, we might expect in a social network that if we know that X is friends with Y and Z, then it becomes much more likely than it would be otherwise that Y is friends with Z. Many other models of random graphs have been studied in recent years, and one family of models that has received a lot of attention is the random geometric graphs-see Penrose's monograph BIB002 for an overview. The random geometric graph G(n, r) is made by choosing n points independently and identically distributed (i.i.d.), according to a probability measure on Euclidean space R d (or any other metric space), and these points correspond to the vertices of the graph. Two vertices x and y are connected by an edge if any only if the distance between x and y satisfies d(x, y) < r. Since one is usually interested in asymptotic properties as n → ∞, we usually think of the threshold distance r as a function of n. This is a very general setup, and many variations on this basic model have been studied. The most closely related model to the n points i.i.d. model is a geometric graph on a Poisson point process with expected number of points n. A Poisson point process replaces the independence of points with spatial independence. There is a lot of technology available for transferring theorems between these two models. See, for example, Section 1.7 of BIB002 . One might also consider more general point processes than Poisson. Recently Yogeshwaran and Adler BIB008 studied random geometric graphs and complexes over more general stationary point processes. This family includes certain attractive and repulsive point processes, as well as stationary determinantal processes. In addition, we can consider random geometric graphs in metric measure spaces, such as Riemannian manifolds equipped with probability measures. The topological and geometric properties of such graphs (and their higher-dimensional analogues) were recently studied in  . There are several natural ways of extending a geometric graph to a simplicial complex, in particular theČech complex and the Vietoris-Rips complex, whose definitions we review in Section 2. Our interest in the topology of random geometric complexes will be mostly confined to their homology. Briefly, if X is a topological space, its degree i-homology, denoted by H i (X) is a vector space. The dimension dim H 0 (X) the number of connected components of X, and for i > 0, H i (X) contains information about i-dimensional 'holes'. One motivation for studying the topological features random geometric complexes comes from topological data analysis (TDA). In TDA one builds a simplicial complex (or filtered simplicial complex) on data, and infers qualitative features of the data from homology (or persistent homology) of the point cloud. Studying the topology of random geometric complexes is related to developing probabilistic null hypothesis for topological statistics. We discuss this further in Section 8. The seminal work by Niyogi-Smale-Weinberger BIB003 BIB007 , introduced a probabilistic analysis to homology recovery algorithms. This was further extended in BIB009   BIB010 . For surveys of persistent homology in topological data analysis, see Carlsson [17] and Ghrist BIB005 . Studying the limiting behavior of random geometric complexes, the first observation we make is that there exist three main regimes for which the limiting properties of the complexes are significantly different. The term that controls the limiting behavior is nr d , which can be thought of as the average number of points in a ball of radius r (up to a constant). The subcritical (sometimes called 'sparse' or 'dust') regime, is when nr d → 0. In this regime the geometric complex is highly disconnected, and this is where homology first appears. The critical regime (sometimes called 'the thermodynamic regime') is when nr d → λ ∈ (0, ∞). Here, the dimension of homology reaches its peak linear growth, and this is also where percolation occurs (the formation of a 'giant' component) -see the discussion in Section 3.2. Finally, in the super-critical regime we have nr d → ∞. In this regime it is known that the number of components slowly decays, until we reach the connectivity threshold. An analogous process occurs for higher homology -cycles get filled, until eventually every i-cycle is a boundary and homology H i vanishes. But in contrast, for higher homology i ≥ 1 there is another phase transition where homology The rest of this survey is structured as follows. In Section 2 we present the concepts and notation that will be used later. Section 3 quickly reviews classical results about the connectivity of random geometric graphs for completeness. Section 4 presents a summary of the main results known to date about the limiting behavior of the homology of random geometric complexes. In Section 5 we review an alternative approach to study the homology of randomČech complexes using Morse theory for the distance function. Sections 6 and 7 review two extensions to the results in Section 4 -one for compact manifolds and the other for stationary point processes. In section 8 we discuss work in progress that studies the persistent homology generated by random geometric complexes. Finally, in Section 9 we present a list of open problems and future work in this area.