# Unbalanced Low-rank Optimal Transport Solvers

arXiv: https://arxiv.org/abs/2305.19727 · HTML: https://mlsanity.com/paper/2305.19727/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 61 references that are in the map.
- First posted on arXiv 31 May 2023.

## Builds on (most cited first, 30 of 31)

- [DINOv2: Learning Robust Visual Features without Supervision](https://mlsanity.com/paper/2304.07193/) (2023)
- [Unsupervised Learning of Visual Features by Contrasting Cluster Assignments](https://mlsanity.com/paper/2006.09882/) (2020)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015)
- [Sinkformers: Transformers with Doubly Stochastic Attention](https://mlsanity.com/paper/2110.11773/) (2021)
- [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Optimal Transport Tools (OTT): A JAX Toolbox for all things Wasserstein](https://mlsanity.com/paper/2201.12324/) (2022)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem](https://mlsanity.com/paper/1905.11882/) (2019)
- [Faster Wasserstein Distance Estimation with the Sinkhorn Divergence](https://mlsanity.com/paper/2006.08172/) (2020)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm](https://mlsanity.com/paper/2002.03293/) (2020)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Supervised Training of Conditional Monge Maps](https://mlsanity.com/paper/2206.14262/) (2022)
- [The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation](https://mlsanity.com/paper/2009.04266/) (2020)
- [Statistical Optimal Transport via Factored Couplings](https://mlsanity.com/paper/1806.07348/) (2018)
- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Aligning individual brains with Fused Unbalanced Gromov-Wasserstein](https://mlsanity.com/paper/2206.09398/) (2022)
- [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022)
- [Low-rank Optimal Transport: Approximation, Statistics and Debiasing](https://mlsanity.com/paper/2205.12365/) (2022)
- [Quantized Gromov-Wasserstein](https://mlsanity.com/paper/2104.02013/) (2021)
- [Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces](https://mlsanity.com/paper/2002.01615/) (2020)
- [Linear Time Sinkhorn Divergences using Positive Features](https://mlsanity.com/paper/2006.07057/) (2020)
- [Sample-Optimal Low-Rank Approximation of Distance Matrices](https://mlsanity.com/paper/1906.00339/) (2019)
- [Fast and Scalable Optimal Transport for Brain Tractograms](https://mlsanity.com/paper/2107.02010/) (2021)
- [A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2303.06595/) (2023)

## Built on by (most cited first, 7 of 7)

- [GENOT: Entropic (Gromov) Wasserstein Flow Matching with Applications to Single-Cell Genomics](https://mlsanity.com/paper/2310.09254/) (2023)
- [Hierarchical Refinement: Optimal Transport to Infinity and Beyond](https://mlsanity.com/paper/2503.03025/) (2025)
- [Structured Transforms Across Spaces with Cost-Regularized Optimal Transport](https://mlsanity.com/paper/2311.05788/) (2023)
- [A Riemannian Approach to Low-Rank Optimal Transport](https://mlsanity.com/paper/2606.12120/) (2026)
- [Multiscale Supervised Unbalanced Optimal Transport Flow Matching](https://mlsanity.com/paper/2605.16529/) (2026)
- [Attribution Markets: A Fisher-Market Formulation for Fractional Credit Assignment Between Planned Tasks and Performed Actions](https://mlsanity.com/paper/2607.20694/) (2026)
- [A Unified Dual Method for Matching Problems](https://mlsanity.com/paper/2609.39339/) (2026)

## Abstract (arXiv)

The relevance of optimal transport methods to machine learning has long been hindered by two salient limitations. First, the O(n3) computational cost of standard sample-based solvers (when used on batches of n samples) is prohibitive. Second, the mass conservation constraint makes OT solvers too rigid in practice: because they must match textitall points from both measures, their output can be heavily influenced by outliers. A flurry of recent works in OT has addressed these computational and modelling limitations, but has resulted in two separate strains of methods: While the computational outlook was much improved by entropic regularization, more recent O(n) linear-time textitlow-rank solvers hold the promise to scale up OT further. On the other hand, modelling rigidities have been eased owing to unbalanced variants of OT, that rely on penalization terms to promote, rather than impose, mass conservation. The goal of this paper is to merge these two strains, to achieve the promise of textitboth versatile/scalable unbalanced/low-rank OT solvers. We propose custom algorithms to implement these extensions for the linear OT problem and its Fused-Gromov-Wasserstein generalization, and demonstrate their practical relevance to challenging spatial transcriptomics matching problems.