Vietoris-Rips Filtration

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

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]

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 [math]\displaystyle{ X }[/math] and a scale parameter (sometimes called the threshold or distance parameter) [math]\displaystyle{ r \in [0, \infty) }[/math], the Vietoris-Rips complex (with respect to [math]\displaystyle{ r }[/math]) is defined as [math]\displaystyle{ \mathbf{VR}_r(X) = \{ \emptyset \neq S \subseteq X \mid S \text{ finite}; \operatorname{diam} S \leq r \} }[/math], where [math]\displaystyle{ \operatorname{diam} S }[/math] is the diameter, i.e. the maximum distance of points lying in [math]\displaystyle{ S }[/math].[8]

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

[math]\displaystyle{ \mathbf{VR}(X) = \{ \mathbf{VR}_r (X) \}_{r \in [0, \infty)} }[/math]

If the non-negative real numbers [math]\displaystyle{ [0, \infty) }[/math] are viewed as a posetal category via the [math]\displaystyle{ \leq }[/math] relation, then the Vietoris-Rips filtration can be viewed as a functor [math]\displaystyle{ \mathbf{VR}(X) : [0, \infty) \to \mathbf{Simp} }[/math] 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 [math]\displaystyle{ \mathbf{Top} }[/math], 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 [math]\displaystyle{ k }[/math]-skeleton, i.e., the number of simplices up to dimension [math]\displaystyle{ k }[/math], of the Vietoris-Rips filtration is known to be [math]\displaystyle{ O\left(n^{k+1}\right) }[/math], where [math]\displaystyle{ n }[/math] is the number of points.[10] The size of the complete skeleton has precisely [math]\displaystyle{ 2^n - 1 }[/math] 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 [math]\displaystyle{ k }[/math].[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 [math]\displaystyle{ r_{\text{max}} \in [0, \infty) }[/math] such that [math]\displaystyle{ \mathbf{VR}_s(X) = \mathbf{VR}_{r_{\text{max}}}(X) }[/math] for all [math]\displaystyle{ s \geq r_{\text{max}} }[/math], and furthermore that the inclusion map [math]\displaystyle{ \mathbf{VR}_{s\to t}(X): \mathbf{VR}_{s}(X) \hookrightarrow \mathbf{VR}_{t}(X) }[/math] is an isomorphism for all but finitely many parameters [math]\displaystyle{ s \leq t }[/math]. 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 [math]\displaystyle{ \mathbb N }[/math], 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 [math]\displaystyle{ {n \choose 2} = n(n-1)/2 }[/math], since all [math]\displaystyle{ n }[/math] vertices are joined by an edge. Therefore the Vietoris-Rips filtration changes at [math]\displaystyle{ O(n^2) }[/math] steps, where [math]\displaystyle{ O(-) }[/math] 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 [math]\displaystyle{ \alpha }[/math], the Vietoris-Rips and Čech complexes on a finite set [math]\displaystyle{ X }[/math] of points in Euclidean space satisfy the inclusion relationship [math]\displaystyle{ \mathbf{VR}_\alpha (X) \subseteq \operatorname{\check{C}ech}_{\sqrt 2\alpha}(X) \subseteq \mathbf{VR}_{\sqrt 2\alpha}(X) }[/math], which is sometimes referred to as the Vietoris-Rips Lemma.[12] In general metric spaces, a straightforward application of the triangle inequality shows that [math]\displaystyle{ \mathbf{VR}_\alpha (X) \subseteq \operatorname{\check{C}ech}_{2\alpha}(X) \subseteq \mathbf{VR}_{2\alpha}(X) }[/math] for any scale parameter [math]\displaystyle{ \alpha }[/math].

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 [math]\displaystyle{ O(n) }[/math] size in [math]\displaystyle{ O(n \log n) }[/math] 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 [math]\displaystyle{ a \in [0, \infty) }[/math], 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 [math]\displaystyle{ a }[/math] defines a filtration of each complex in the Vietoris-Rips filtration, where the complexes get smaller as [math]\displaystyle{ a }[/math] 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 [math]\displaystyle{ (a,r) \in \mathbb R^\operatorname{op} \times \mathbb R }[/math], 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 [math]\displaystyle{ \gamma: X \to \mathbb R }[/math], where [math]\displaystyle{ \gamma }[/math] can be a density function, an eccentricity function, or any other function. Namely, each complex is defined via [math]\displaystyle{ \mathbf{F}\text{-}\mathbf{VR}_{a,r}(\gamma) = \mathbf{VR}_r (\gamma^{-1}[a, \infty)) }[/math], which yields a bifiltration indexed over [math]\displaystyle{ \mathbb R^\operatorname{op} \times [0, \infty) }[/math].[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 [math]\displaystyle{ \sigma_0 \subset \cdots\subset\sigma_m }[/math]. 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 [math]\displaystyle{ k }[/math]. The collection of all such complexes yields a bifiltration indexed over [math]\displaystyle{ [0, \infty)^{\operatorname{op}} \times [0, \infty) }[/math].[21]

References

  1. ↑ 1.0 1.1 Chazal, Frédéric; Oudot, Steve Y. (2013), Nielsen, Frank; Barbaresco, Frédéric, eds., "Interleaved Filtrations: Theory and Applications in Point Cloud Data Analysis", Geometric Science of Information (Berlin, Heidelberg: Springer Berlin Heidelberg) 8085: pp. 587–592, doi:10.1007/978-3-642-40020-9_65, ISBN 978-3-642-40019-3, http://link.springer.com/10.1007/978-3-642-40020-9_65, retrieved 2023-04-05 
  2. ↑ 2.0 2.1 2.2 Dey, Tamal K.; Shi, Dayu; Wang, Yusu (2019-01-30). "SimBa: An Efficient Tool for Approximating Rips-filtration Persistence via Simplicial Batch Collapse". ACM Journal of Experimental Algorithmics 24: 1.5:1–1.5:16. doi:10.1145/3284360. ISSN 1084-6654. https://doi.org/10.1145/3284360. 
  3. ↑ Oudot, Steve Y.; Sheehy, Donald R. (2013-06-17). "Zigzag zoology: rips zigzags for homology inference". Proceedings of the Twenty-ninth Annual Symposium on Computational Geometry. SoCG '13 (New York, NY, USA: Association for Computing Machinery): 387–396. doi:10.1145/2462356.2462371. ISBN 978-1-4503-2031-3. https://doi.org/10.1145/2462356.2462371. 
  4. ↑ Lee, Hyekyoung; Chung, Moo K.; Kang, Hyejin; Kim, Bung-Nyun; Lee, Dong Soo (2011). "Discriminative persistent homology of brain networks". 2011 IEEE International Symposium on Biomedical Imaging: From Nano to Macro: 841–844. doi:10.1109/ISBI.2011.5872535. ISBN 978-1-4244-4127-3. https://ieeexplore.ieee.org/document/5872535/;jsessionid=EZNTPzFc08Tk2MdVbttcE6ev01Li3fXvqhHf7iHVLJT4_mI8ZaOj!71486806. 
  5. ↑ Vietoris, L. (1927-12-01). "Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen" (in de). Mathematische Annalen 97 (1): 454–472. doi:10.1007/BF01447877. ISSN 1432-1807. https://doi.org/10.1007/BF01447877. 
  6. ↑ Gromov, M. (1987), Gersten, S. M., ed., "Hyperbolic Groups", Essays in Group Theory, Mathematical Sciences Research Institute Publications (New York, NY: Springer New York) 8: pp. 75–263, doi:10.1007/978-1-4613-9586-7_3, ISBN 978-1-4613-9588-1, http://link.springer.com/10.1007/978-1-4613-9586-7_3, retrieved 2023-04-05 
  7. ↑ Reitberger, Heinrich (2002), "Leopold Vietoris (1891–2002)", Notices of the American Mathematical Society, 49 (20).
  8. ↑ Bauer, Ulrich; Roll, Fabian (2022). Goaoc, Xavier; Kerber, Michael. eds. "Gromov Hyperbolicity, Geodesic Defect, and Apparent Pairs in Vietoris-Rips Filtrations". 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs) (Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik) 224: 15:1–15:15. doi:10.4230/LIPIcs.SoCG.2022.15. ISBN 978-3-95977-227-3. https://drops.dagstuhl.de/opus/volltexte/2022/16023. 
  9. ↑ 9.0 9.1 9.2 Lesnick, Michael (1 April 2023). "Lecture notes for AMAT 840: Multiparameter Persistence". University at Albany, SUNY: 33. https://www.albany.edu/~ML644186/840_2022/Math840_Notes_22.pdf. 
  10. ↑ 10.0 10.1 Sheehy, Donald R. (2012-06-17). "Linear-size approximations to the vietoris-rips filtration". Proceedings of the Twenty-eighth Annual Symposium on Computational Geometry. SoCG '12 (New York, NY, USA: Association for Computing Machinery): 239–248. doi:10.1145/2261250.2261286. ISBN 978-1-4503-1299-8. https://doi.org/10.1145/2261250.2261286. 
  11. ↑ Chambers, Erin W.; de Silva, Vin; Erickson, Jeff; Ghrist, Robert (2010). "Vietoris–Rips Complexes of Planar Point Sets" (in en). Discrete & Computational Geometry 44 (1): 75–90. doi:10.1007/s00454-009-9209-8. ISSN 0179-5376. http://link.springer.com/10.1007/s00454-009-9209-8. 
  12. ↑ Edelsbrunner, Herbert (2010). Computational topology : an introduction. J. Harer. Providence, R.I.: American Mathematical Society. ISBN 978-0-8218-4925-5. OCLC 427757156. https://www.worldcat.org/oclc/427757156. 
  13. ↑ Har-Peled, Sariel; Mendel, Manor (2006). "Fast Construction of Nets in Low-Dimensional Metrics and Their Applications" (in en). SIAM Journal on Computing 35 (5): 1148–1184. doi:10.1137/S0097539704446281. ISSN 0097-5397. http://epubs.siam.org/doi/10.1137/S0097539704446281. 
  14. ↑ Kerber, Michael; Sharathkumar, R. (2013). Cai, Leizhen; Cheng, Siu-Wing; Lam, Tak-Wah. eds. "Approximate Čech Complex in Low and High Dimensions" (in en). Algorithms and Computation. Lecture Notes in Computer Science (Berlin, Heidelberg: Springer) 8283: 666–676. doi:10.1007/978-3-642-45030-3_62. ISBN 978-3-642-45030-3. https://link.springer.com/chapter/10.1007/978-3-642-45030-3_62. 
  15. ↑ Sheehy, Donald R. (2020-12-03). "A Sparse Delaunay Filtration". arXiv:2012.01947 [cs.CG].
  16. ↑ Choudhary, Aruni; Kerber, Michael; Raghvendra, Sharath (2021-09-01). "Improved approximate rips filtrations with shifted integer lattices and cubical complexes" (in en). Journal of Applied and Computational Topology 5 (3): 425–458. doi:10.1007/s41468-021-00072-4. ISSN 2367-1734. PMID 34722862. PMC 8549989. https://doi.org/10.1007/s41468-021-00072-4. 
  17. ↑ Vishwanath, Siddharth; Sriperumbudur, Bharath K.; Fukumizu, Kenji; Kuriki, Satoshi (2022-06-03). "Robust Topological Inference in the Presence of Outliers". arXiv:2206.01795 [math.ST].
  18. ↑ Carlsson, Gunnar; Zomorodian, Afra (2009). "The Theory of Multidimensional Persistence" (in en). Discrete & Computational Geometry 42 (1): 71–93. doi:10.1007/s00454-009-9176-0. ISSN 0179-5376. http://link.springer.com/10.1007/s00454-009-9176-0. 
  19. ↑ Lesnick, Michael; Wright, Matthew (2015-12-01). "Interactive Visualization of 2-D Persistence Modules". arXiv:1512.00180 [math.AT].
  20. ↑ Botnan, Magnus Bakke; Lesnick, Michael (2023-03-13). "An Introduction to Multiparameter Persistence". arXiv:2203.14289 [math.AT].
  21. ↑ D. R. Sheehy, “A multicover nerve for geometric inference,” in CCCG: Canadian conference in computational geometry, 2012.




Retrieved from "https://handwiki.org/wiki/index.php?title=Vietoris-Rips_Filtration&oldid=3379739"