Sierpi\'nski--Knopp Wasserstein Distance for Persistence Diagrams and Applications to 2-Wasserstein Approximation

arXiv:2609.01528v1 Announce Type: cross Abstract: This paper introduces the Sierpi\'nski-Knopp (SK) Wasserstein distance, a fast metric between persistence diagrams. The SK-Wasserstein distance, denoted $d_{\mathrm{SK}}$, maps diagram points and their diagonal projections to the unit interval via the Sierpi\'nski-Knopp space-filling curve on the upper diagonal triangle. The encoded point sets are then efficiently matched via one-dimensional optimal assignment, in $O(N\log N)$ steps, yielding an explicit diagonal-aware point assignment between the two input persistence diagrams. We show that the SK-Wasserstein distance controls the classical $2$-Wasserstein distance between diagrams, admits an explicit isometric embedding into a Hilbert space, and induces a positive-definite Gaussian kernel, making the resulting geometry directly compatible with Euclidean and kernel-based learning methods. A tighter surrogate dissimilarity, noted $W_\Gamma$, is also introduced based on the point assignments along the curve. Experiments on 12 scientific collections comprising 227 diagrams show median per-collection speedup of $d_{\mathrm{SK}}$ over state-of-the-art approximations of $W_2$ is $626\times$, while the aggregate speedup over the full benchmark is $2100\times$. Average-linkage partitions obtained from $d_{\mathrm{SK}}$ and $W_\Gamma$ each exactly match the corresponding $W_2$ partition on 8 of the 12 collections. Hilbert $k$-means and Gaussian spectral clustering, both based on $d_{\mathrm{SK}}$, achieve mean adjusted Rand indices (ARI) of $0.756$ and $0.800$, respectively, with respect to the benchmark reference partitions, compared to $0.750$ obtained by average linkage on $W_2$. The Gaussian $d_{\mathrm{SK}}$ kernel supports other kernel-based analysis tasks, as illustrated by its use for contiguous segmentation of ordered diagram collections in our experiments.

Abstract:This paper introduces the Sierpiński-Knopp (SK) Wasserstein distance, a fast metric between persistence diagrams. The SK-Wasserstein distance, denoted $d_{\mathrm{SK}}$, maps diagram points and their diagonal projections to the unit interval via the Sierpiński-Knopp space-filling curve on the upper diagonal triangle. The encoded point sets are then efficiently matched via one-dimensional optimal assignment, in $O(N\log N)$ steps, yielding an explicit diagonal-aware point assignment between the two input persistence diagrams. We show that the SK-Wasserstein distance controls the classical $2$-Wasserstein distance between diagrams, admits an explicit isometric embedding into a Hilbert space, and induces a positive-definite Gaussian kernel, making the resulting geometry directly compatible with Euclidean and kernel-based learning methods. A tighter surrogate dissimilarity, noted $W_\Gamma$, is also introduced based on the point assignments along the curve. Experiments on 12 scientific collections comprising 227 diagrams show median per-collection speedup of $d_{\mathrm{SK}}$ over state-of-the-art approximations of $W_2$ is $626\times$, while the aggregate speedup over the full benchmark is $2100\times$. Average-linkage partitions obtained from $d_{\mathrm{SK}}$ and $W_\Gamma$ each exactly match the corresponding $W_2$ partition on 8 of the 12 collections. Hilbert $k$-means and Gaussian spectral clustering, both based on $d_{\mathrm{SK}}$, achieve mean adjusted Rand indices (ARI) of $0.756$ and $0.800$, respectively, with respect to the benchmark reference partitions, compared to $0.750$ obtained by average linkage on $W_2$. The Gaussian $d_{\mathrm{SK}}$ kernel supports other kernel-based analysis tasks, as illustrated by its use for contiguous segmentation of ordered diagram collections in our experiments.

49 pages, 11 figures, 6 tables. Code and reproducibility package: this https URL

Computational Geometry (cs.CG); Machine Learning (cs.LG)

arXiv:2609.01528 [cs.CG]

(or arXiv:2609.01528v1 [cs.CG] for this version)

https://doi.org/10.48550/arXiv.2609.01528 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

Sierpi\'nski--Knopp Wasserstein Distance for Persistence Diagrams and Applications to 2-Wasserstein Approximation

Related coverage