Iterative Bregman Projections and Bregman-Dykstra Regularized Optimal Transport

Iterative Bregman Projections and Bregman-Dykstra Regularized Optimal Transport is a convex-analytic optimization framework introduced by Benamou, Carlier, Cuturi, Nenna, and Peyré (2015) that reformulates entropically regularized linear optimal transport, multi-marginal transport, Wasserstein barycenters, tomographic marginal constraints, partial optimal transport, capacity-constrained transport, and martingale transport as Kullback-Leibler Bregman projections min_{gamma in cap_{l=1}^L C_l} KL(gamma | xi) of the Gibbs kernel xi = exp(-C / epsilon) onto intersections of closed convex sets C_1, ..., C_L. When every C_l is an affine subspace (including two-marginal transport C_1 = {gamma 1 = p}, C_2 = {gamma^T 1 = q} in Proposition 1 and multi-coupling Wasserstein barycenters C_1 = {gamma_k 1 = p_k}, C_2 = {exists p : gamma_k^T 1 = p} with geometric-mean update p^{(n)} = prod_{k=1}^K (gamma_k^{(n)T} 1)^{lambda_k} in Proposition 2), cyclic Iterative Bregman Projections gamma^{(n)} = P_{C_{[n]}}^{KL}(gamma^{(n-1)}) converge globally to the exact KL projection onto cap_{l=1}^L C_l (Equation 3). When any constraint C_l is a non-affine convex inequality or cone constraint (such as partial transport total mass gamma^T 1 <= q and 1^T gamma 1 = m in Proposition 5 or pointwise capacity bounds gamma <= bar{gamma} in Section 5.2), naive cyclic projections fail to converge to the KL optimum and the framework employs Dykstra's algorithm with multiplicative dual memory variables q^{(n)} = q^{(n-L)} odot (gamma^{(n-1)} / gamma^{(n)}) and updates gamma^{(n)} = P_{C_{[n]}}^{KL}(gamma^{(n-1)} odot q^{(n-L)}) (Equation 4).