Poster

Low-Rank Sinkhorn Factorization

Meyer Scetbon · Marco Cuturi · Gabriel Peyré

Keywords: [ Algorithms ] [ Optimal Transport ]

[ Abstract ]
[ Paper ] [ Visit Poster at Spot C4 in Virtual World ]
Tue 20 Jul 9 a.m. PDT — 11 a.m. PDT
 
Spotlight presentation: Optimal Transport
Tue 20 Jul 5 a.m. PDT — 6 a.m. PDT

Abstract:

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.

Chat is not available.