Hilbert Curve Projection Distance for Distribution Comparison
This provides a more efficient metric for distribution comparison in machine learning tasks like generative modeling, though it is incremental as it builds on existing Wasserstein distance methods.
The authors tackled the problem of comparing high-dimensional probability distributions by proposing the Hilbert curve projection (HCP) distance, which achieves a convergence rate of O(n^{-1/2max{d,p}}) and serves as an effective surrogate for the Wasserstein distance with lower complexity.
Distribution comparison plays a central role in many machine learning tasks like data classification and generative modeling. In this study, we propose a novel metric, called Hilbert curve projection (HCP) distance, to measure the distance between two probability distributions with low complexity. In particular, we first project two high-dimensional probability distributions using Hilbert curve to obtain a coupling between them, and then calculate the transport distance between these two distributions in the original space, according to the coupling. We show that HCP distance is a proper metric and is well-defined for probability measures with bounded supports. Furthermore, we demonstrate that the modified empirical HCP distance with the $L_p$ cost in the $d$-dimensional space converges to its population counterpart at a rate of no more than $O(n^{-1/2\max\{d,p\}})$. To suppress the curse-of-dimensionality, we also develop two variants of the HCP distance using (learnable) subspace projections. Experiments on both synthetic and real-world data show that our HCP distance works as an effective surrogate of the Wasserstein distance with low complexity and overcomes the drawbacks of the sliced Wasserstein distance.