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)
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)
- 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 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.