## The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding ProblemJ. Sun, S. Boyd, L. Xiao, and P. Diaconis
We consider a Markov process on a connected graph, with edges labeled with
transition rates between the adjacent vertices. The distribution of the Markov
process converges to the uniform distribution at a rate determinined by the
second smallest eigenvalue of the Laplacian of the weighted graph. In this
paper we consider the problem of assigning transition rates to the edges so as
to maximize the second smallest eigenvalue, subject to a linear constraint on
the rates. This is the problem of finding the fastest mixing Markov process
(FMMP) on the graph. We show that the FMMP problem is a convex optimization
problem, which can in turn be expressed as a semidefinite program, and
therefore effectively solved numerically. We formulate a dual of the FMMP
problem, and show that it has a natural geometric interpretation as a maximum
variance unfolding (MVU) problem, |