Hilbert Curve Projection Distance for Distribution Comparison

2022/05/30 by Li, Tao, Meng, Cheng, Xu, Hongteng +1
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2205.15059

Abstract

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/2max\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.

Related

• Comparing Distributions and Shapes using the Kernel Distance
• Intrinsic Sliced Wasserstein Distances for Comparing Collections of Probability Distributions on Manifolds and Graphs
• Schoenberg-Rao distances: Entropy-based and geometry-aware statistical Hilbert distances
• Distance Measure Machines
• Kernel Trace Distance: Quantum Statistical Metric between Measures through RKHS Density Operators