Subdivision bifiltration

Short description: Technique in topological data analysis

In topological data analysis, a subdivision bifiltration is a collection of filtered simplicial complexes, typically built upon a set of data points in a metric space, that captures shape and density information about the underlying data set. The subdivision bifiltration relies on a natural filtration of the barycentric subdivision of a simplicial complex by flags of minimum dimension, which encodes density information about the metric space upon which the complex is built. The subdivision bifiltration was first introduced by Donald Sheehy in 2011 as part of his doctoral thesis (later subsumed by a conference paper in 2012) as a discrete model of the multicover bifiltration, a continuous construction whose underlying framework dates back to the 1970s. In particular, Sheehy applied the construction to both the Vietoris-Rips and Čech filtrations, two common objects in the field of topological data analysis. Whereas single parameter filtrations are not robust with respect to outliers in the data, the subdivision-Rips and -Cech bifiltrations satisfy several desirable stability properties.

Definition

Let [math]\displaystyle{ T }[/math] be a simplicial complex. Then a nested sequence of simplices [math]\displaystyle{ \sigma_1 \subset \sigma_2 \subset \cdots \subset \sigma_k }[/math] of [math]\displaystyle{ T }[/math] is called a flag or chain of [math]\displaystyle{ T }[/math]. The set of all flags of [math]\displaystyle{ T }[/math] comprises an abstract simplicial complex, known as the barycentric subdivision of [math]\displaystyle{ T }[/math], denoted by [math]\displaystyle{ \operatorname{Bary}(T) }[/math]. The barycentric subdivision is naturally identified with a geometric subdivision of [math]\displaystyle{ T }[/math], created by starring the geometric realization of [math]\displaystyle{ T }[/math] at the barycenter of each simplex.

There is a natural filtration on [math]\displaystyle{ \operatorname{Bary}(T) }[/math] by considering for each natural number [math]\displaystyle{ k }[/math] the maximal subcomplex of [math]\displaystyle{ \operatorname{Bary}(T) }[/math] spanned by vertices of [math]\displaystyle{ \operatorname{Bary}(T) }[/math] corresponding to simplices of [math]\displaystyle{ T }[/math] of dimension at least [math]\displaystyle{ k-1 }[/math], which is denoted [math]\displaystyle{ \tilde \mathcal S (T)_k }[/math]. In particular, by this convention, then [math]\displaystyle{ \tilde \mathcal S (T)_1 = \operatorname{Bary}(T) }[/math]. Considering the sequence of nested subcomplexes given by varying the parameter [math]\displaystyle{ k }[/math], we obtain a filtration on [math]\displaystyle{ \operatorname{Bary}(T) }[/math] known as the subdivision filtration. Since the complexes in the subdivision filtration grow as [math]\displaystyle{ k }[/math] increases, we can regard it as a functor [math]\displaystyle{ \tilde \mathcal S (-): \mathbb N^\operatorname{op} \to \mathbf{Simp} }[/math] from the opposite posetal category [math]\displaystyle{ \mathbb N^\operatorname{op} }[/math] to the category [math]\displaystyle{ \mathbf{Simp} }[/math] of simplicial complexes and simplicial maps.

Let [math]\displaystyle{ P }[/math] be a partially ordered set. Given a simplicial filtration [math]\displaystyle{ F: P \to \mathbf{Simp} }[/math], regarded as a functor from the posetal category of [math]\displaystyle{ P }[/math] to the category [math]\displaystyle{ \mathbf{Simp} }[/math], by applying the subdivision filtration object-wise on [math]\displaystyle{ F }[/math], we obtain a two-parameter filtration [math]\displaystyle{ \mathcal S (F): \mathbb N^\operatorname{op}\times P \to \mathbf{Simp} }[/math], called the subdivision bifiltration.

In particular, when we take [math]\displaystyle{ F }[/math] to be the Rips or Čech filtration, we obtain bifiltrations [math]\displaystyle{ \mathcal S \operatorname{Rips}(-) }[/math] and [math]\displaystyle{ \mathcal S \operatorname{\check{C}ech}(-) }[/math], respectively.

Properties

The subdivision-Čech bifiltration is weakly equivalent to the multicover bifiltration, implying that they have isomorphic persistent homology. A combinatorial proof of this statement was given in Sheehy's original conference paper, but a more algebraic version was presented in 2017 by Cavanna et al. The ideas from Cavanna's proof were later generalized by Blumberg and Lesnick in a 2022 paper on 2-parameter persistent homology.

By the size of a bifiltration, we mean the number of simplices in the largest complex. The subdivision-Čech bifiltration has exponential size as a function of the number of vertices. This implies that its homology cannot be directly computed in polynomial time. However, for points in Euclidean space, the homology of subdivision-Čech can be computed in polynomial time, up to weak equivalence, via a construction known as the rhomboid bifiltration. As a precursor to the rhomboid bifiltration, Edelsbrunner and Osang presented in 2021 a polyhedral cell complex called the rhomboid tiling, which they used to compute horizontal or vertices slices of the multicover bifiltration up to weak equivalence. This was extended a year later by Corbet et al. to the rhomboid bifiltration, which is weakly equivalent to the multicover bifiltration, but has polynomial size.