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
- 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 bottleneck matching and related problems
- Geometry Helps in Matching
- Geometry Helps to Compare Persistence Diagrams
- scientific article; zbMATH DE number 1433426 (Why is no real title available?)
- 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
(41)- Signal classification with a point process distance on the space of persistence diagrams
- Barcode embeddings for metric graphs
- Generalized persistence diagrams for persistence modules over posets
- Persistent topology of protein space
- Compression for \(2\)-parameter persistent homology
- Functional summaries of persistence diagrams
- Computing the interleaving distance is NP-hard
- Spatiotemporal persistent homology for dynamic metric spaces
- Optimal transport: discretization and algorithms
- Understanding the topology and the geometry of the space of persistence diagrams via optimal partial transport
- A feasibility study for a persistent homology-based \(k\)-nearest neighbor search algorithm in melanoma detection
- Topological learning for brain networks
- Symmetric functions for fast image retrieval with persistent homology
- Topological data analysis on simple English Wikipedia articles
- \textit{giotto-tda}: a topological data analysis toolkit for machine learning and data exploration
- Metric spaces with expensive distances
- Supervised learning with indefinite topological Kernels
- scientific article; zbMATH DE number 7559221 (Why is no real title available?)
- Exact computation of the matching distance on 2-parameter persistence modules
- Computational complexity of the interleaving distance
- Computing bottleneck distance for 2-D interval decomposable modules
- Same but different: distance correlations between topological summaries
- Geometry Helps to Compare Persistence Diagrams
- Tropical sufficient statistics for persistent homology
- An Overview of the Topology ToolKit
- Persistence Flamelets: Topological Invariants for Scale Spaces
- Cancer Fingerprints by Topological Data Analysis
- Bayesian topological learning for classifying the structure of biological networks
- On the Stability of Multigraded Betti Numbers and Hilbert Functions
- Bottleneck profiles and discrete Prokhorov metrics for persistence diagrams
- Approximating 1-Wasserstein distance between persistence diagrams by graph sparsification
- Curvature sets over persistence diagrams
- Interleaving by parts: join decompositions of interleavings and join-assemblage of geodesics
- Vector summaries of persistence diagrams for permutation-based hypothesis testing
- A topological approach for capturing high-order interactions in graph data with applications to anomaly detection in time-varying cryptocurrency transaction graphs
- Geometric characterization of the persistence of 1D maps
- Geometric matching and bottleneck problems
- Approximation algorithms for 1-Wasserstein distance between persistence diagrams
- A statistical framework for analyzing shape in a time series of random geometric objects
- Algebraic Wasserstein distances and stable homological invariants of data
- Sketching 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)
