Hilbert Sinkhorn Divergence for Optimal Transport

Qian Li, Zhichao Wang, Gang Li, Jun Pang, Guandong Xu

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).

Overview of the Hilbert Sinkhorn Divergence framework, mapping empirical measures into a Reproducing Kernel Hilbert Space (RKHS) for SVM classification.

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.

Comparison of classification error across different training set sizes, showing the superior performance of the $S_{H,\epsilon}$ kernel.

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

Abstract

Sinkhorn divergence has become a very popular metric to compare probability distributions in optimal transport. However, most works resort to Sinkhorn divergence in Euclidean space, which greatly blocks their applications in complex data with nonlinear structure. It is therefore of theoretical demand to empower Sinkhorn divergence with the capability of capturing nonlinear structures. We propose a theoretical and computational framework to bridge this gap. In this paper, we extend Sinkhorn divergence in Euclidean space to the reproducing kernel Hilbert space, which we term "Hilbert Sinkhorn divergence" (HSD).In particular, we can use kernel matrices to derive a closed form expression of HSD that is proved to be a tractable convex optimization problem. We also prove several attractive statistical properties of the proposed HSD, i.e., strong consistency, asymptotic behavior and sample complexity. Empirically, our method yields state-of-the-art performances on image classification and topological data analysis.
BibTeX
@inproceedings{li2021hilbert,
  author = {Qian Li and Zhichao Wang and Gang Li and Jun Pang and Guandong Xu},
  title = {{Hilbert Sinkhorn Divergence for Optimal Transport}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2021},
  doi = {10.1109/cvpr46437.2021.00383},
}
Figure