Generating Doubly Stochastic Matrices

Constrained Optimization

Generate random matrix, find closest doubly stochastic in least square sense

Markov Chain sampling

Start with a random permutation matrix, randomly modify 4 entries each time

Iterative Proportional Fitting (Dr.Teh suggestion)

Normalize rows/columns repeatedly

How long does it take to converge?

Convex Combination of Permutation Matrices (Jeremy's suggestion)

(Birkhoff Theorem, 8.7 .1 from Horn and Johnson)

In[1007]:=

Out[1008]=

In[1010]:=

Out[1010]=

In[1011]:=

Out[1014]=

Created by Wolfram Mathematica 6.0  (18 December 2007)