The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
- Creators
- Sun, Jun
- Boyd, Stephen
- Xiao, Lin
- Diaconis, Persi
Abstract
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.
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.Attached Files
Published - SUNsiamr06.pdf
Files
Name | Size | Download all |
---|---|---|
md5:5784a69892c28f13dae0949d11df625e
|
503.8 kB | Preview Download |
Additional details
- Eprint ID
- 6632
- Resolver ID
- CaltechAUTHORS:SUNsiamr06
- Created
-
2006-12-15Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field