Iterative Bregman Projections for Regularized Transportation Problems

Understand

This article details a general numerical framework to approximate so-lutions to linear programs related to optimal transport.

• The general idea is to introduce an entropic regularization of the initial linear program.
• This regularized problem corresponds to a Kullback-Leibler Bregman di-vergence projection of a vector (representing some initial joint distribu-tion) on the polytope of constraints.
• We show that for many problems related to optimal transport, the set of linear constraints can be split in an intersection of a few simple constraints, for which the projections can be computed in closed form.