# Approximation algorithms for 1-Wasserstein distance between persistence diagrams

arXiv: https://arxiv.org/abs/2104.07710 · HTML: https://mlsanity.com/paper/2104.07710/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2021.

## Built on by (most cited first, 5 of 5)

- [Efficient approximation of Earth Mover's Distance Based on Nearest Neighbor Search](https://mlsanity.com/paper/2401.07378/) (2024)
- [Vector Summaries of Persistence Diagrams for Permutation-based Hypothesis Testing](https://mlsanity.com/paper/2306.06257/) (2023)
- [A Class of Topological Pseudodistances for Fast Comparison of Persistence Diagrams](https://mlsanity.com/paper/2402.14489/) (2024)
- [Data-driven techniques for translational neuroscience and personalized neuro-health](https://mlsanity.com/paper/2608.13749/) (2026)
- [Sierpi'nski--Knopp Wasserstein Distance for Persistence Diagrams and Applications to 2-Wasserstein Approximation](https://mlsanity.com/paper/2609.01528/) (2026)

## Abstract (arXiv)

Recent years have witnessed a tremendous growth using topological summaries, especially the persistence diagrams (encoding the so-called persistent homology) for analyzing complex shapes. Intuitively, persistent homology maps a potentially complex input object (be it a graph, an image, or a point set and so on) to a unified type of feature summary, called the persistence diagrams. One can then carry out downstream data analysis tasks using such persistence diagram representations. A key problem is to compute the distance between two persistence diagrams efficiently. In particular, a persistence diagram is essentially a multiset of points in the plane, and one popular distance is the so-called 1-Wasserstein distance between persistence diagrams. In this paper, we present two algorithms to approximate the 1-Wasserstein distance for persistence diagrams in near-linear time. These algorithms primarily follow the same ideas as two existing algorithms to approximate optimal transport between two finite point-sets in Euclidean spaces via randomly shifted quadtrees. We show how these algorithms can be effectively adapted for the case of persistence diagrams. Our algorithms are much more efficient than previous exact and approximate algorithms, both in theory and in practice, and we demonstrate its efficiency via extensive experiments. They are conceptually simple and easy to implement, and the code is publicly available in github.