Английская Википедия: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.

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>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>X</math>, commonly denoted <math>\text{Rips}(X)</math> or <math>\mathcal R (X)</math>. The Rips filtration can be expressed as a functor <math>\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>\mathbf{Top}</math> of topological spaces and continuous maps via the geometric realization functor.

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.

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>(a,b)</math> be an element of <math>\mathbb R^2</math> and define <math>G_{a,b}</math> to be the subgraph of the 1-skeleton of <math>\text{Rips}(X)_b</math> containing all vertices whose degree is at least <math>a</math>. Subsequently building the maximal simplicial complex possible on this 1-skeleton, we obtain a complex <math>\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>\{ \text{D-Rips}(X)_{a,b}\}_{(a,b) \in \mathbb R^2}</math>.

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

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.

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>\text{D-Rips}(X)</math> has <math>O(|X|^{k+2})</math> simplices, where <math>O</math> denotes an asymptotic upper bound. Moreover, it has been shown that the degree-Rips bifiltration possesses reasonably strong stability properties with respect to perturbations of the underlying data set. Further work has also been done examining the stable components and homotopy types of degree-Rips complexes.

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.

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. 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.

The degree-Rips bifiltration has been used for data analysis on random point clouds, as well as for analyzing data clusters with respect to variations in density. 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.