Suppose we are given a finite set, , of points in . The set of points is topologically uninteresting. How can we fix this? Yes, you guessed it: we can construct a Vietoris Rips (Rips) complex from the points in ! The Rips Filtration is a specific nested sequence of Rips complexes over . Both provide geometric and topological information about our point set. In this tutorial, we explore this idea and how a Rips complex and filtration can be used to better understand data sets.
By the end of this tutorial you should be able to:
- Define Abstract Simplicial Complexes.
- Compute a Rips complex and Rips filtration from a finite set of points in by hand.
- Compute a Rips Filtration from a finite set of points in using the R-TDA package.
- Name a few applications of the Rips complexes and filtrations.
First, we breifly describe the mathematical foundations behind a Rips Filtration including abstract simplicial complexes, filtrations, and the Rips complex. Computation Topology: An Introduction provides more details on the theory (Edelsbrunner & Harer, 2010).
We construct a Rips complex from simplices of varying dimensions that are generalizations of triangles of varying dimensions. More specifically, an n-simplex is the smallest convex set of points, where are linearly independent.
An abstract simplicial complex is a finite collection of sets, , that is closed under the subset relation, i.e., if and , then . The elements are the simplices where dimcard. Here, card is the number of points in the set, .
Let be finite set of points in . Let . The Rips complex of and is the abstract simplicial complex of consisting of all subsets of diameter at most :
where the diameter of a set of points is the maximum distance between any two points in the set.
Geometrically, we can constuct the Rips complex by considering balls of radius , centered at each point in . Whenever balls have pairwise intersections, we add a dimensional simplex. For this tutorial, we use the standard Euclidean distance (unless stated otherwise) to compute a Rips complex.
You may be familiar with contact graphs where the vertices represent a geometric object such as a circle, curve, or polygon, and an edge between two vertices exists if the corresponding two objects intersect. The Rips complex is a generalization of contact graphs.
Here are some examples of Rips complexes:
Note: Many people also define . However, the algorithms used in the R-TDA package use the first definition.
A filtration of a simplicial complex, , is a nested sequence of subcomplexes starting at the empty set and ending with the full simplicial complex, i.e.,
Going back to the Rips complex, we consider to be a free parameter. If we vary , we get different Rips complexes. In many data analysis situations, the value of that best describes the data is unknown or does not exist, so why not look at all of them!? Observe if we increase continuously, then we get a family of nested Rips complexes; the Rips filtration.
Let’s work through an example. Let . We want to compute a Rips filtration on for all .
- When , none of the balls of radius intersect and so ) is four points.
- When , the balls of radius centered at and intersect which means we add a 1-simplex between and . Similarly, we add a 1-simplex between and .
- When , no additional balls of radius intersect which means ).
- When , we add a two more 1-simplices between , and .
- When ,
- When , we add two 2-simplices between and .
- When ,
- When , we add a 3-simplex.
- When ,
Applications of Rips Complexes and Filtrations
Now that we have discussed the theory, let’s talk about some of the applications! A Rips filtration is used on point cloud data or more generally on a data set where there is some notion of distance between all data points. A common form of these types of data are location data. For example, coordinates of galaxies in the Universe and GPS coordinates of airports on Earth.
The Rips complex provides information on how close the data points are to each other. Furthermore, the holes in the complex can provide information on where data are not present. Lastly, the topological information given by taking a Rips filtration can be studied using persistent homology (tutorial to come soon!).
Another application is studying coverage in sensor networks. The problem is to look at a set of sensors and find how much coverage the sensors provide. Robert Ghrist and Vin de Silva studied this problem using Rips complexes since the complex can be determined easily from pairwise communication data (Silva & Ghrist, 2007).
Furthermore, Rips complexes can be used in shape reconstruction. Dominque Attali, Andre Lieutier, and David Salinas proved that the Rips complex of a point cloud, , at some threshold has the same homotopy type as the union of balls centered around each point in with radius (Attali, Lieutier, & Salinas, 2013). Rips complexes are nice to use for shape reconstruction since they do not favor a specific type of alignment of the input.
These are just a few of the applications. There are many more!
Computing the Rips Filtration using the R-TDA Package
First, let’s go back to the example where . We compute the Rips filtration using the R-TDA package.
Great! So how do we interpret the RipsFilt object?
The ripsFiltration function returns a list:
- complx is a list where the element is a vector of the vertices for the simplex.
- values is a vector where the entry is the filtration value for the simplex.
- increasing is a logical variable that states TRUE if the filtration values in the values vector are in increasing order and FALSE if the filtration values are in decreasing order.
- coordinates is a matrix representing the coordinates of the vertices. The row is the coordinate for the vertex. Note the coordinates matrix appears only if the Euclidean distance is used.
See the documentation for this function with this link. Let’s check this out.
Our output tells us that we have a 2-simplex on vertices . Let’s see at which filtration value this appears.
So we have a 2-simplex when . We also found this by hand! Accessing the other complex and filtration value elements verifies the rest of the filtration computation we did earlier.
If we want to see an animation of the Rips filtration, we can run the following code with a plot function. This function has input arguments:
- filt is the Rips filtration object. (So, Ripsfilt from above)
- animate is a logical variable stating TRUE if you want an animation of the filtration or FALSE if you do not want an animation.
- thresh is the threshold value for the Rips complex that will be plotted if animate = FALSE.
- fn_out is the name of the file for the animation if animate = TRUE.
- l_out is the number of levels of radii used in the animation between 0 and 1.1 times the max distance between any two points if animate = TRUE.
Note this function only works if the data set is two dimensional and the Euclidean distance is used.
Furthermore, we can look at the Rips complex at a threshold of , by adding the argument, thresh = and changing animate = FALSE to animate = TRUE.
Non-Euclidean Distance Example
Now we compute a Rips filtration on , but this time using the Manhattan distance or norm. Recall, that for points, and , the Manhattan distance, is defined as:
In order to compute the Rips filtration on , we need to create a distance matrix in R. We can do this using the following code:
When we use the ripsFiltration function, we write DistMatrix as the first argument instead of . Additionally, the fourth argument will change to dist = “arbitrary” to indicate that we are giving our own distance metric.
This time when we compute the Rips complex with , we get the following complex:
Hence with the Manhattan distance is a simplicial complex with two edges, while with the Euclidean distance is a simplicial complex with two 2-simplices.
Sightings of Bigfoot in Montana
Lastly, we work through an example with real data! The Bigfoot Field Researchers Organization (BFRO) is the only scientific research organization studying the Bigfoot/Sasquatch mystery. They publically provide all Bigfoot sighting reports on their website. We will compute the Rips filtration for Bigfoot sightings in Montana with the hope of finding the where Bigfoot is and is not roaming. Finding the deadzones where Bigfoot is not present could help keep hikers safe from potential encounters.
We can plot the data using the following code.
Now, let’s compute the filtration and visualize it with an animation. In order to speed up the computation, we will set maxscale = 2.5 and maxdimension = 3.
Furthermore, we can look at the Rips complex at a threshold of 0.8.
As we watch the animation, we see that the Rips filtration captures geometric properties about the data set since simplices quickly arise in the filtraion in the locations that reported the most bigfoot sightings. Furthermore, we see the filtration also reveals some topological information about the data set. In particular, at a filtration value of 0.698812, five edges that form a cycle appear around the GPS coordinate (-111, 46). Furthermore, this cycle persists until the filtration value of 0.94698369. Considering the amount of land that is covered in 1 longitude/latitude unit, this cycle could tell us something meaningful about our data. Perhaps this hole is a deadzone where Bigfoot has yet to be found, or maybe this area is inaccessible to humans and that is why there has not been sightings. Regardless of the answer, this cycle provides us guidance for the next step to take to solve the Bigfoot mystery!
- Edelsbrunner, H., & Harer, J. (2010). Computational Topology - an Introduction. (pp. 1–241). American Mathematical Society.
- Silva, V. de, & Ghrist, R. (2007). Coverage in Sensor Networks via Persistent Homology. Algebraic & Geometric Topology, 7. https://doi.org/10.2140/agt.2007.7.339
- Attali, D., Lieutier, A., & Salinas, D. (2013). Vietoris–Rips Complexes also Provide Topologically Correct Reconstructions of Sampled Shapes. Computational Geometry, 46(4), 448–465. https://doi.org/https://doi.org/10.1016/j.comgeo.2012.02.009