Sinkhorn's Algorithm

From Optimal Transport Wiki
Jump to navigation Jump to search

Sinkhorn's Algorithm is an iterative numerical method used to obtain an optimal transport plan for the Kantorovich Problem with entropic regularization in the case of finitely supported positive measures . For further reading see Peyré & Cuturi (pg. 62-73)[1]

Continuous Problem Formulation

Entropic regularization modifies the Kantorovich problem by adding a Kullback-Leibler divergence term to the optimization goal. Specifically, the general form of the problem is now to determine

where is the product measure of and , and where

whenever the Radon-Nikodym derivative exists (i.e. when is absolutely continuous w.r.t. ) and otherwise. This form of the KL divergence is applicable even when differ in total mass and it reduces to the standard definition whenever and have equal total mass. From this definition it immediately follows that for an optimal coupling must be absolutely continuous w.r.t . As a result, the optimal plan is in some sense less singular and hence "smoothed out."

Discrete Problem Formulation

To apply Sinkhorn's algorithm to approximate , it will be necessary to assume finite support so let and and denote the corresponding vector of weights by and . Additionally let and denote the discrete version of by . This lets us write the entropic Kantorovich problem as


See here for more on discrete optimal transport.

Characterizing the Solution

The solution to the discrete problem formulation is unique and has a special form.

Theorem (Peyré & Cuturi, Proposition 4.3 on pg. 63)[1]
The solution to discrete regularized Kantorovich problem is unique and has the form for some where . Moreover, and are unique up to multiplication and division by some scaling factor.

Sinkhorn's Algorithm

Sinkhorn's algorithm takes advantage of the aforementioned characterization result to iteratively approximate the scaling factors and . The procedure is simple and only involves matrix-vector multiplication and entrywise division as follows

Once a sufficient number of iterations have been taken, we let be our approximation of the optimal plan.