Tiny VoltSinkhorn distance
This post focuses on the derivation of (dual) Sinkhorn distances introduced in the paper Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances. The algorithm is the matrix decomposition using Sinkhorn iterations that was covered in the previous post.
0. The problem
The problem is to learn an assignment from probability distribution r to a probability distribution c with the lowest cost. The cost of an assignment i ā j is given by . The matrix is a cost matrix. This assignment can be described by a joint probability distribution given by a matrix whose rows sum to and whose columns sum to . Thus the total cost for a given assignment is given by . Both matrices have a shape of .
This is a linear programming problem with a complexity of . The paper introduces a regularization term to turn it into a convex optimization problem: needs to have entropy at least , where is a regularization parameter.
It can be shown that when lies in the cone of distance matrices, the regularized metric is a valid distance.
1. (Dual) Sinkhorn distances
In practice however, it is still not fast enough to solve the regularized problem. A "dual" version of the regularized problem is introduced which has a nice solution:
Given
r,candM, findPthat minimizes where is a regularization parameter.
This expression has a nice solution as we will see below.
2. Derivation based on Lagrange multipliers
We have the following Lagrangian:
How do we determine the diagonal matrices and ? We use Sinkhorn-Knopp iteration to alternately scale the rows and columns of until the row and column sums are equal to and respectively.
You can check out the official implementation here.