The distilled Vietoris-Rips filtration for persistent homology and a new memory-efficient algorithm.
Musashi Ayrton Koyama, Vanessa Robins, Katharine Turner · 2024
Read The distilled Vietoris-Rips filtration for persistent homology and a new memory-efficient algorithm. by Musashi Ayrton Koyama, Vanessa Robins, Katharine Turner (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-07805.txt.
Introduction
Musashi Ayrton Koyama, Vanessa Robins, and Katharine Turner shrink a data analysis method in a 2024 math paper. Persistent homology reads the shape of point clouds at many scales, but the standard construction eats time and memory, which blocks big data use. Their version, the distilled filtration, trims the construction down.
A discrete flow field on the standard complex guides the trimming. The authors prove the trimmed version keeps the same shape signature as the original. The algorithm that builds and reduces it runs well in parallel and uses little memory. It works for point clouds in any space where pairwise distances are known. The paper targets practitioners who need shape analysis on large datasets.
Catalog record
| CREATOR | Musashi Ayrton Koyama, Vanessa Robins, Katharine Turner |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-07805
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The distilled Vietoris-Rips filtration for persistent homology and a new memory-efficient algorithm. Musashi Ayrton Koyama, Vanessa Robins, Katharine Turner Abstract The long computational time and large memory requirements for computing Vietoris-Rips persistent homology from point clouds remains a significant deterrent to its application to ‘big data’. This paper aims to reduce the memory footprint of these computations. It presents a new construction, the distilled Vietoris-Rips filtration , and proves that its persistent homology is isomorphic to that of standard Vietoris-Rips. The distilled complex is constructed using a discrete Morse vector field defined on the reduced Vietoris-Rips complex. The algorithm for building and reducing the distilled filtration boundary matrix is highly parallelisable and memory efficient. It can be implemented for point clouds in any metric space given the pairwise distance matrix. 1 Introduction Computing persistent homology on large data sets has been, and still remains one of the most significant bottlenecks to the adoption of persistent homology by the wider scientific community. While there are software packages which can compute persistent homology for large point clouds, usually these come with some sort of restriction on the data-set. For example, persistent homology of the Cech filtration is efficiently computed using alpha-shapes for point clouds in low-dimensional Euclidean spaces. The Vietoris-Rips filtration is a natural choice of data structure for computing persistent homology when working with arbitrary finite metric spaces. This is because constructing the Vietoris-Rips filtration only requires the pairwise distance matrix. However, whilst applying Vietoris-Rips persistent homology to finite metric spaces is conceptually simple, applying it in practice to finite metric spaces of even a modest size presents difficulties. Ripser [ 1 ] , along with its GPU accelerated counterpart [ 2 ] are the current state of the art software for computing Vietoris-Rips persistent homology on finite metric spaces. With that said, computing \text{PH}_{1}(X) for |X|=10^{5} and above remains a computation limited to the realm of supercomputers and is currently not even remotely feasible on a civilian machine. There are currently two main roadblocks to computing Vietoris-Rips persistent homology on larger point clouds. One is a prohibitively long runtime, the other is machine memory. Of these two issues, memory remains the limiting factor. The superlinear memory usage of current software means that even with improved hardware, the increase in what we are able to analyse will not increase substantially. One way to deal with the runtime is to use parallelization. In the software \mathsf{Dory} , parallelization was used to compute Vietoris-Rips persistent persistent homology for a point cloud with 10^{6} points and assisted by setting a small stopping radius for the filtration [ 3 ] . The large memory requirements of currently available software stems from the fact that a large number of simplices are required for computation. Algorithms to reduce the number of simplices required for computation have been explored in [ 4 ] , though the author states that these techniques would be more suited for computing \text{PH}_{q}(X) where q\geq 2 and that the results are mixed for computing \text{PH}_{1}(X) . In [ 5 ] , the reduced Vietoris-Rips complex was introduced as a way to reduce the number of 2 -simplices required to compute \text{PH}_{1}(X) from O(n^{3}) to O(n^{2}) provided X has bounded doubling dimension. In this paper we present an algorithm that is highly parallelizable and memory efficient, though it may require a significant number of cores to obtain a runtime that is acceptable to the user. 2 Background material Here we briefly present the necessary background material and establish notation. 2.1 Homology We give basic definitions for simplicial homology following Munkres’ text Elements of Algebraic Topology [ 6 ] . First we define the notion of a simplicial complex. Definition 2.1 (Simplicial complex) . A simplicial complex with vertex set V=\{v_{1},...,v_{n}\} is a set K\subset 2^{V} which satisfies the following properties. • \emptyset\in K • \{v_{i}\}\in K for all i\in\{1,...,n\} . • If \sigma\in K , then all subsets of \sigma are also in K . • If \tau\in K and \sigma\in K then \tau\cap\sigma\in K . Next we define the notion of a simplex. Definition 2.2 ( q -simplex) . Consider a simplicial complex K with vertex set V=\{v_{1},...,v_{n}\} . Then let \sigma be a subset of V with q+1 elements. Then we refer to \sigma as a q -simplex. We will make reference to the dimension of a simplex in Definition 2.30 . Definition 2.3 (Dimension of a simplex) . Consider a simplicial complex K . Let \sigma be a q -simplex, then we say that \sigma has dimension q and denote this by \dim(\sigma)=q It will be convenient later on to have a special term for when one simplex is a subset of another simplex. Definition 2.4 (Faces and cofaces) . Consider a simplicial complex K with simplices \sigma,\tau with \sigma\subset\tau . Then we say that \sigma is a face of \tau and \tau is a coface of \sigma . From here on in we write \sigma=\{w_{0},...,w_{q}\} as \langle w_{0}...w_{q}\rangle , following standard notation for oriented simplices. Since we are working with \mathbb{Z}_{2} -coefficients we can effectively ignore the orientation of the simplices. This means that we can refer to a given simplex using any permutation of its vertices. For example, the 2 -simplex \langle xyz\rangle can equally be referred to as \langle xzy\rangle=\langle zxy\rangle=\langle zyx\rangle=\langle yzx\rangle=\langle yxz\rangle . The addition of simplices is formalised in the next definition. Definition 2.5 (Simplicial q -chain) . A simplicial q -chain is a finite formal sum of q simplices, \sum_{i=1}^{N}c_{i}\sigma_{i} (1) In this paper, the coefficients c_{i} are taken from \mathbb{Z}_{2} . We now define three important vector spaces. Definition 2.6 (Chain group) . C_{q}(K) is the free abelian group with coefficients in \mathbb{Z}_{2} with generating set consisting of all q -simplices. It is customary to set C_{-1}(K)=\mathbb{Z}_{2} . Remark 2.7 . It is worth noting that C_{q}(K) is actually a vector space since \mathbb{Z}_{2} is a field and that from this point on, any time the word “group” is mentioned it could be replaced with “vector space”. We continue to use the word group to adhere to the “traditional” presentation of homology, though the reader unfamiliar with groups can replace them with vector spaces for the purposes of this paper. Definition 2.8 (Boundary map) . Let K be a simplicial complex. Consider the map \partial_{q+1}^{K}:C_{q+1}(K)\rightarrow C_{q}(K) defined as follows. Let \sigma=\langle v_{0},...,v_{q}\rangle . Then we define \partial_{q+1}^{K}(\sigma) as follows: \partial_{q+1}^{K}(\sigma)=\sum_{i=0}^{q}\langle v_{0}...\hat{v_{i}}...v_{q}\rangle. (2) We extend this linearly to a map on C_{q+1}(K) . Here \hat{v_{i}} means that v_{i} is to be omitted from \langle v_{0}...v_{i}...v_{q}\rangle . When it is clear what K is, we may write \partial_{q+1}^{K} as \partial_{q+1} . When q is also clear, we may simply write \partial_{q+1} as \partial . The map \partial_{0}^{K}:C_{0}(K)\rightarrow C_{-1}(K)=\mathbb{Z}_{2} acts in the following fashion: \partial_{0}^{K}(\langle v_{0}\rangle)=1. (3) It follows that \partial_{0}^{K} maps a simplicial 0 -chain to the parity of the number of 0 -simplices in the chain. Definition 2.9 ( q -cycles) . Consider a simplicial complex K . We denote \mathrm{ker}(\partial_{q}^{K})=Z_{q}(K) . We call a q -chain c\in Z_{q}(K) a q -cycle. Z_{q}(K) will be referred to as the group of q -cycles. Definition 2.10 ( q -boundaries) . Consider a simplicial complex K