Abstract
Optimal Transport (OT) is a powerful tool for comparing probability distributions, but its application is often limited by the constraints of Euclidean space. This paper introduces the Hilbert Sinkhorn Divergence (HSD), a novel framework that extends entropy-regularized OT to Reproducing Kernel Hilbert Spaces (RKHS). By leveraging kernel embeddings, HSD captures complex nonlinear data structures while maintaining computational efficiency. We demonstrate that HSD is theoretically robust and achieves state-of-the-art performance in tasks ranging from image classification to topological data analysis.
Introduction
Optimal Transport (OT) provides a robust geometric framework for comparing probability distributions by calculating the Wasserstein distance—the minimum cost to transform one distribution into another. While computationally demanding, the introduction of entropy-regularized Sinkhorn divergence has made OT practical for large-scale machine learning. However, standard Sinkhorn methods are typically confined to Euclidean spaces, failing to capture the complex nonlinear structures inherent in data such as 3D shapes, graphs, and topological persistence diagrams. This paper introduces the Hilbert Sinkhorn Divergence (HSD), bridging the gap between the efficiency of Sinkhorn iterations and the expressive power of Reproducing Kernel Hilbert Spaces (RKHS).
Methodology: The Kernel Trick for Optimal Transport
The core innovation of HSD lies in its ability to operate directly within an RKHS. The process begins with a Hilbert Embedding, where probability distributions are mapped into a high-dimensional feature space as mean functions. This allows the representation of complex distributions in a way that respects their underlying geometry.
To make this tractable, the authors leverage the "kernel trick." They prove that the HSD between two distributions can be reformulated as a finite optimization problem solvable using only the kernel matrix. The "cost" of moving mass is redefined using the kernel-induced distance: $c_H(x, y) = k(x, x) + k(y, y) - 2k(x, y)$. This formulation ensures that the resulting optimization problem remains strictly convex, allowing for efficient solution via standard Sinkhorn iterations (matrix-vector products).
The authors further establish the theoretical foundations of HSD, proving its strong consistency and analyzing its sample complexity, ensuring that estimates converge reliably to the true value as more data is observed.
Applications in Topological Data Analysis
A significant challenge in Topological Data Analysis (TDA) is comparing persistence diagrams, which do not naturally reside in a vector space. HSD provides a theoretically grounded method for this task. By defining a positive definite kernel ($S_{H,\epsilon}$-kernel) based on HSD, non-vectorial data like persistence diagrams can be directly integrated into standard machine learning pipelines, such as Support Vector Machines (SVMs). This approach effectively solves the "bottleneck" of comparing topological features.
Experimental Results
The effectiveness of HSD was evaluated across image classification, 3D shape analysis, and texture recognition. On the USPS handwritten digit dataset, the HSD-based kernel consistently achieved lower error rates than both standard RBF kernels and traditional Sinkhorn divergence across varying training set sizes.
In 3D shape classification tasks using the SHREC datasets, the proposed method (referred to as PSK) outperformed specialized topological kernels. For instance, on the "ANT" class, PSK achieved an accuracy of 92.7%. Similarly, in texture recognition on the Outex dataset, HSD reached 75.3% accuracy on the CLBP-S feature set, a notable improvement over the 70.5% achieved by the Persistence Scale Space kernel.
Conclusion and Future Work
Hilbert Sinkhorn Divergence offers a powerful, computationally efficient framework for comparing distributions in non-Euclidean spaces. By combining the geometric insights of kernels with the algorithmic efficiency of Sinkhorn regularization, HSD enables state-of-the-art performance in complex domains like TDA and shape analysis. Future research will focus on improving scalability for massive datasets through low-rank approximations like the Nyström method and extending the framework to other manifold structures common in computer vision.
Summary updated