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[1] (later subsumed by a conference paper in 2012[2]) as a discrete model of the multicover bifiltration, a continuous construction whose underlying framework dates back to the 1970s.
[3] In particular, Sheehy applied the construction to both the Vietoris-Rips and Čech filtrations, two common objects in the field of topological data analysis.
[4][5][6] Whereas single parameter filtrations are not robust with respect to outliers in the data,[7] the subdivision-Rips and -Cech bifiltrations satisfy several desirable stability properties.
Then a nested sequence of simplices
is called a flag or chain of
comprises an abstract simplicial complex, known as the barycentric subdivision of
The barycentric subdivision is naturally identified with a geometric subdivision of
, created by starring the geometric realization of
Considering the sequence of nested subcomplexes given by varying the parameter
Since the complexes in the subdivision filtration shrink as
increases, we can regard it as a functor
from the opposite posetal category
be a partially ordered set.
, regarded as a functor from the posetal category of
, by applying the subdivision filtration object-wise on
, we obtain a two-parameter filtration
, called the subdivision bifiltration.
to be the Rips or Čech filtration, we obtain bifiltrations
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.[11] The ideas from Cavanna's proof were later generalized by Blumberg and Lesnick in a 2022 paper on 2-parameter persistent homology.
[8] 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.
[12] 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.
[13] 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.