Vietoris–Rips filtration

In topological data analysis, the Vietoris–Rips filtration (sometimes shortened to "Rips filtration") is the collection of nested Vietoris–Rips complexes on a metric space created by taking the sequence of Vietoris–Rips complexes over an increasing scale parameter. Often, the Vietoris–Rips filtration is used to create a discrete, simplicial model on point cloud data embedded in an ambient metric space.^[1] The Vietoris–Rips filtration is a multiscale extension of the Vietoris–Rips complex that enables researchers to detect and track the persistence of topological features, over a range of parameters, by way of computing the persistent homology of the entire filtration.^[2][3][4] It is named after Leopold Vietoris and Eliyahu Rips.

A set of three nested subcomplexes within the Vietoris–Rips filtration on a set of points in the Euclidean plane.

Definition

The Vietoris–Rips filtration is the nested collection of Vietoris–Rips complexes indexed by an increasing scale parameter. The Vietoris–Rips complex is a classical construction in mathematics that dates back to a 1927 paper^[5] of Leopold Vietoris, though it was independently considered by Eliyahu Rips in the study of hyperbolic groups, as noted by Mikhail Gromov in the 1980s.^[6] The conjoined name "Vietoris–Rips" is due to Jean-Claude Hausmann.^[7]

An example of a Vietoris–Rips complex built on points in the Euclidean plane.

Given a metric space ${\displaystyle X}$ and a scale parameter (sometimes called the threshold or distance parameter) ${\displaystyle r\in [0,\infty )}$, the Vietoris–Rips complex (with respect to ${\displaystyle r}$) is defined as ${\displaystyle \mathbf {VR} _{r}(X)=\{\emptyset \neq S\subseteq X\mid S{\text{ finite}};\operatorname {diam} S\leq r\}}$, where ${\displaystyle \operatorname {diam} S}$ is the diameter, i.e. the maximum distance of points lying in ${\displaystyle S}$.^[8]

Observe that if ${\displaystyle r\leq s\in [0,\infty )}$, there is a simplicial inclusion map ${\displaystyle \mathbf {VR} _{r}(X)\hookrightarrow \mathbf {VR} _{s}(X)}$ . The Vietoris–Rips filtration is the nested collection of complexes ${\displaystyle \mathbf {VR} _{r}(X)}$ :

$${\displaystyle \mathbf {VR} (X)=\{\mathbf {VR} _{r}(X)\}_{r\in [0,\infty )}}$$

If the non-negative real numbers ${\displaystyle [0,\infty )}$ are viewed as a posetal category via the ${\displaystyle \leq }$ relation, then the Vietoris–Rips filtration can be viewed as a functor ${\displaystyle \mathbf {VR} (X):[0,\infty )\to \mathbf {Simp} }$ valued in the category of simplicial complexes and simplicial maps, where the morphisms (i.e., relations in the poset) in the source category induce inclusion maps among the complexes.^[9] Note that the category of simplicial complexes may be viewed as a subcategory of ${\displaystyle \mathbf {Top} }$, the category of topological spaces, by post-composing with the geometric realization functor.

Properties

The size of a filtration refers to the number of simplices in the largest complex, assuming the underlying metric space is finite. The ${\displaystyle k}$-skeleton, i.e., the number of simplices up to dimension ${\displaystyle k}$, of the Vietoris–Rips filtration is known to be ${\displaystyle O\left(n^{k+1}\right)}$, where ${\displaystyle n}$ is the number of points.^[10] The size of the complete skeleton has precisely ${\displaystyle 2^{n}-1}$ simplices, one for each non-empty subset of points.^[9] Since this is exponential, researchers usually only compute the skeleton of the Vietoris–Rips filtration up to small values of ${\displaystyle k}$.^[2]

When the underlying metric space is finite, the Vietoris–Rips filtration is sometimes referred to as essentially discrete,^[9] meaning that there exists some terminal or maximum scale parameter ${\displaystyle r_{\text{max}}\in [0,\infty )}$ such that ${\displaystyle \mathbf {VR} _{s}(X)=\mathbf {VR} _{r_{\max }}(X)}$ for all ${\displaystyle s\geq r_{\max }}$, and furthermore that the inclusion map ${\displaystyle \mathbf {VR} _{s\to t}(X):\mathbf {VR} _{s}(X)\hookrightarrow \mathbf {VR} _{t}(X)}$ is an isomorphism for all but finitely many parameters ${\displaystyle s\leq t}$. In other words, when the underlying metric space is finite, the Vietoris–Rips filtration has a largest complex, and the complex changes at only a finite number of steps. The latter implies that the Vietoris–Rips filtration on a finite metric space can be considered as indexed over a discrete set such as ${\displaystyle \mathbb {N} }$, by restricting the filtration to the scale parameters at which the filtration changes, then relabeling the complexes using the natural numbers.

An explicit bound can also be given for the number of steps at which the Vietoris–Rips filtration changes. The Vietoris–Rips complex is a clique complex, meaning it is entirely determined by its 1-skeleton.^[11] Therefore the number of steps at which the Vietoris–Rips filtration changes is bounded by the number of edges in the largest complex. The number of edges in the largest complex is ${\displaystyle {n \choose 2}=n(n-1)/2}$, since all ${\displaystyle n}$ vertices are joined by an edge. Therefore the Vietoris–Rips filtration changes at ${\displaystyle O(n^{2})}$ steps, where ${\displaystyle O(-)}$ denotes an asymptotic upper bound.

For points in Euclidean space, the Vietoris–Rips filtration is an approximation to the Čech filtration, in the sense of the interleaving distance.^[1] This follows from the fact that for any scale parameter ${\displaystyle \alpha }$, the Vietoris–Rips and Čech complexes on a finite set ${\displaystyle X}$ of points in Euclidean space satisfy the inclusion relationship ${\displaystyle \mathbf {VR} _{\alpha }(X)\subseteq \operatorname {{\check {C}}ech} _{{\sqrt {2}}\alpha }(X)\subseteq \mathbf {VR} _{{\sqrt {2}}\alpha }(X)}$, which is sometimes referred to as the Vietoris–Rips Lemma.^[12] In general metric spaces, a straightforward application of the triangle inequality shows that ${\displaystyle \mathbf {VR} _{\alpha }(X)\subseteq \operatorname {{\check {C}}ech} _{2\alpha }(X)\subseteq \mathbf {VR} _{2\alpha }(X)}$ for any scale parameter ${\displaystyle \alpha }$.

Variants

Approximations

Since the Vietoris–Rips filtration has an exponential number of simplices in its complete skeleton, a significant amount of research has been done on approximating the persistent homology of the Vietoris–Rips filtration using constructions of smaller size. The first work in this direction was published by computer scientist Donald Sheehy in 2012, who showed how to construct a filtration of ${\displaystyle O(n)}$ size in ${\displaystyle O(n\log n)}$ time that approximates the persistent homology of the Vietoris–Rips filtration to a desired margin of error.^[10] This type of filtration is known as a Sparse Vietoris–Rips filtration, since it removes points from the standard Vietoris–Rips filtration using ideas from computational geometry related to geometric spanners.^[13] Since then, there have been several more efficient methods developed for approximating the Vietoris–Rips filtration, mostly using the ideas of Sheehy, but also building upon approximation schemes developed for the Čech^[14] and Delaunay^[15] filtrations.^[16][2]

Multiparameter Extensions

It is known that persistent homology can be sensitive to outliers in the underlying data set.^[17] To remedy this, in 2009 Gunnar Carlsson and Afra Zomorodian proposed a multidimensional version of persistence, that considers filtrations with respect to multiple parameters, such as scale and density.^[18]

To that end, several multiparameter extensions of the Vietoris–Rips filtration have been developed.

• The Degree-Rips bifiltration extends the Vietoris–Rips filtration by constructing a sub-graph of the 1-skeleton of each complex in the Vietoris–Rips filtration, restricting only to vertices whose degree is at least a given parameter ${\displaystyle a\in [0,\infty )}$, then building the clique complex on that subgraph. The degree of a vertex encodes density information about the data, because it is quantifies how "central" that point is by way of how many other vertices it is connected to. The collection over all degree parameters ${\displaystyle a}$ defines a filtration of each complex in the Vietoris–Rips filtration, where the complexes get smaller as ${\displaystyle a}$ increases. Altogether, this defines a 2-parameter extension of the Vietoris–Rips filtration, by considering the collection of bi-filtered complexes over all scale parameters ${\displaystyle (a,r)\in \mathbb {R} ^{\operatorname {op} }\times \mathbb {R} }$, where "op" denotes the opposite poset.^[19]
• The Function-Rips bifiltration extends the Vietoris–Rips filtration by bifiltering each complex according to the superlevel-sets of some function ${\displaystyle \gamma :X\to \mathbb {R} }$, where ${\displaystyle \gamma }$ can be a density function, an eccentricity function, or any other function. Namely, each complex is defined via ${\displaystyle \mathbf {F} {\text{-}}\mathbf {VR} _{a,r}(\gamma )=\mathbf {VR} _{r}(\gamma ^{-1}[a,\infty ))}$, which yields a bifiltration indexed over ${\displaystyle \mathbb {R} ^{\operatorname {op} }\times [0,\infty )}$.^[20]
• The subdivision-Rips bifiltration extends the Vietoris–Rips filtration by taking the barycentric subdivision of each complex in the Vietoris–Rips filtration, then filtering these complexes by dimension of each flag. Namely, the barycentric subdivision of a simplicial complex is the abstract simplicial complex defined using flags of simplices in the underlying complex, where a flag (sometimes called a chain) is a nested series of simplices ${\displaystyle \sigma _{0}\subset \cdots \subset \sigma _{m}}$. Then given the barycentric subdivision of a complex, one can filter it by taking the subcomplex spanned by vertices corresponding to simplices in the original complex of some minimum dimension ${\displaystyle k}$. The collection of all such complexes yields a bifiltration indexed over ${\displaystyle [0,\infty )^{\operatorname {op} }\times [0,\infty )}$.^[21]