  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.
