  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.
