Timezone: »

 
Poster
Unbalanced Optimal Transport through Non-negative Penalized Linear Regression
Laetitia Chapel · Rémi Flamary · Haoran Wu · Cédric Févotte · Gilles Gasso

Wed Dec 08 12:30 AM -- 02:00 AM (PST) @
in Poster Session 3 »

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.

Keywords: Optimization · Optimal Transport

Author Information

Laetitia Chapel (IRISA)
Rémi Flamary (École Polytechnique)
Haoran Wu (INSA Rennes)
Cédric Févotte (CNRS, University of Toulouse)

Cédric Févotte is a CNRS research director with the Institut de Recherche en Informatique de Toulouse (IRIT). Previously, he has been a CNRS researcher at Laboratoire Lagrange (Nice, 2013-2016) & Télécom ParisTech (2007-2013), a research engineer at Mist-Technologies (the startup that became Audionamix, 2006-2007) and a postdoc at University of Cambridge (2003-2006). He holds MEng and PhD degrees in EECS from École Centrale de Nantes. His research interests concern statistical signal processing and machine learning, with particular interests in matrix factorisation, representation learning, source separation and recommender systems. He is currently the principal investigator of the European Research Council (ERC) project FACTORY (New paradigms for latent factor estimation, 2016-2022, 2M€).

Gilles Gasso (LITIS - INSA Rouen Normandie)

More from the Same Authors