Improved approximate Rips filtrations with shifted integer lattices and cubical complexes (Q2239807)

The paper is devoted to the development of methods for calculating topological and homotopy invariants of large sets of points located in a finite-dimensional Euclidean space. Much has been done in classical works [\textit{G. Carlsson}, Bull. Am. Math. Soc., New Ser. 46, No. 2, 255--308 (2009; Zbl 1172.62002)], [\textit{H. Edelsbrunner} and \textit{J. L. Harer}, Computational topology. An introduction. Providence, RI: American Mathematical Society (AMS) (2010; Zbl 1193.55001)], [\textit{H. Edelsbrunner} et al., Discrete Comput. Geom. 28, No. 4, 511--533 (2002; Zbl 1011.68152)]. But this topic always brings new problems. Let \(P\) be a set of points in Euclidean space \({\mathbb R}^d\) and let \(\alpha \geq 0\) be a real number. A Rips complex on \(P\) in \textit{scale} \(\alpha\) is a simplicial complex whose simplices \(\sigma=(p_0, \dots, p_n)\) have diameters at most \(\alpha\), where \(p_i\in P\) for all \(0\leq i\leq n\). In the paper, \({\mathcal R}_{\alpha}\) denotes the Rips complex at scale \(2\alpha\) with the Euclidean metric, and \({\mathcal R}^{\infty}_{\alpha}\) with the metric of the \(L_{\infty}\)-norm. When \(\alpha\) increases from \(0\) to \(\infty\), the Rips complexes form a filtration. The homologies \(H({\mathcal R}_{\alpha})\) make up the persistence module. The \([0, \infty)\) axis is divided into open intervals, within each of which the homology vector spaces (and the number of holes) of the complex \({\mathcal R}_{\alpha}\) do not change. This division into intervals is called the barcode of the point cloud under study. From the text: ``The computational drawback of Rips complexes is their sheer size: the \(k\)-skeleton of a Rips complex (that is, where only subsets of size at most \(k+1\) are considered) for \(n\) points consists of \(\Theta(n^{k+1})\) simplices because every \((k+1)\)-subset joins the complex for a sufficiently large scale parameter. This size bound makes barcode computations for large point clouds infeasible even for low-dimensional homological features. This difficulty motivates the question of what we can say about the barcode of the Rips filtration without explicitly constructing all of its simplices. We address this question using approximation techniques. The space of barcodes forms a metric space: two barcodes are close if similiar homological features occur on roughly the same range of scales. More precisely, the bottleneck distance is used as a distance metric between barcodes. The first approximation scheme by \textit{D.R. Sheehy} [Discrete Comput. Geom. 49, No. 4, 778--796 (2013; Zbl 1280.55005)] constructs a \((1+\varepsilon)\)-approximation of the \(k\)-skeleton of the Rips filtration using only \(n( \frac{1}{\varepsilon} )^{O(\lambda k)}\) simplices for arbitrary finite metric spaces, where \(\lambda\) is the doubling dimension of the metric. Further approximation techniques for Rips complexes [\textit{T. K. Dey} et al., in: Proceedings of the 30th annual symposium on computational geometry, SoCG '14, Kyoto, Japan, June 8--11, 2014. New York, NY: Association for Computing Machinery (ACM). 345--354 (2014; Zbl 1395.68299)] and the closely related \textit{Čech complexes} [\textit{M. B. Botnan} and \textit{G. Spreemann}, Appl. Algebra Eng. Commun. Comput. 26, No. 1--2, 73--101 (2015; Zbl 1320.55002); \textit{N. J. Cavanna} et al., LIPIcs -- Leibniz Int. Proc. Inform. 34, 23--25 (2015; Zbl 1378.68163); \textit{M. Kerber} and \textit{R. Sharathkumar}, Lect. Notes Comput. Sci. 8283, 666--676 (2013; Zbl 1406.68119)] have been derived subsequently, all with comparable size bounds. More recently, we constructed an approximation scheme [\textit{A. Choudhary} et al., Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2675--2688 (2019; Zbl 1432.68474)] for the Čech filtrations of \(n\) points in \({\mathbb R}^d\) that had size \(n(\frac{1}{\varepsilon})^{O(d)} 2^{O(d \log{d}+dk)}\) for the \(k\)-skeleton, improving the size bound from previous work.'' In [\textit{A. Choudhary} et al., Discrete Comput. Geom. 61, No. 1, 42--80 (2019; Zbl 1441.62937)], an approximation scheme for Rips filtrations in Euclidean space was constructed that yields a worse approximation factor of only \(O(d)\), but uses only \(n 2^{O(d \log{k}+d)}\) simplices. A lower bound result on the size of approximations was also shown there: for any \(\varepsilon < 1/ \log^{1+c} n\) with some constant \(c \in (0, 1)\), any \(\varepsilon\)-approximate filtration has size \(n^{\Omega (\log \log n)}\). From the text: ``There has also been work on using cubical complexes to compute persistent homology, such as in [\textit{H. Wagner} et al., Topological methods in data analysis and visualization II. Theory, algorithms, and applications. Based on the 4th workshop on topology-based methods in data analysis and visualization, TopoInVis 2011. Berlin: Springer. 91--106 (2012; Zbl 1246.68245)]. Cubical complexes are typically smaller than their simplicial counterparts, simply because they avoid triangulations. However, to our knowledge, there has been no attempt to utilize them in computing approximations of filtrations. Also, while there are efficient methods to compute persistence for simplicial complexes connected with simplicial maps ([\textit{T.K. Dey} et al., loc. cit.], [\textit{M. Kerber} and \textit{H. Schreiber}, LIPIcs - Leibniz Int. Proc. Inform. 77, Article 57, 16 p. (2017; Zbl 1436.55009)]), we are not aware of such counterparts for cubical complexes. \textit{Our contributions}. For the Rips filtration of \(n\) points in \({\mathbb R}^d\) with distances taken in the \(L_{\infty}\)-norm, we present a \(2\)-approximation whose \(k\)-skeleton has size at most \[ n6^{d-1}(2k+4)(k + 3)! \left\{\begin{matrix} d\\ k+2 \end{matrix}\right\} = n2^{O(d \log k+d)} \] where \(\left\{\begin{matrix} a\\ b \end{matrix}\right\}\) denotes Stirling numbers of the second kind. This translates to a \(2d^{0.25}\)-approximation of the Rips filtration in the Euclidean metric and hence improves the asymptotic approximation quality of our previous approach [\textit{A. Choudhary} et al., loc. cit.] with the same size bound. Our scheme gives the best size guarantee over all previous approaches. On a high level, our approach follows a straightforward approximation scheme: given a scaled and appropriately shifted integer grid on \({\mathbb R}^d\), we identify those grid points that are close to the input points and build an approximation complex using these grid points. The challenge lies in how to connect these grid points to a simplicial complex such that close-by grid points are connected, while avoiding too many connections to keep the size small. Our approach first selects a set of active faces in the cubical complex defined over the grid, and defines the approximation complex using the barycentric subdivision of this cubical complex. We also describe an output-sensitive algorithm to compute our approximation. By randomizing the aforementioned shifts of the grids, we obtain a worst-case running time of \(n2^{O(d)} \log\Delta +2^{O(d)}M\) in expectation, where \(\Delta\) is the spread of the point set (that is, the ratio of the diameter to the closest distance of two points) and \(M\) is the size of the approximation.''