More Like this

1. Computing Betti Tables and Minimal Presentations of Zero-Dimensional Persistent Homology

   https://doi.org/10.4230/LIPIcs.SoCG.2025.69  

   Morozov, Dmitriy; Scoccola, Luis (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Aichholzer, Oswin; Wang, Haitao (Ed.)

   The Betti tables of a multigraded module encode the grades at which there is an algebraic change in the module. Multigraded modules show up in many areas of pure and applied mathematics, and in particular in topological data analysis, where they are known as persistence modules, and where their Betti tables describe the places at which the homology of filtered simplicial complexes changes. Although Betti tables of singly and bigraded modules are already being used in applications of topological data analysis, their computation in the bigraded case (which relies on an algorithm that is cubic in the size of the filtered simplicial complex) is a bottleneck when working with large datasets. We show that, in the special case of 0-dimensional homology (relevant for clustering and graph classification) Betti tables of bigraded modules can be computed in log-linear time. We also consider the problem of computing minimal presentations, and show that minimal presentations of 0-dimensional persistent homology can be computed in quadratic time, regardless of the grading poset. 

   more » « less
2. Persistent Topological Laplacians—A Survey

   https://doi.org/10.3390/math13020208  

   Wei, Xiaoqi; Wei, Guo-Wei (January 2025, Mathematics)

   Persistent topological Laplacians constitute a new class of tools in topological data analysis (TDA). They are motivated by the necessity to address challenges encountered in persistent homology when handling complex data. These Laplacians combine multiscale analysis with topological techniques to characterize the topological and geometrical features of functions and data. Their kernels fully retrieve the topological invariants of corresponding persistent homology, while their non-harmonic spectra provide supplementary information. Persistent topological Laplacians have demonstrated superior performance over persistent homology in the analysis of large-scale protein engineering datasets. In this survey, we offer a pedagogical review of persistent topological Laplacians formulated in various mathematical settings, including simplicial complexes, path complexes, flag complexes, digraphs, hypergraphs, hyperdigraphs, cellular sheaves, and N-chain complexes. 

   more » « less
3. Polytopal Complex Construction and Use in Persistent Homology

   https://doi.org/10.1109/ICDMW58026.2022.00087  

   Singh, Rohit P.; Wilsey, Philip A. (November 2022, ICDM Workshop on High Dimensional Data Mining)

   Topological Data Analysis (TDA) is a data mining technique to characterize the topological features of data. Persistent Homology (PH) is an important tool of TDA that has been applied to a wide range of applications. However its time and space complexities motivates a need for new methods to compute the PH of high-dimensional data. An important, and memory intensive, element in the computation of PH is the complex constructed from the input data. In general, PH tools use and focus on optimizing simplicial complexes; less frequently cubical complexes are also studied. This paper develops a method to construct polytopal complexes (or complexes constructed of any mix of convex polytopes) in any dimension Rn . In general, polytopal complexes are significantly smaller than simplicial or cubical complexes. This paper includes an experimental assessment of the impact that polytopal complexes have on memory complexity and output results of a PH computation. 

   more » « less
4. Computing Bottleneck Distance for 2-D Interval Decomposable Modules

   Dey, Tamal K; Xin, Cheng (June 2018, j34th International Symposium on Computational Geometry (SoCG 2018))

   Computation of the interleaving distance between persistence modules is a central task in topological data analysis. For $$1$$-D persistence modules, thanks to the isometry theorem, this can be done by computing the bottleneck distance with known efficient algorithms. The question is open for most $$n$$-D persistence modules, $n>1$$, because of the well recognized complications of the indecomposables. Here, we consider a reasonably complicated class called {\em $$2$$-D interval decomposable} modules whose indecomposables may have a description of non-constant complexity. We present a polynomial time algorithm to compute the bottleneck distance for these modules from indecomposables, which bounds the interleaving distance from above, and give another algorithm to compute a new distance called {\em dimension distance} that bounds it from below. 

   more » « less
5. Homotopy, homology, and persistent homology using closure spaces

   https://doi.org/10.1007/s41468-024-00183-8  

   Bubenik, Peter; Milićević, Nikola (July 2024, Journal of Applied and Computational Topology)

   Abstract. We develop persistent homology in the setting of filtrations of (Cˇech) closure spaces. Examples of filtrations of closure spaces include metric spaces, weighted graphs, weighted directed graphs, and filtrations of topological spaces. We use various products and intervals for closure spaces to obtain six homotopy theories, six cubical singular homology theories, and three simplicial singular homology theories. Applied to filtrations of closure spaces, these homology theories produce persistence modules. We extend the definition of Gromov-Hausdorff distance from metric spaces to filtrations of closure spaces and use it to prove that any persistence module obtained from a homotopy-invariant functor on closure spaces is stable. 

   more » « less