Degree-Rips bifiltration

From HandWiki
Short description: Degree-Rips Bifiltration

The degree-Rips bifiltration is a simplicial filtration used in topological data analysis for analyzing the shape of point cloud data. It is a multiparameter extension of the Vietoris–Rips filtration that possesses greater stability to data outliers than single-parameter filtrations, and which is more amenable to practical computation than other multiparameter constructions. Introduced in 2015 by Lesnick and Wright, the degree-Rips bifiltration is a parameter-free and density-sensitive vehicle for performing persistent homology computations on point cloud data.[1]

Definition

It is standard practice in topological data analysis (TDA) to associate a sequence of nested simplicial complexes to a finite data set in order to detect the persistence of topological features over a range of scale parameters. One way to do this is by considering the sequence of Vietoris–Rips complexes of a finite set in a metric space indexed over all scale parameters.

If [math]\displaystyle{ X }[/math] is a finite set in a metric space, then this construction is known as the Vietoris–Rips (or simply "Rips") filtration on [math]\displaystyle{ X }[/math], commonly denoted [math]\displaystyle{ \text{Rips}(X) }[/math] or [math]\displaystyle{ \mathcal R (X) }[/math].[2][3][4] The Rips filtration can be expressed as a functor [math]\displaystyle{ \text{Rips}(X): \mathbb R \to \mathbf{Simp} }[/math] from the real numbers (viewed as a poset category) to the category of simplicial complexes and simplicial maps, a subcategory of the category [math]\displaystyle{ \mathbf{Top} }[/math] of topological spaces and continuous maps via the geometric realization functor.[5]

The Rips filtration is indexed over a single parameter, but we can capture more information (e.g., density) about the underlying data set by considering multiparameter filtrations. A filtration indexed by the product of two totally-ordered sets is known as a bifiltration, first introduced by Gunnar Carlsson and Afra Zomorodian in 2009.[6]

The degree-Rips bifiltration filters each simplicial complex in the Rips filtration by the degree of each vertex in the graph isomorphic to the 1-skeleton at each index. More formally, let [math]\displaystyle{ (a,b) }[/math] be an element of [math]\displaystyle{ \mathbb R^2 }[/math] and define [math]\displaystyle{ G_{a,b} }[/math] to be the subgraph of the 1-skeleton of [math]\displaystyle{ \text{Rips}(X)_b }[/math] containing all vertices whose degree is at least [math]\displaystyle{ a }[/math]. Subsequently building the maximal simplicial complex possible on this 1-skeleton, we obtain a complex [math]\displaystyle{ \text{D-Rips}(X)_{a,b} }[/math]. By doing this for all possible vertex degrees, and across all scale parameters in the Rips filtration, we extend the Rips construction to a bifiltration [math]\displaystyle{ \{ \text{D-Rips}(X)_{a,b}\}_{(a,b) \in \mathbb R^2} }[/math].[1]

Note that since the size of each complex will decrease as [math]\displaystyle{ a }[/math] increases, we should identify the indexing set [math]\displaystyle{ \mathbb R^2 }[/math] with [math]\displaystyle{ \mathbb R^{\text{op}}\times \mathbb R }[/math], where [math]\displaystyle{ \mathbb R^{\text{op}} }[/math] is the opposite poset category of [math]\displaystyle{ \mathbb R }[/math]. Therefore the degree-Rips bifiltration can be viewed as a functor [math]\displaystyle{ \text{D-Rips}(X): \mathbb R^{\operatorname{op}}\times \mathbb R \to \mathbf{Simp} }[/math].[7]

The idea behind the degree-Rips bifiltration is that vertices of higher degree will correspond to higher density regions of the underlying data set. However, since degree-Rips does not depend on an arbitrary choice of a parameter (such as a pre-selected density parameter, which is a priori difficult to determine), it is a convenient tool for analyzing data.[8]

Applications to data analysis

The degree-Rips bifiltration possesses several properties that make it a useful tool in data analysis. For example, each of its skeleta has polynomial size; the k-dimensional skeleton of [math]\displaystyle{ \text{D-Rips}(X) }[/math] has [math]\displaystyle{ O(|X|^{k+2}) }[/math] simplices, where [math]\displaystyle{ O }[/math] denotes an asymptotic upper bound.[7] Moreover, it has been shown that the degree-Rips bifiltration possesses reasonably strong stability properties with respect to perturbations of the underlying data set.[7] Further work has also been done examining the stable components and homotopy types of degree-Rips complexes.[9][10][11]

The software RIVET was created in order to visualize several multiparameter invariants (i.e., data structures that attempt to capture underlying geometric information of the data) of 2-parameter persistence modules, including the persistent homology modules of the degree-Rips bifiltration. These invariants include the Hilbert function, rank invariant, and fibered barcode.[1]

As a follow-up to the introduction of degree-Rips in their original 2015 paper, Lesnick and Wright showed in 2022 that a primary component of persistent homology computations (namely, computing minimal presentations and bigraded Betti numbers) can be achieved efficiently in a way that outperforms other persistent homology software.[12] Methods of improving algorithmic efficiency of multiparameter persistent homology have also been explored that suggest the possibility of substantial speed increases for data analysis tools such as RIVET.[13]

The degree-Rips bifiltration has been used for data analysis on random point clouds,[14] as well as for analyzing data clusters with respect to variations in density.[15][16][17] There has been some preliminary experimental analysis of the performance of degree-Rips with respect to outliers in particular, but this is an ongoing area of research as of February 2023.[18]

References

  1. ↑ 1.0 1.1 1.2 Lesnick, Michael; Wright, Matthew (2015-12-01). "Interactive Visualization of 2-D Persistence Modules". arXiv:1512.00180 [math.AT].
  2. ↑ Rabadan, Raul; Blumberg, Andrew J. (2019). Topological Data Analysis for Genomics and Evolution: Topology in Biology. Cambridge: Cambridge University Press. pp. 135–139. doi:10.1017/9781316671665. ISBN 978-1-107-15954-9. https://www.cambridge.org/core/books/topological-data-analysis-for-genomics-and-evolution/FCC8429FAD2B5D1525AEA47A8366D6EB. 
  3. ↑ Oudot, Steve Y. (2015). Persistence theory : from quiver representations to data analysis. Providence, Rhode Island. pp. 104. ISBN 978-1-4704-2545-6. OCLC 918149730. https://www.worldcat.org/oclc/918149730. 
  4. ↑ The structure and stability of persistence modules. Frédéric Chazal, Vin De Silva, Marc Glisse, Steve Y. Oudot. Switzerland. 2016. pp. 66. ISBN 978-3-319-42545-0. OCLC 960458101. https://www.worldcat.org/oclc/960458101. 
  5. ↑ Botnan, Magnus Bakke; Lesnick, Michael (2022-03-27). "An Introduction to Multiparameter Persistence". p. 8. arXiv:2203.14289 [math.AT].
  6. ↑ Carlsson, Gunnar; Zomorodian, Afra (2009-07-01). "The Theory of Multidimensional Persistence" (in en). Discrete & Computational Geometry 42 (1): 71–93. doi:10.1007/s00454-009-9176-0. ISSN 1432-0444. https://doi.org/10.1007/s00454-009-9176-0. 
  7. ↑ 7.0 7.1 7.2 Blumberg, Andrew J.; Lesnick, Michael (2022-10-17). "Stability of 2-Parameter Persistent Homology" (in en). Foundations of Computational Mathematics: 3, 8. doi:10.1007/s10208-022-09576-6. ISSN 1615-3375. https://link.springer.com/10.1007/s10208-022-09576-6. 
  8. ↑ Schenck, Hal (2022). Algebraic foundations for applied topology and data analysis. Cham. pp. 183. ISBN 978-3-031-06664-1. OCLC 1351750760. https://www.worldcat.org/oclc/1351750760. 
  9. ↑ Jardine, J. F. (September 2020). "Stable Components and Layers" (in en). Canadian Mathematical Bulletin 63 (3): 562–576. doi:10.4153/S000843951900064X. ISSN 0008-4395. https://www.cambridge.org/core/journals/canadian-mathematical-bulletin/article/abs/stable-components-and-layers/115EEF4BDE091E9C93D9473D0B4EEFA0. 
  10. ↑ Jardine, J. F. (2019). Data and homotopy types. 
  11. ↑ Jardine, J. F. (2020-10-26). "Persistent homotopy theory". arXiv:2002.10013 [math.AT].
  12. ↑ Lesnick, Michael; Wright, Matthew (2022). "Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology". SIAM Journal on Applied Algebra and Geometry 6 (2): 267–298. doi:10.1137/20M1388425. https://epubs.siam.org/doi/10.1137/20M1388425. 
  13. ↑ Alonso; Kerber; Pritam (2023). "Filtration-Domination in Bifiltered Graphs". 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX): 27–38. doi:10.1137/1.9781611977561.ch3. ISBN 978-1-61197-756-1. https://epubs.siam.org/doi/abs/10.1137/1.9781611977561.ch3. 
  14. ↑ Prabesh Paudel; Wang, Ken; Yuldasheva, Julie (2021) (in en). Characteristics of Degree-Rips Bifiltrations from Random Geometric Point Clouds. doi:10.13140/RG.2.2.34156.28809. http://rgdoi.net/10.13140/RG.2.2.34156.28809. 
  15. ↑ Rolle, Alexander; Scoccola, Luis (2021-07-16). "Stable and consistent density-based clustering". arXiv:2005.09048 [math.ST].
  16. ↑ Rolle, Alexander (2020). "Multi-parameter hierarchical clustering and beyond". Topological Data Analysis and Beyond Workshop at the 34th Conference on Neural Information Processing Systems. https://openreview.net/pdf?id=g0-tBxQTPRy. 
  17. ↑ Adamyk, Katharine L. M. (2021). Stability for layer points. 
  18. ↑ Rolle, Alexander (2022-03-16). "The Degree-Rips Complexes of an Annulus with Outliers". arXiv:2203.08767 [math.AT].



Retrieved from "https://handwiki.org/wiki/index.php?title=Degree-Rips_bifiltration&oldid=3380348"