Vietoris-Rips Filtration

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.

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_{\text{max}}}(X)}$ for all ${\displaystyle s\geq r_{\text{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 }$.