On the pythagorean structure of the optimal transport for separable cost functions

In this paper, we study the optimal transport problem induced by two measures supported over two polish spaces, namely, X and Y, which are the product of n smaller polish spaces, that is, X =×nj=1 Xj and Y = ×nj=1 Yj . In particular, we focus on problems induced by a cost function c W X × Y→[0,+∞) that is separable; i.e., c is such that c =c1 C+...+cn, where each cj depends only on the couple (xj, yj), and thus cj : Xj × Yj → [0,+∞). Noticeably, if X = Y = Rn, this class of cost functions includes all the lpp costs. Our main result proves that the optimal transportation plan with respect to a separable cost function between two given measures can be expressed as the composition of n different lower-dimensional transports, one for each pair of coordinates (xi, yi) in X × Y . This allows us to decompose the entire Wasserstein cost as the sum of n lower-dimensional Wasserstein costs and to prove that there always exists an optimal transportation plan whose random variable enjoys a conditional independence property with respect to its marginals.We then show that our formalism allows us to explicitly compute the optimal transportation plan between two probability measures when each measure has independent marginals. Finally, we focus on two specific frameworks. In the first one, the cost function is a separable distance, i.e., d = d1 + d2, where both d1 and d2 are distances themselves. In the second one, both measures are supported over Rn and the cost function is of the form c(x,y) = h(|x1-y1|) + h(|x2 - y2|), where h is a convex function such that h(0) = 0.