# Unbalanced Optimal Transport through Non-negative Penalized Linear Regression

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 8 Jun 2021.

## Builds on (most cited first, 15 of 15)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Optimal Entropy-Transport problems and a new Hellinger-Kantorovich distance between positive measures](https://mlsanity.com/paper/1508.07941/) (2015)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [Sinkhorn Divergences for Unbalanced Optimal Transport](https://mlsanity.com/paper/1910.12958/) (2019)
- [Multilevel Clustering via Wasserstein Means](https://mlsanity.com/paper/1706.03883/) (2017)
- [Outlier-Robust Optimal Transport](https://mlsanity.com/paper/2012.07363/) (2020)
- [Celer: a Fast Solver for the Lasso with Dual Extrapolation](https://mlsanity.com/paper/1802.07481/) (2018)
- [Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1711.01851/) (2017)
- [Fast Unbalanced Optimal Transport on a Tree](https://mlsanity.com/paper/2006.02703/) (2020)

## Built on by (most cited first, 30 of 31)

- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [Generative Modeling through the Semi-dual Formulation of Unbalanced Optimal Transport](https://mlsanity.com/paper/2305.14777/) (2023)
- [Optimal Transport for Treatment Effect Estimation](https://mlsanity.com/paper/2310.18286/) (2023)
- [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)
- [Neural Unbalanced Optimal Transport via Cycle-Consistent Semi-Couplings](https://mlsanity.com/paper/2209.15621/) (2022)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [Light Unbalanced Optimal Transport](https://mlsanity.com/paper/2303.07988/) (2023)
- [Unbalanced CO-Optimal Transport](https://mlsanity.com/paper/2205.14923/) (2022)
- [Unbalanced Optimal Transport for Unbalanced Word Alignment](https://mlsanity.com/paper/2306.04116/) (2023)
- [WFR-FM: Simulation-Free Dynamic Unbalanced Optimal Transport](https://mlsanity.com/paper/2601.06810/) (2026)
- [Group-blind optimal transport to group parity and its constrained variants](https://mlsanity.com/paper/2310.11407/) (2023)
- [Quantifying Lexical Semantic Shift via Unbalanced Optimal Transport](https://mlsanity.com/paper/2412.12569/) (2024)
- [Deep Joint Distribution Optimal Transport for Universal Domain Adaptation on Time Series](https://mlsanity.com/paper/2503.11217/) (2025)
- [Unsupervised Learning for Optimal Transport plan prediction between unbalanced graphs](https://mlsanity.com/paper/2506.12025/) (2025)
- [A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignment](https://mlsanity.com/paper/2209.02905/) (2022)
- [Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methods](https://mlsanity.com/paper/2602.10697/) (2026)
- [On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gaps](https://mlsanity.com/paper/2205.13846/) (2022)
- [Optimal Transport for Change Detection on LiDAR Point Clouds](https://mlsanity.com/paper/2302.07025/) (2023)
- [GeOT: A spatially explicit framework for evaluating spatio-temporal predictions](https://mlsanity.com/paper/2410.11709/) (2024)
- [Control, Optimal Transport and Neural Differential Equations in Supervised Learning](https://mlsanity.com/paper/2503.15105/) (2025)
- [Merging Embedded Topics with Optimal Transport for Online Topic Modeling on Data Streams](https://mlsanity.com/paper/2504.07711/) (2025)
- [Globally Solving Unbalanced Optimal Transport and Density Control for Gaussian Distributions](https://mlsanity.com/paper/2605.04246/) (2026)
- [On making optimal transport robust to all outliers](https://mlsanity.com/paper/2206.11988/) (2022)
- [Safe Screening for Unbalanced Optimal Transport](https://mlsanity.com/paper/2307.00247/) (2023)
- [An inexact Bregman proximal point method and its acceleration version for unbalanced optimal transport](https://mlsanity.com/paper/2402.16978/) (2024)
- [On Barycenter Computation: Semi-Unbalanced Optimal Transport-based Method on Gaussians](https://mlsanity.com/paper/2410.08117/) (2024)
- [An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph](https://mlsanity.com/paper/2502.00739/) (2025)
- [Scalable Approximate Algorithms for Optimal Transport Linear Models](https://mlsanity.com/paper/2504.04609/) (2025)
- [Soft-Masked Semi-Dual Optimal Transport for Partial Domain Adaptation](https://mlsanity.com/paper/2505.01664/) (2025)

## Abstract (arXiv)

This paper addresses the problem of Unbalanced Optimal Transport (UOT) in which the marginal conditions are relaxed (using weighted penalties in lieu of equality) and no additional regularization is enforced on the OT plan. In this context, we show that the corresponding optimization problem can be reformulated as a non-negative penalized linear regression problem. This reformulation allows us to propose novel algorithms inspired from inverse problems and nonnegative matrix factorization. In particular, we consider majorization-minimization which leads in our setting to efficient multiplicative updates for a variety of penalties. Furthermore, we derive for the first time an efficient algorithm to compute the regularization path of UOT with quadratic penalties. The proposed algorithm provides a continuity of piece-wise linear OT plans converging to the solution of balanced OT (corresponding to infinite penalty weights). We perform several numerical experiments on simulated and real data illustrating the new algorithms, and provide a detailed discussion about more sophisticated optimization tools that can further be used to solve OT problems thanks to our reformulation.