The Vietoris-Rips filtration for an @math -point metric space is a sequence of large simplicial complexes adding a topological structure to the otherwise disconnected space. The persistent homology is a key tool in topological data analysis and studies topological features of data that persist over many scales. The fastest algorithm for computing persistent homology of a filtration has time @math , where @math is the number of updates (additions or deletions of simplices), @math is the time for multiplication of @math matrices. For a space of @math points given by their pairwise distances, we approximate the Vietoris-Rips filtration by a zigzag filtration consisting of @math updates, which is sublinear in @math . The constant depends on a given error of approximation and on the doubling dimension of the metric space. Then the persistent homology of this sublinear-size filtration can be computed in time @math , which is subquadratic in @math .
If we run the best algorithm @cite_3 @cite_2 for persistent homology on the Sheehy approximation to the Vietoris-Rips filtration, the overall running time for approximating persistent homology will be @math . This overquadratic time is a bottleneck, but allows us to replace a sophisticated construction of a net-tree by a simpler algorithm for @math -farthest neighbors in a metric space.
@cite_3 @cite_2
2963754066 1900583485 2908292748 2408772186
A standard way of approximating or discretizing a metric space is by taking its Rips complexes. These approximations for all parameters are often bound together into a filtration, to which we apply the fundamental group or the first homology. We call the resulting object persistence. Recent results demonstrate that persistence of a compact geodesic locally contractible space X carries a lot of geometric information. However, by definition the corresponding Rips complexes have uncountably many vertices. In this paper we show that nonetheless, the whole persistence of X may be obtained by an appropriate finite sample (subset of X), and that persistence of any subset of X is well interleaved with the persistence of X. It follows that the persistence of X is the minimum of persistences obtained by all finite samples. Furthermore, we prove a much improved Stability theorem for such approximations. As a special case we provide for each (r>0 ) a density (s>0 ), so that for each s-dense sample (S X ) the corresponding fundamental group (and the first homology) of the Rips complex of S is isomorphic to the one of X, leading to an improved reconstruction result. Given a metric space X and a distance threshold r>0, the Vietoris-Rips simplicial complex has as its simplices the finite subsets of X of diameter less than r. A theorem of Jean-Claude Hausmann states that if X is a Riemannian manifold and r is sufficiently small, then the Vietoris-Rips complex is homotopy equivalent to the original manifold. Little is known about the behavior of Vietoris-Rips complexes for larger values of r, even though these complexes arise naturally in applications using persistent homology. We show that as r increases, the Vietoris-Rips complex of the circle obtains the homotopy types of the circle, the 3-sphere, the 5-sphere, the 7-sphere, ..., until finally it is contractible. As our main tool we introduce a directed graph invariant, the winding fraction, which in some sense is dual to the circular chromatic number. Using the winding fraction we classify the homotopy types of the Vietoris-Rips complex of an arbitrary (possibly infinite) subset of the circle, and we study the expected homotopy type of the Vietoris-Rips complex of a uniformly random sample from the circle. Moreover, we show that as the distance parameter increases, the ambient Cech complex of the circle also obtains the homotopy types of the circle, the 3-sphere, the 5-sphere, the 7-sphere, ..., until finally it is contractible. We inspect Vietoris-Rips complexes @math of certain metric spaces @math using a new generalization of Bestvina-Brady discrete Morse theory. Our main result is a pair of metric criteria on @math , called the Morse Criterion and Link Criterion, that allow us to deduce information about the homotopy types of certain @math . One application is to topological data analysis, specifically persistence of homotopy type for certain Vietoris-Rips complexes. For example we recover some results of Adamaszek-Adams and Hausmann regarding homotopy types of @math . Another application is to geometric group theory; we prove that any group acting geometrically on a metric space satisfying a version of the Link Criterion admits a geometric action on a contractible simplicial complex, which has implications for the finiteness properties of the group. This applies for example to asymptotically @math groups. We also prove that any group with a word metric satisfying the Link Criterion in an appropriate range has a contractible Vietoris-Rips complex, and use combings to exhibit a family of groups with this property. Persistent homology captures the evolution of topological features of a model as a parameter changes. The most commonly used summary statistics of persistent homology are the barcode and the persistence diagram. Another summary statistic, the persistence landscape, was recently introduced by Bubenik. It is a functional summary, so it is easy to calculate sample means and variances, and it is straightforward to construct various test statistics. Implementing a permutation test we detect conformational changes between closed and open forms of the maltose-binding protein, a large biomolecule consisting of 370 amino acid residues. Furthermore, persistence landscapes can be applied to machine learning methods. A hyperplane from a support vector machine shows the clear separation between the closed and open proteins conformations. Moreover, because our approach captures dynamical properties of the protein our results may help in identifying residues susceptible to ligand binding; we show that the majority of active site residues and allosteric pathway residues are located in the vicinity of the most persistent loop in the corresponding filtered Vietoris-Rips complex. This finding was not observed in the classical anisotropic network model.