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. 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.
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 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. The conjoined name "Vietoris-Rips" is due to Jean-Claude Hausmann.
Given a metric space and a scale parameter (sometimes called the threshold or distance parameter) , the Vietoris-Rips complex (with respect to ) is defined as , where is the diameter, i.e. the maximum distance of points lying in .
Observe that if , there is a simplicial inclusion map . The Vietoris-Rips filtration is the nested collection of complexes :
If the non-negative real numbers are viewed as a posetal category via the relation, then the Vietoris-Rips filtration can be viewed as a functor 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. Note that the category of simplicial complexes may be viewed as a subcategory of , 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 -skeleton, i.e., the number of simplices up to dimension , of the Vietoris-Rips filtration is known to be , where is the number of points. The size of the complete skeleton has precisely simplices, one for each non-empty subset of points. Since this is exponential, researchers usually only compute the skeleton of the Vietoris-Rips filtration up to small values of .
When the underlying metric space is finite, the Vietoris-Rips filtration is sometimes referred to as essentially discrete, meaning that there exists some terminal or maximum scale parameter such that for all , and furthermore that the inclusion map is an isomorphism for all but finitely many parameters . 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 , 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. 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 , since all vertices are joined by an edge. Therefore the Vietoris-Rips filtration changes at steps, where 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. This follows from the fact that for any scale parameter , the Vietoris-Rips and Čech complexes on a finite set of points in Euclidean space satisfy the inclusion relationship , which is sometimes referred to as the Vietoris-Rips Lemma. In general metric spaces, a straightforward application of the triangle inequality shows that for any scale parameter .