A Homotopy Algorithm for Optimal Transport
This work addresses a bottleneck in applying optimal transport to large-scale machine learning and other fields, offering a potentially faster algorithm, though it appears incremental as it builds on known homotopy and transformation techniques.
The paper tackles the computational challenge of solving optimal transport problems for large datasets in high-dimensional spaces by proposing a homotopy algorithm that transforms the problem into an easier form and iteratively traces back to the original, aiming for a complexity of O(n^2 log(n)) to outperform existing methods.
The optimal transport problem has many applications in machine learning, physics, biology, economics, etc. Although its goal is very clear and mathematically well-defined, finding its optimal solution can be challenging for large datasets in high-dimensional space. Here, we propose a homotopy algorithm that first transforms the problem into an easy form, by changing the target distribution. It then transforms the problem back to the original form through a series of iterations, tracing a path of solutions until it finds the optimal solution for the original problem. We define the homotopy path as a subspace rotation based on the orthogonal Procrustes problem, and then we discretize the homotopy path using eigenvalue decomposition of the rotation matrix. Our goal is to provide an algorithm with complexity bound $\mathcal{O}(n^2 \log(n))$, faster than the existing methods in the literature.