Generating Doubly Stochastic Matrices

Constrained Optimization

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

"doubly-stochastic3_1.gif"

"doubly-stochastic3_2.gif"

"doubly-stochastic3_3.gif"

"doubly-stochastic3_4.gif"

"doubly-stochastic3_5.gif"

"doubly-stochastic3_6.gif"

"doubly-stochastic3_7.gif"

"doubly-stochastic3_8.gif"

Markov Chain sampling

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

"doubly-stochastic3_9.gif"

"doubly-stochastic3_10.gif"

"doubly-stochastic3_11.gif"

"doubly-stochastic3_12.gif"

Iterative Proportional Fitting (Dr.Teh suggestion)

Normalize rows/columns repeatedly

"doubly-stochastic3_13.gif"

"doubly-stochastic3_14.gif"

"doubly-stochastic3_15.gif"

How long does it take to converge?

"doubly-stochastic3_16.gif"

"doubly-stochastic3_17.gif"

Graphics:Number of Iterations till convergence

Convex Combination of Permutation Matrices (Jeremy's suggestion)

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

In[1007]:=

"doubly-stochastic3_19.gif"

Out[1008]=

"doubly-stochastic3_20.gif"

In[1010]:=

"doubly-stochastic3_21.gif"

Out[1010]=

"doubly-stochastic3_22.gif"

In[1011]:=

"doubly-stochastic3_23.gif"

Out[1014]=

"doubly-stochastic3_24.gif"


Created by Wolfram Mathematica 6.0  (18 December 2007) Valid XHTML 1.1!