The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem

Jun Sun, Stephen Boyd, Lin Xiao, Persi Diaconis

Research output: Contribution to journalArticlepeer-review

108 Scopus citations

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 λ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 λ 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, i.e., 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.

Original languageEnglish
Pages (from-to)681-699
Number of pages19
JournalSIAM Review
Volume48
Issue number4
DOIs
StatePublished - Dec 2006
Externally publishedYes

Keywords

  • Dimensionality reduction
  • Fast mixing
  • Markov process
  • Second smallest eigenvalue
  • Semidefinite programming

Fingerprint

Dive into the research topics of 'The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem'. Together they form a unique fingerprint.

Cite this