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)- Barcode embeddings for metric graphs
- Curvature sets over persistence diagrams
- Optimal transport: discretization and algorithms
- Symmetric functions for fast image retrieval with persistent homology
- Tropical sufficient statistics for persistent homology
- Spatiotemporal persistent homology for dynamic metric spaces
- Topological learning for brain networks
- Metric spaces with expensive distances
- A feasibility study for a persistent homology-based \(k\)-nearest neighbor search algorithm in melanoma detection
- Computational complexity of the interleaving distance
- Computing bottleneck distance for 2-D interval decomposable modules
- scientific article; zbMATH DE number 7559246 (Why is no real title available?)
- Interleaving by parts: join decompositions of interleavings and join-assemblage of geodesics
- Computing the interleaving distance is NP-hard
- 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
- Supervised learning with indefinite topological Kernels
- Cancer Fingerprints by Topological Data Analysis
- Signal classification with a point process distance on the space of persistence diagrams
- On the Stability of Multigraded Betti Numbers and Hilbert Functions
- Bottleneck profiles and discrete Prokhorov metrics for persistence diagrams
- scientific article; zbMATH DE number 7370556 (Why is no real title available?)
- Topological data analysis on simple English Wikipedia articles
- Persistence Flamelets: Topological Invariants for Scale Spaces
- Geometric characterization of the persistence of 1D maps
- Functional summaries of persistence diagrams
- An Overview of the Topology ToolKit
- Understanding the topology and the geometry of the space of persistence diagrams via optimal partial transport
- Generalized persistence diagrams for persistence modules over posets
- Same but different: distance correlations between topological summaries
- Persistent topology of protein space
- scientific article; zbMATH DE number 7559221 (Why is no real title available?)
- Geometry Helps to Compare Persistence Diagrams
- Bayesian topological learning for classifying the structure of biological networks
- Compression for \(2\)-parameter persistent homology
- Approximating 1-Wasserstein distance between persistence diagrams by graph sparsification
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)
