The Sinkhorn Knopp Algorithm — Without Proof

I've recently come across various mentions of the Sinkhorn Knopp algorithm. It deals with scaling the rows and columns of a non-negative matrix A such that its rows and columns all sum to 1 (i.e. it is doubly-stochastic). It has impressive applications in assignment problems and has been used by the authors in https://arxiv.org/abs/1911.05371 and https://psarlin.com/superglue/.

As a first step I thought I'd give its implementation a try, without attempting its proof.

From the Wikipedia page I see that:

"A simple iterative method to approach the double stochastic matrix is to alternately rescale all rows and all columns of A to sum to 1. Sinkhorn and Knopp presented this algorithm and analysed its convergence."

So let's give that a go!

In the following I am going to initialise a random matrix A with elements in the range [0,1), so non-negative. I then initialise two diagonal matrices D1 and D2 to identity to scale the rows and the columns respectively.

As suggested by the algorithm describe on Wikipedia, I iterate alternatively between normalising the rows and then normalising the columns — keeping track of the normalisation coefficients in the matrices D1 and D2.

Alas! We do get the convergence to a doubly-stochastic matrix :)

• A less hacky version of this would iterate until some convergence criterion is reached e.g. the deviation of the sums from a vector of ones.
• In the future, I will address the proof of the convergence of this method for the required conditions.