Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a Riemannian geometric framework for low-rank optimal transport (OT) that overcomes the limitations of first-order mirror-descent methods by incorporating the curvature of the optimization landscape. By modeling balanced and unbalanced rank-$r$ positive factored couplings as smooth embedded submanifolds and utilizing the Fisher-Rao product metric, the authors derive efficient algorithms for both balanced and unbalanced OT. Experimental results show that their approach significantly outperforms existing low-rank OT solvers in terms of convergence speed and solution quality, with linear per-iteration complexity relative to dataset size.
Riemannian geometry can revolutionize low-rank optimal transport, achieving faster convergence and better performance without the need for regularization.
Low-rank optimal transport (OT) mitigates the quadratic scaling of classical solvers, yet existing approaches rely heavily on first-order mirror-descent updates that require careful hyperparameter tuning and ignore the optimization landscape's curvature. To address these limitations, we propose a unified Riemannian geometric framework for low-rank OT, modeling balanced and unbalanced rank-$r$ positive factored couplings as novel smooth embedded submanifolds of the positive orthant. By equipping these manifolds with the Fisher-Rao product metric, we derive tractable formulations for Riemannian projectors, retractions, and Hessian-vector products. Our cost-agnostic framework seamlessly extends to linear OT, Gromov-Wasserstein (GW), fused GW, and their unbalanced counterparts. For balanced OT, our geometric ingredients are computed via efficient conjugate-gradient and iterative Bregman updates. For the unbalanced OT, our operations elegantly reduce to closed-form scalings, completely eliminating inner iterative loops. In both regimes, per-iteration complexity scales linearly with dataset size, and we provide a rank-sufficiency certificate for global optimality verification. Extensive experiments across a range of problem sizes demonstrate that our regularization-free first- and second-order solvers achieve faster convergence and superior performance over existing state-of-the-art low-rank OT solvers.