Topology of random geometric complexes: a survey <s> Persistent homology <s> Assume that a finite set of points is randomly sampled from a subspace of a metric space. Recent advances in computational topology have provided several approaches to recovering the geometric and topological properties of the underlying space. In this paper we take a statistical approach to this problem. We assume that the data is randomly sampled from an unknown probability distribution. We define two filtered complexes with which we can calculate the persistent homology of a probability distribution. Using statistical estimators for samples from certain families of distributions, we show that we can recover the persistent homology of the underlying distribution. <s> BIB001 </s> Topology of random geometric complexes: a survey <s> Persistent homology <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> BIB002
In this section we will overview some recent work in progress on persistent homology of random geometric complexes  . Briefly, persistent homology tracks the evolution of the homology of the complex as the radius r changes from zero to infinity. For survey articles on persistent homology see [17] and BIB002 . One of the outputs provided by persistent homology is a pair of values (b γ , d γ ) assigned to every non-trivial cycle γ, that represent the radii at which γ appear and vanish (born and dies), respectively. Traditionally, the persistence (or significance) of a cycle γ is measured by the difference d γ − b γ . Here, we wish measure the persistence of γ by the ratio p γ := d γ /b γ . There are a number of reasons to measure the persistence of a cycle multiplicatively. • The persistence measured this way is scale invariant, i.e. the persistence of cycles for n points chosen uniformly in a cube [0,  d will have the same distribution as for n points chosen uniformly in a cube [0, λ] d for any λ > 0. • In a random geometric setting, one issue with measuring persistence by just be a small error term and it will be hard to differentiate between them. The multiplicative way of measuring persistence is more informative. • BothČech complexes C(n, r) and Vietoris-Rips complexes R(n, r) are central to the theory of persistent homology, and it is important to be able to compare them. The standard way of relating them is via the inclusion maps . . . → C(n, r) → R(n, r) → C(n, √ 2r) → R(n, √ 2r) → . . . So one may relate persistent homology between the two types of complexes. Because this relationship is naturally multiplicative in r, our results are stated in a way that holds for both types of complexes. We will assume that the distribution is uniform on a convex body. However, similar results should hold for any measurable function f on a 2-dimensional manifold with boundary, provided that f is bounded from below and above. , where the maximum is taken over all non-trivial i-cycles γ. The implied constants in the asymptotic notation Θ only depend on the underlying probability distribution. The last theorem is an example for the results studied in  . Persistent homology is becoming a very popular and powerful data analysis tool. Studying this type of extreme value behavior for persistent homology, can be later used to provide a statistical analysis to persistent homology. For example, suppose that the data are sampled from a distribution supported on a manifold M with non trivial homology that we wish to recover. Knowing the distribution of p (i) max for convex bodies (where homology is trivial), would enable us to develop statistical tests to differentiate between the signal (real cycles of M) and noise (artifacts of the sampling mechanism) in this type of data analysis problems. Persistent homology in random contexts was studied earlier by Bubenik and Kim in BIB001 .