Sierpiński--Knopp Wasserstein Distance for Persistence Diagrams and Applications to 2-Wasserstein Approximation
2609.01528

Authors

Sebastien Tchitchek,Julien Tierny

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_Γ$, 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_Γ$ 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.

Resources

Ray graphicRay graphicRay graphicRay graphic

Stay in the loop

Every AI paper that matters, free in your inbox daily.

Details

  • takara.ai
  • Custom AI and machine learning from the Frontier Research Team.
  • © 2026 takara.ai Ltd
  • Content is sourced from third-party publications.
Ray graphicRay graphicRay graphic