Subdivision bifiltration

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. ^[8]

Definition

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

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

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

In particular, when we take ${\displaystyle F}$ to be the Rips or Čech filtration, we obtain bifiltrations ${\displaystyle {\mathcal {S}}\operatorname {Rips} (-)}$ and ${\displaystyle {\mathcal {S}}\operatorname {{\check {C}}ech} (-)}$, 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. ^[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. ^[12]

References

1. Sheehy, D. R. (2011). Mesh generation and geometric persistent homology (Doctoral dissertation, Carnegie Mellon University).
2. Sheehy, Donald R. 2012. “A Multicover Nerve for Geometric Inference.” in CCCG: Canadian conference in computational geometry.
3. Fejes Tóth, G. (March 1976). "Multiple packing and covering of the plane with circles". Acta Mathematica Academiae Scientiarum Hungaricae. 27 (1–2): 135–140. doi:10.1007/BF01896768. ISSN   0001-5954. S2CID   189778121.
4. Chazal, Frédéric; Oudot, Steve Yann (2008). "Towards persistence-based reconstruction in euclidean spaces". Proceedings of the twenty-fourth annual symposium on Computational geometry. pp. 232–241. arXiv: 0712.2638 . doi:10.1145/1377676.1377719. ISBN   9781605580715. S2CID   1020710.
5. Ghrist, Robert (2007). "Barcodes: The persistent topology of data". Bulletin of the American Mathematical Society. 45: 61–76. doi: 10.1090/s0273-0979-07-01191-3 .
6. Chazal, Frédéric; De Silva, Vin; Oudot, Steve (2014). "Persistence stability for geometric complexes". Geometriae Dedicata. 173: 193–214. arXiv: 1207.3885 . doi:10.1007/s10711-013-9937-z. S2CID   254508455.
7. Chazal, Frédéric; Cohen-Steiner, David; Mérigot, Quentin (December 2011). "Geometric Inference for Probability Measures". Foundations of Computational Mathematics. 11 (6): 733–751. doi:10.1007/s10208-011-9098-0. ISSN   1615-3375. S2CID   15371638.
8. Blumberg, Andrew J.; Lesnick, Michael (2022-10-17). "Stability of 2-Parameter Persistent Homology". Foundations of Computational Mathematics. arXiv: 2010.09628 . doi:10.1007/s10208-022-09576-6. ISSN   1615-3375. S2CID   224705357.
9. Rourke, C. P. (1982). Introduction to piecewise-linear topology. B. J. Sanderson. Berlin: Springer-Verlag. ISBN   0-387-11102-6. OCLC   7948164.
10. Lesnick, Michael (11 March 2023). "Lecture notes for AMAT 840: Multiparameter Persistence" (PDF). Retrieved 27 March 2023.
11. Cavanna, Nicholas J.; Gardner, Kirk P.; Sheehy, Donald R. (2017). "When and Why the Topological Coverage Criterion Works". Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2679–2690. doi:10.1137/1.9781611974782.177. ISBN   978-1-61197-478-2.
12. Corbet, René; Kerber, Michael; Lesnick, Michael; Osang, Georg (2023-02-20). "Computing the Multicover Bifiltration". Discrete & Computational Geometry. 70 (2): 376–405. arXiv: 2103.07823 . doi:10.1007/s00454-022-00476-8. ISSN   0179-5376. PMC   10423148 . PMID   37581017.
13. Edelsbrunner, Herbert; Osang, Georg (2021). "The Multi-Cover Persistence of Euclidean Balls". Discrete & Computational Geometry. 65 (4): 1296–1313. doi:10.1007/s00454-021-00281-9. ISSN   0179-5376. PMC   8550220 . PMID   34720303.