Geometry helps to compare persistence diagrams
From MaRDI portal
Publication:4577947
Abstract: Exploiting geometric structure to improve the asymptotic complexity of discrete assignment problems is a well-studied subject. In contrast, the practical advantages of using geometry for such problems have not been explored. We implement geometric variants of the Hopcroft--Karp algorithm for bottleneck matching (based on previous work by Efrat el al.) and of the auction algorithm by Bertsekas for Wasserstein distance computation. Both implementations use k-d trees to replace a linear scan with a geometric proximity query. Our interest in this problem stems from the desire to compute distances between persistence diagrams, a problem that comes up frequently in topological data analysis. We show that our geometric matching algorithms lead to a substantial performance gain, both in running time and in memory consumption, over their purely combinatorial counterparts. Moreover, our implementation significantly outperforms the only other implementation available for comparing persistence diagrams.
Recommendations
Cites work
- scientific article; zbMATH DE number 1433426 (Why is no real title available?)
- Algorithms for the Assignment and Transportation Problems
- Algorithms for the transportation problem in geometric settings
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Approximation algorithms for bipartite matching with metric and geometric costs
- Assignment Problems
- Computational topology. An introduction
- Exploring uses of persistent homology for statistical analysis of landmark-based shape data
- Geometry Helps in Matching
- Geometry Helps to Compare Persistence Diagrams
- Geometry helps in bottleneck matching and related problems
- Improvements on geometric pattern matching problems
- Lipschitz functions have \(L_{p}\)-stable persistence
- Multidimensional binary search trees used for associative searching
- Parallel synchronous and asynchronous implementations of the auction algorithm
- Paths, Trees, and Flowers
- Space-time tradeoffs for approximate nearest neighbor searching
- Stability of persistence diagrams
- The auction algorithm for the transportation problem
- The auction algorithm: A distributed relaxation method for the assignment problem
- Topological persistence and simplification
Cited in
(36)- Topological data analysis on simple English Wikipedia articles
- Compression for \(2\)-parameter persistent homology
- A topological approach for capturing high-order interactions in graph data with applications to anomaly detection in time-varying cryptocurrency transaction graphs
- Vector summaries of persistence diagrams for permutation-based hypothesis testing
- Spatiotemporal persistent homology for dynamic metric spaces
- Curvature sets over persistence diagrams
- Computational complexity of the interleaving distance
- Computing bottleneck distance for 2-D interval decomposable modules
- Same but different: distance correlations between topological summaries
- Barcode embeddings for metric graphs
- Persistence Flamelets: Topological Invariants for Scale Spaces
- Approximating 1-Wasserstein distance between persistence diagrams by graph sparsification
- Optimal transport: discretization and algorithms
- Generalized persistence diagrams for persistence modules over posets
- On the Stability of Multigraded Betti Numbers and Hilbert Functions
- Bottleneck profiles and discrete Prokhorov metrics for persistence diagrams
- Geometric characterization of the persistence of 1D maps
- Interleaving by parts: join decompositions of interleavings and join-assemblage of geodesics
- Persistent topology of protein space
- scientific article; zbMATH DE number 7559246 (Why is no real title available?)
- Functional summaries of persistence diagrams
- Tropical sufficient statistics for persistent homology
- Signal classification with a point process distance on the space of persistence diagrams
- Metric spaces with expensive distances
- Cancer Fingerprints by Topological Data Analysis
- Topological learning for brain networks
- A feasibility study for a persistent homology-based \(k\)-nearest neighbor search algorithm in melanoma detection
- Supervised learning with indefinite topological Kernels
- Computing the interleaving distance is NP-hard
- Symmetric functions for fast image retrieval with persistent homology
- scientific article; zbMATH DE number 7370556 (Why is no real title available?)
- scientific article; zbMATH DE number 7559221 (Why is no real title available?)
- Bayesian topological learning for classifying the structure of biological networks
- An Overview of the Topology ToolKit
- Understanding the topology and the geometry of the space of persistence diagrams via optimal partial transport
- Geometry Helps to Compare Persistence Diagrams
This page was built for publication: Geometry helps to compare persistence diagrams
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4577947)
