Coarse Hilbert embeddings of persistence diagrams
Let $\mathcal{D}$ be the set of all finite multisets of points $(b,d)$ in $\mathbb{R}^2$ with $b < d$, the empty multiset included, with no common bound on cardinality or coordinates. For $1 \le p \le 2$ let $W_p$ be the $p$-Wasserstein distance on $\mathcal{D}$ with the $\ell^\infty$ ground metric, unmatched points being matched to the diagonal $\Delta = \{(t,t) : t \in \mathbb{R}\}$: $$W_p(D,E)^p = \min_{\substack{D' \subseteq D,\ E' \subseteq E\\ \phi : D' \to E' \text{ bijective}}} \Bigl(\sum_{x \in D'} \|x - \phi(x)\|_\infty^p + \sum_{x \in D \setminus D'} \operatorname{dist}_\infty(x, \Delta)^p + \sum_{y \in E \setminus E'} \operatorname{dist}_\infty(y, \Delta)^p\Bigr),$$ where subsets and bijections respect multiplicity.
Pritchard and Weighill proved that, for each $p \ge 1$, $(\mathcal{D}, W_p)$ coarsely embeds into a Hilbert space if and only if the $p$-Wasserstein space of probability measures on $\mathbb{R}^2$ does. As they record, diagrams with at most $N$ points coarsely embed into a Hilbert space for every $p$ (Mitra and Virk), while $(\mathcal{D}, W_p)$ does not for $2 < p \le \infty$ (Bubenik and Wagner; Wagner).
Problem. For which $p \in [1,2]$ are there a Hilbert space $H$, a map $F : \mathcal{D} \to H$ and finite-valued nondecreasing functions $\rho_-, \rho_+ : [0,\infty) \to [0,\infty)$ with $\lim_{t \to \infty} \rho_-(t) = \infty$ such that $$\rho_-(W_p(D,E)) \le \|F(D) - F(E)\|_H \le \rho_+(W_p(D,E))$$ for all $D, E \in \mathcal{D}$? The map and the control functions may depend on $p$ but must work for all diagrams at once.
Source: Pritchard and Weighill (2025), for 1 ≤ p ≤ 2. Stated by AIM — Open Applied Problems with the ℓ∞ ground metric.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- AT, FA
- Keywords
- AIM Open Applied Problems, coarse embeddings, persistence diagrams, Wasserstein distance
References
@article{pritchard2025coarse,
author = {Pritchard, Neil and Weighill, Thomas},
title = {Coarse embeddability of {W}asserstein space and the space of persistence diagrams},
journal = {Discrete Comput. Geom.},
volume = {74},
number = {2},
year = {2025},
pages = {358--373},
doi = {10.1007/s00454-024-00674-6},
eprint = {2307.12884},
archivePrefix = {arXiv},
}
@misc{aim-persistence-diagram-coarse-embedding,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Coarse Hilbert embeddings of persistence diagrams}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/520-persistence-diagram-coarse-embedding.md},
note = {Entry 520 at commit 24edaad, 2026-10-15},
}
Resolution claims
We prove that the space of all finite persistence diagrams, with no common cardinality or coordinate bound, does not coarsely embed into Hilbert space for any Wasserstein exponent \(1\le p\le2\). The metric uses the usual \(\ell^\infty\) ground distance and matching to the diagonal. For each finite family of rational signed measures on a square grid, a sufficiently large common background …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Needs verification → Solution claimed | — | Recorded here: AIM @ 24edaad, paper/main.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00816, "Coarse Hilbert embeddings of persistence diagrams", clopen.solutions.