Geometry helps to compare persistence diagrams
From MaRDI portal
Publication:4577947
DOI10.1145/3064175zbMATH Open1414.68129arXiv1606.03357OpenAlexW2294510945MaRDI QIDQ4577947FDOQ4577947
Authors: Michael Kerber, Dmitriy Morozov, Arnur Nigmetov 
Publication date: 6 August 2018
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1606.03357
Recommendations
Other homology theories in algebraic topology (55N35) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Computational topology. An introduction
- Stability of persistence diagrams
- Lipschitz functions have \(L_{p}\)-stable persistence
- The auction algorithm: A distributed relaxation method for the assignment problem
- Assignment Problems
- Topological persistence and simplification
- Exploring uses of persistent homology for statistical analysis of landmark-based shape data
- Paths, Trees, and Flowers
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Algorithms for the Assignment and Transportation Problems
- Geometry Helps in Matching
- Multidimensional binary search trees used for associative searching
- Title not available (Why is that?)
- Algorithms for the transportation problem in geometric settings
- Geometry helps in bottleneck matching and related problems
- Improvements on geometric pattern matching problems
- The auction algorithm for the transportation problem
- Approximation algorithms for bipartite matching with metric and geometric costs
- Space-time tradeoffs for approximate nearest neighbor searching
- Parallel synchronous and asynchronous implementations of the auction algorithm
- Geometry Helps to Compare Persistence Diagrams
Cited In (35)
- Curvature sets over persistence diagrams
- Barcode embeddings for metric graphs
- 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
- Metric spaces with expensive distances
- Topological learning for brain networks
- 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
- Title not available (Why is that?)
- 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
- Cancer Fingerprints by Topological Data Analysis
- Supervised learning with indefinite topological Kernels
- 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
- Title not available (Why is that?)
- Topological data analysis on simple English Wikipedia articles
- Persistence Flamelets: Topological Invariants for Scale Spaces
- An Overview of the Topology ToolKit
- Functional summaries of persistence diagrams
- Understanding the topology and the geometry of the space of persistence diagrams via optimal partial transport
- Same but different: distance correlations between topological summaries
- Generalized persistence diagrams for persistence modules over posets
- Persistent topology of protein space
- Title not available (Why is that?)
- Bayesian topological learning for classifying the structure of biological networks
- Geometry Helps to Compare Persistence Diagrams
- Filtration simplification for persistent homology via edge contraction
- Compression for \(2\)-parameter persistent homology
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)
