A Caltech Library Service

The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem

Sun, Jun and Boyd, Stephen and Xiao, Lin and Diaconis, Persi (2006) The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem. SIAM Review, 48 (4). pp. 681-699. ISSN 0036-1445. doi:10.1137/S0036144504443821.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 determined by the second smallest eigenvalue lambda_2 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 lambda_2 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, , the problem of choosing a set of points to be as far apart as possible, measured by their variance, while respecting local distance constraints. This MVU problem is closely related to a problem recently proposed by Weinberger and Saul as a method for "unfolding" high-dimensional data that lies on a low-dimensional manifold. The duality between the FMMP and MVU problems sheds light on both problems, and allows us to characterize and, in some cases, find optimal solutions.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:©2006 Society for Industrial and Applied Mathematics (Received May 17, 2004; accepted October 8, 2005; published November 2, 2006) We thank the referees for helpful comments.
Subject Keywords:Markov process; fast mixing; second smallest eigenvalue; semidefinite programming; dimensionality reduction
Issue or Number:4
Record Number:CaltechAUTHORS:SUNsiamr06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6632
Deposited By: Archive Administrator
Deposited On:15 Dec 2006
Last Modified:08 Nov 2021 20:35

Repository Staff Only: item control page