Sierpiński--Knopp Wasserstein Distance for Persistence Diagrams and Applications to 2-Wasserstein Approximation
Sebastien Tchitchek, Julien Tierny
cs.CG · cs.LG
Quick verdict
SK-curve metric for diagrams: W₂ control, Hilbert embedding, 626× speedups vs exact solver; rigorous theory, honest limits; no fast-surrogate baseline shown.
Summary
The paper introduces d_SK, a distance between persistence diagrams obtained by pushing diagram points and their diagonal projections onto [0,1] via the first-hit selector of the Sierpiński–Knopp space-filling curve, then solving a one-dimensional W1 assignment whose monotone solution reduces to sorting two length-N lists, giving O(N log N) evaluation. The authors prove d_SK is a metric, that W2 ≤ √2·d_SK via the curve's 1/2-Hölder regularity, and that d_SK² admits a cumulative-L1 representation yielding an explicit isometric Hilbert embedding and a positive-definite Gaussian kernel; a planar surrogate W_Γ re-scores the induced assignment with the quadratic diagonal-aware cost and is tighter in median but not a metric (explicit counterexample provided). Experiments on 12 scientific collections (227 diagrams, 3.38M pairs) with TTK-computed W2 references show numerical stabilization at refinement level L=30, median Spearman correlations with W2 of 0.879 (d_SK,30) and 0.924 (W_Γ,30), verified bound orderings on all 3,004 pairs, and median per-collection speedups of 626× (about 2100× aggregate) over TTK's auction solver. Average-linkage partitions from d_SK and W_Γ match W2 partitions exactly on 8/12 collections; Gaussian spectral clustering reaches mean ARI 0.800 versus 0.750 for W2 average linkage. Main limitations: one-sided control (d_SK can overestimate W2), collection-wide normalization restricting online use, and timing compared only against the exact W2 solver.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- d_SK is a true metric on normalized persistence diagrams, computable in O(N log N) after selector evaluation by sorting two length-N scalar lists.
- The universal bound W2(X,Y) ≤ √2·d_SK(X,Y) holds, and the induced planar surrogate satisfies W2 ≤ W_Γ ≤ √2·d_SK, with W_Γ tighter in median but provably non-metric.
- d_SK² admits a cumulative-L1 representation yielding an explicit isometric embedding into L2([0,1]×R) and a positive-definite, characteristic Gaussian kernel.
- On 12 scientific collections (227 diagrams), d_SK,30 attains median Spearman 0.879 with W2, median per-collection speedup 626× over TTK's auction solver, and bound ordering verified on all 3,004 pairs.
- d_SK-based Gaussian spectral clustering achieves mean ARI 0.800 versus 0.750 for W2 average linkage, demonstrating practical value of the Hilbertian/kernel structure.
Strengths
Complete, verifiable theory chain
Metricity (Thms A.6-A.7), universal control W2 ≤ √2·d_SK via the 1/2-Hölder regularity of the SK curve (Thm A.12, constant C_SK=2 derived from Shchepin 2020), conditional negative definiteness (Prop A.15), explicit isometric Hilbert embedding into L2([0,1]×R) (Prop A.21), and positive-definite/characteristic Gaussian kernel (Cor A.16, Thm A.24, Cor A.25) are all proved with explicit arguments, not asserted.
Unusually honest treatment of the weaker surrogate
W_Γ's non-metricity is established with an explicit singleton counterexample whose level-8 selector ordering is certified to imply the exact ordering (Fig. 5), and its lack of Hilbertian/kernel guarantees is stated rather than hidden.
Exhaustive numerical bound verification
Principled refinement-level ablation
Reproducibility posture
Weaknesses
Single speedup baseline
One-sided accuracy control with moderate empirical fidelity
Collection-dependent normalization
Modest statistical reporting
Metric guarantees hold only for the exact selector
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a method paper in computational topology/TDA. It proposes **d_SK**, a distance between persistence diagrams obtained by pushing each normalized diagram and its diagonal projections onto [0,1] through the first-hit selector ι of the Sierpiński–Knopp space-filling curve, then solving a one-dimensional W1 assignment between the augmented encodings. Because 1D W1 has a monotone closed-form solution, evaluation reduces to sorting two length-N lists — O(N log N), plus O(NL) for the finite-level selector. Central claims: (i) d_SK is a metric (Thms A.6–A.7); (ii) universal one-sided control W2 ≤ √2·d_SK (Thm A.12, via the curve's 1/2-Hölder regularity, C_SK = 2 derived from Shchepin 2020); (iii) d_SK² has a cumulative-L1 representation yielding an explicit isometric Hilbert embedding into L2([0,1]×R) (Prop A.21) and a positive-definite, characteristic Gaussian kernel (Cor A.16, Thm A.24, Cor A.25); (iv) the planar surrogate W_Γ satisfies W2 ≤ W_Γ ≤ √2·d_SK but is provably non-metric via an explicit, level-8-certified counterexample (Fig. 5).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the Sierpiński–Knopp (SK) Wasserstein distance in simple terms?
It is a fast distance between persistence diagrams: each diagram point and its diagonal projection is encoded as a single number in [0,1] using a space-filling curve's first-hit position, and the two diagrams are compared by a one-dimensional optimal assignment that reduces to sorting two lists, running in O(N log N) time.
How much faster is d_SK than computing the exact 2-Wasserstein distance?
On the paper's benchmark of 12 scientific collections (227 diagrams, 3.38 million persistence pairs), the median per-collection speedup over TTK's auction-based W2 solver was 626× at refinement level L=30, with roughly 2100× aggregate speedup over the full benchmark.
Is d_SK a real metric, and can it be used with machine-learning kernels?
Yes. The paper proves the exact d_SK is a metric, gives an explicit isometric embedding into a Hilbert space, and shows the Gaussian kernel exp(−d_SK²/2σ²) is positive definite (in fact characteristic). The tighter surrogate W_Γ, however, is not a metric — the triangle inequality can fail.
What are the main limitations of the SK-Wasserstein distance?
Three stand out: the accuracy guarantee is one-sided (d_SK can substantially overestimate W2, with no dataset-independent reverse bound); all diagrams must be normalized using statistics of the whole collection, which complicates online/streaming use; and the reported timings are compared only against the exact W2 solver, not against other fast approximation methods.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Provided text is a sampled excerpt with five gaps: parts of Sec. 2.2-2.3, part of Sec. 3.5, the contents of Table 3 (its caption and narrative medians are visible), a stretch of references, and appendix material between Remarks A.26 and A.28 (the statement of Theorem A.27 is known only from its citation in Sec. 5.2.1). Judgments touching those regions are hedged.
- Per-collection faithfulness and speedup values beyond the reported medians (626× d_SK, 586× W_Γ, Isabel Spearman 0.603) were not visible in the extraction; they are cited from the surrounding narrative and figure captions only.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.