Multicover Bifiltration
The multicover bifiltration is a two-parameter sequence of nested topological spaces derived from the covering of a finite set in a metric space by growing metric balls. It is a multidimensional extension of the offset filtration that captures density information about the underlying data set by filtering the points of the offsets at each index according to how many balls cover each point.[1] The multicover bifiltration has been an object of study within multidimensional persistent homology and topological data analysis.[2][3][4][5][6][7]
Definition
Following the notation of Corbet et al. (2022), given a finite set [math]\displaystyle{ A\subset \mathbb R^d }[/math], the multicover bifiltration on [math]\displaystyle{ A }[/math] is a two-parameter filtration indexed by [math]\displaystyle{ \mathbb R \times \mathbb N^{\text{op}} }[/math] defined index-wise as [math]\displaystyle{ \operatorname{Cov}_{r,k} := \{b \in \mathbb R^d : ||b-a|| \leq r \text{ for at least } k \text{ points } a\in A\} }[/math], where [math]\displaystyle{ \mathbb N }[/math] denotes the non-negative integers.[8] Note that when [math]\displaystyle{ k=1 }[/math] is fixed we recover the Offset Filtration.
Properties
The multicover bifiltration admits a polynomially-sized simplicial model that is topologically equivalent, called the "rhomboid bifiltration."[8] The rhomboid bifiltration is an extension of the rhomboid tiling introduced by Edelsbrunner and Osang in 2021 for computing the persistent homology of the multicover bifiltration along one axis of the indexing set.[2] The rhomboid bifiltration on a set of [math]\displaystyle{ n }[/math] points in Euclidean space can be computed in time [math]\displaystyle{ O(n^5) }[/math].[8]
The multicover bifiltration is also topologically equivalent to a multicover nerve construction due to Sheehy called the subdivision-Čech bifiltration, which considers the barycentric subdivision on the nerve of the offsets.[9] In particular, the subdivision-Čech and multicover bifiltrations are weakly equivalent, and hence have isomorphic homology modules in all dimensions.[4] However, the subdivision-Čech bifiltration has an exponential number of simplices in the size of the data set, and hence is not amenable to efficient direct computations.[8]
References
- ↑ Botnan, Magnus Bakke; Lesnick, Michael (2022). "An Introduction to Multiparameter Persistence". p. 26. arXiv:2203.14289 [math.AT].
- ↑ 2.0 2.1 Edelsbrunner, Herbert; Osang, Georg (2021). "The Multi-Cover Persistence of Euclidean Balls" (in en). Discrete & Computational Geometry 65 (4): 1296–1313. doi:10.1007/s00454-021-00281-9. ISSN 0179-5376. PMID 34720303.
- ↑ Corbet, René; Kerber, Michael; Lesnick, Michael; Osang, Georg (2023-02-20). "Computing the Multicover Bifiltration" (in en). Discrete & Computational Geometry. doi:10.1007/s00454-022-00476-8. ISSN 0179-5376. https://link.springer.com/10.1007/s00454-022-00476-8.
- ↑ 4.0 4.1 Blumberg, Andrew J.; Lesnick, Michael (2022-10-17). "Stability of 2-Parameter Persistent Homology" (in en). Foundations of Computational Mathematics. doi:10.1007/s10208-022-09576-6. ISSN 1615-3375. https://link.springer.com/10.1007/s10208-022-09576-6.
- ↑ Botnan, Magnus B.; Hirsch, Christian (2022-12-22). "On the consistency and asymptotic normality of multiparameter persistent Betti numbers" (in en). Journal of Applied and Computational Topology. doi:10.1007/s41468-022-00110-9. ISSN 2367-1726. https://link.springer.com/10.1007/s41468-022-00110-9.
- ↑ Kerber, Michael (2022-07-29) (in en). Multi-Parameter Persistent Homology is Practical (Extended Abstract). https://openreview.net/forum?id=TDU6UycGYxR.
- ↑ Corbet, Rene (2020). Improvements to the Pipeline of Multiparameter Persistence. https://diglib.tugraz.at/download.php?id=5f901701ae9f0&location=aleph.
- ↑ 8.0 8.1 8.2 8.3 Corbet, René; Kerber, Michael; Lesnick, Michael; Osang, Georg (2023-02-20). "Computing the Multicover Bifiltration" (in en). Discrete & Computational Geometry. doi:10.1007/s00454-022-00476-8. ISSN 0179-5376. https://link.springer.com/10.1007/s00454-022-00476-8.
- ↑ D. R. Sheehy, “A multicover nerve for geometric inference,” in CCCG: Canadian conference in computational geometry, 2012.
 |
