The Observable Wasserstein Distance

Summary

This paper introduces the observable Wasserstein distance, a new framework for computing lower bounds on the Wasserstein distance between probability measures on general Polish metric spaces, designed to address the computational intractability of exact optimal transport in large-scale, non-Euclidean settings.

The core idea is analogous to the sliced Wasserstein distance for Euclidean spaces: instead of projecting measures onto 1-dimensional linear subspaces (which requires linear structure), the authors project probability measures onto the real line via 1-Lipschitz observables—functions f: X to R satisfying f(x) - f(y) d(x,y). For a measure mu, the pushforward f mu is computed, and the Wasserstein distance between these projected measures is taken. The observable Wasserstein p-distance is defined as:

[

theta p(mu, nu):= f in (X) w p(f mu, f nu),

]

where (X) is the set of all 1-Lipschitz functions on X. Since observables are 1-Lipschitz, it immediately follows that theta p(mu, nu) w p(mu, nu).

To make the framework computationally tractable, the authors introduce a nested chain of subspaces of observables. The basic observables are distance-to-a-point functions f a(x) = d(x,a), and higher-order observables are formed via weighted wedge products (pointwise minima) of these functions. Specifically, for 0 n < infinity, define:

[

n(X) = f a alpha: alpha in I n+1, a in X n+1,

]

where f a alpha = alpha 0 f a 0 alpha n f a n, and I = [0,1]. The full space is infinity(X) = n=1 infinity n(X). This yields a chain:

[

X 0(X) 1(X) infinity(X) (X).

]

A central theoretical contribution is the injectivity result linking the metric covering dimension of a measure's support to the order in the hierarchy needed for unique recovery. The Lipschitz transform T mu: (X) to P(R) maps an observable to its pushforward measure. The authors prove:

• Theorem 2.9 (Injectivity for infinity): If T mu infinity = T nu infinity, then mu = nu. This holds for any Polish metric space and any probability measures. The proof shows that from the projections via distance functions, one can recover the measure of all open balls, and via wedge products, the measure of arbitrary finite unions of open balls, which suffices to determine the measure on all open sets.

• Theorem 3.9 (Stratified Injectivity): For 0 n < infinity, if mu, nu have supports with metric covering dimension n, then T mu n = T nu n implies mu = nu. This serves as a metric-space analogue of the Cramér–Wold Device for Euclidean distributions. The metric covering dimension xi X(S) is defined via refinements of open covers by open balls with bounded intersection multiplicity.

• Corollary 3.10: For finitely supported measures (empirical measures), T mu 0 = T nu 0 implies mu = nu, meaning distance-to-a-point functions alone suffice for discrete measures.

• Corollary 3.11: If the ambient space X has metric covering dimension n, then all probability measures on X are uniquely determined by their projections via n(X).

Restricting the supremum to n(X) defines the pseudo-metrics:

[

theta p,n(mu, nu):= f in n(X) w p(f mu, f nu).

]

These satisfy the monotonicity:

[

theta p,m(mu, nu) theta p,n(mu, nu) theta p(mu, nu) w p(mu, nu), for m n.

]

The injectivity results imply that theta p,n is a genuine metric when restricted to measures whose supports have dimension n. There is a tunable trade-off between sharpness as a lower bound and computational efficiency.

Key properties established include:

• Proposition 2.4: The Lipschitz transform T mu is continuous; if X is compact, it is 1-Lipschitz with respect to the sup norm on observables and the Wasserstein distance on pushforwards.

• Proposition 4.5: For p=1, theta 1(mu, nu) = w 1(mu, nu), via Kantorovich–Rubinstein duality.

• Corollary 4.6: For compact X, the metrics theta p and w p are topologically equivalent for all p in [1, infinity).

The paper also develops a discrete model for computation. Given a finite delta-cover A X, one can approximate any measure by a measure supported on A with Wasserstein error < delta. The discrete distance d A p,n is defined by restricting observables to those anchored at points in A. Proposition 5.9 shows that this discrete distance approximates the continuous one within 2 delta.

Numerical experiments validate the framework:

1. Gaussian classification: The observable Wasserstein distance performs comparably to sliced Wasserstein distance in classifying Gaussian distributions, with a performance edge in high dimensions due to Gaussian concentration effects.

2. Distributions on graphs: On random geometric graphs with shortest-path distance, observable Wasserstein distances significantly outperform classical Wasserstein distance in classification accuracy and are much faster to compute.

3. Dependence on observables: On spheres, experiments show that increasing the number of observables or the number of functions in wedge products decreases the relative error (lower bound gap) but increases compute time, with diminishing returns.

4. ModelNet10 classification: On 3D point cloud data, observable Wasserstein distances (using distance-to-a-point functions and wedge products) outperform sliced Wasserstein and Chamfer distances in nearest-neighbor classification, especially under noise.

5. Deep learning autoencoder: The observable Wasserstein distance is integrated into a point cloud autoencoder loss function. Results show that pure observable Wasserstein loss yields better latent-space classification accuracy than pure Chamfer loss, with more uniform point density in reconstructions, though Chamfer produces sharper renderings.

The paper concludes by outlining future directions: investigating bi-Lipschitz equivalence between theta p and w p for p not equal to 1, extending sampling convergence and robustness results from sliced Wasserstein to this setting, exploring other classes of observables, and developing a more complete numerical framework including learning observables in deep learning pipelines.

Based on the paper, here are the specific improvements I can make to AI systems and what the improved systems can do:

• Improvement: Implement the observable Wasserstein distance (OWD) as a loss function in autoencoders, GANs, and diffusion models, replacing or augmenting sliced Wasserstein distance (SWD).

• What the improved system can do: Handle non-Euclidean data (graphs, manifolds, point clouds on spheres) where SWD is undefined. It provides a tunable lower bound on the true Wasserstein distance, allowing the model to balance computational cost with fidelity. In the paper's MNIST autoencoder experiment, OWD achieved 90.92% latent-space classification accuracy vs. 87.31% for Chamfer distance, and showed superior denoising performance.

• Improvement: Use the nested chain of observables Λ0(X) ⊆ Λ1(X) ⊆... ⊆ Λn(X) to create a multi-scale distance for point cloud comparison. For a point cloud with support dimension ≤ n, the distance θp,n is a true metric (not just a pseudo-metric).

• What the improved system can do: Automatically select the minimal number of observables needed to uniquely distinguish point clouds. For finite point sets (dimension 0), only distance-to-anchor functions are needed (Λ0), reducing computation from O(N2) to O(N·k) where k is the number of anchors. The system can then refine with higher-order observables only when needed.

• Improvement: Use OWD instead of classical Wasserstein distance for nearest-neighbor classification on noisy data. The paper shows OWD significantly outperforms Wasserstein distance on graph-based distributions with added noise (e.g., at noise level β=3.0, OWD with 15% anchors achieved 85% classification vs. 60% for Wasserstein).

• What the improved system can do: Maintain high classification accuracy even when up to 100% of points are corrupted by Gaussian noise (as demonstrated on ModelNet10). The system is more robust because it compares distributions via scalar projections, which are less sensitive to individual outlier points than direct optimal transport.

• Improvement: Implement OWD using distance-to-node functions on weighted graphs with shortest-path metrics. The paper shows OWD computation time scales linearly with graph size, while classical Wasserstein distance scales super-linearly.

• What the improved system can do: Process graphs with 700+ nodes in under 0.5 seconds per distance computation, versus several seconds for Wasserstein. This makes it feasible for real-time graph clustering, anomaly detection, or graph matching in social networks, molecular structures, or transportation networks.

• Improvement: Expose the parameter n (number of anchor points in observables) as a user-controlled knob. The system can start with n=1 (fastest, least sharp) and increase n until the distance estimate stabilizes within a user-defined tolerance.

• What the improved system can do: Automatically find the minimum computational cost needed to achieve a desired approximation error. For example, on 2D Gaussian classification, using 10 anchors gives 90% accuracy, while 50 anchors gives 98%—the system can adaptively choose the number based on the task's accuracy requirements.

• Improvement: Integrate OWD into the loss function of autoencoders or VAEs that operate on graph-structured or manifold-valued data. The paper demonstrates this on MNIST point clouds, but the framework extends to any Polish metric space.

• What the improved system can do: Learn latent representations of protein structures, 3D shapes, or functional surfaces where Euclidean distances are inappropriate. The system can use the L2 variant of OWD (as in the paper's Remark 4.4) for better differentiability during backpropagation, while still benefiting from the theoretical guarantees of the L∞ version.

• Improvement: Use the paper's Proposition 5.3 and Corollary 5.4 to provide theoretical guarantees that empirical OWD estimates converge to the true distance as the δ-cover becomes finer. The system can report a confidence interval for the distance based on the grid resolution.

• What the improved system can do: Provide reliable distance estimates with known error bounds, even when the data is not fully observed. This is critical for scientific applications where false positives/negatives are costly (e.g., medical imaging, materials science).

• Improvement: Use the stratified injectivity result (Theorem 3.9) to detect anomalies. If a new data point has support dimension > n, but the system was calibrated for dimension ≤ n, the OWD distance will be a strict lower bound, signaling that the data lies outside the expected manifold.

• What the improved system can do: Flag out-of-distribution samples in high-dimensional data (e.g., detecting adversarial attacks on neural networks, identifying novel molecular structures) by checking whether the observed OWD value violates the expected bound for the known support dimension.

The improved AI system can:

• Process non-Euclidean data (graphs, manifolds, point clouds) with a distance that is both computationally tractable and theoretically guaranteed to be a metric on the relevant data class.

• Achieve classification accuracy comparable to or better than sliced Wasserstein distance in high dimensions (e.g., 100-dim Gaussian data), while being more robust to noise.

• Scale to large datasets with linear-time distance computations, enabling real-time applications.

• Provide tunable trade-offs between accuracy and speed, with theoretical bounds on the approximation error.

• Integrate seamlessly into deep learning pipelines as a differentiable loss function, improving reconstruction quality and latent-space separability.

We introduce the observable Wasserstein distance, a framework for deriving lower bounds on the Wasserstein distance between probability measures on Polish metric spaces, designed to bypass the computational intractability of exact optimal transport in large-scale, non-Euclidean datasets. Analogous to the sliced Wasserstein distance in R d, our approach projects measures onto the real line via 1-Lipschitz observables and computes the Wasserstein distances between the resulting pushforward distributions. We define a hierarchy of pseudo-metrics by restricting observables to a nested chain of subspaces. A central theoretical contribution is an injectivity result linking the metric covering dimension of the support of a measure to the specific order in the hierarchy that guarantees unique recovery. This serves as a metric-space analogue to the Cram' e r-Wold Device for Euclidean distributions. We demonstrate that this hierarchy offers a tunable trade-off between sharpness as a lower bound on the Wasserstein distance and computational efficiency. We also present a discrete computational model for finite grids and numerical experiments validating the efficacy and utility of these approximations.