Timezone: »

 
Poster
Low-Rank Sinkhorn Factorization
Meyer Scetbon · Marco Cuturi · Gabriel Peyré

Tue Jul 20 09:00 AM -- 11:00 AM (PDT) @
in Poster Session 1 »

Several recent applications of optimal transport (OT) theory to machine learning have relied on regularization, notably entropy and the Sinkhorn algorithm. Because matrix-vector products are pervasive in the Sinkhorn algorithm, several works have proposed to \textit{approximate} kernel matrices appearing in its iterations using low-rank factors. Another route lies instead in imposing low-nonnegative rank constraints on the feasible set of couplings considered in OT problems, with no approximations on cost nor kernel matrices. This route was first explored by~\citet{forrow2018statistical}, who proposed an algorithm tailored for the squared Euclidean ground cost, using a proxy objective that can be solved through the machinery of regularized 2-Wasserstein barycenters. Building on this, we introduce in this work a generic approach that aims at solving, in full generality, the OT problem under low-nonnegative rank constraints with arbitrary costs. Our algorithm relies on an explicit factorization of low-rank couplings as a product of \textit{sub-coupling} factors linked by a common marginal; similar to an NMF approach, we alternatively updates these factors. We prove the non-asymptotic stationary convergence of this algorithm and illustrate its efficiency on benchmark experiments.

Keywords: Algorithms · Optimal Transport

Author Information

Meyer Scetbon (CREST, ENSAE)
Marco Cuturi (Google)
Gabriel Peyré (CNRS and ENS)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors