By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Review

Previous Article
Problems and Techniques
Readers may be surprised to learn that there is something on which everybody in my department agrees: the heating system is absolutely ineffective. Some offices get too hot too fast (usually inhabita...
Next Article
Globalization Techniques for Newton–Krylov Methods and Applications to the Fully Coupled Solution of the Navier–Stokes Equations
A Newton–Krylov method is an implementation of Newton's method in which a Krylov subspace method is used to solve approximately the linear subproblems that determine Newton steps. To enhance ro...

You are logged in to this journal.

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

SIAM Rev. Volume 48, Issue 4, pp. 681-699 (January 2006)

Published November 2, 2006
FULL TEXT OPTIONS   (FREE)
Download PDF (492 kB) View Cart

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.

©2006 Society for Industrial and Applied Mathematics
History: Received May 17, 2004; accepted October 8, 2005; published November 2, 2006
Permalink: http://dx.doi.org/10.1137/S0036144504443821

KEYWORDS and AMS

Keywords
AMS Subject Classifications
60J25, 65F15, 68Q32, 90C22, 90C46

PUBLICATION DATA

ISSN:
0036-1445 (print)   1095-7200 (online)
Publisher:
AIP is a member of CrossRef SIAM

REFERENCES (32)
View in Separate Window/Tab
  1. S. Benson and Y. Ye, DSDP: Dual-Scaling Algorithm for Semidefinite Programming, Tech. Report ANL/MCS-P851-1000, Argonne National Laboratory, Argonne, IL, 2001 doi:10.1137/0523015. [ISI] [ZentralblattMath] [MathRev]
  2. B. Borchers, CSDP, a C library for semidefinite programming, Optim. Methods Softw., 11 (1999), pp. 613–623.
  3. S. Boyd, P. Diaconis, J. Sun, and L. Xiao, Fastest mixing Markov chain on a path, Amer. Math. Monthly, 113 (2006), pp. 70–74.
  4. S. Boyd, P. Diaconis, and L. Xiao, Fastest mixing Markov chain on a graph, SIAM Rev., 46 (2004), pp. 667–689. [MathRev]
  5. S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, UK, 2004. Available online from www.stanford.edu/boyd/cvxbook.
  6. S. J. Cox and M. L. Overton, On the optimal design of columns against buckling, SIAM J. Math. Anal., 23 (1992), pp. 287–325.
  7. S. J. Cox and P. X. Uhlig, Where best to hold a drum fast, SIAM J. Optim., 9 (1999), pp. 948–964. [MathRev]
  8. P. Diaconis and L. Saloff-Coste, Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probab., 6 (1996), pp. 695–750.
  9. M. Fiedler, Absolute algebraic connectivity of trees, Linear Multilinear Algebra, 26 (1990), pp. 85–106.
  10. M. Fiedler, Some minimax problems for graphs, Discrete Math., 121 (1993), pp. 65–74.
  11. K. Fujisawa, M. Kojima, K. Nakata, and M. Yamashita, SDPA (SemiDefinite Programming Algorithm) User's Manual. Version 6.00, Research Reports on Mathematical and Computing Sciences B-308, Tokyo Institute of Technology, Japan, 2002.
  12. F. Göring, C. Helmberg, and M. Wappler, Embedded in the Shadow of the Separator, Preprint 2005-12, Fakultät für Mathematik, Technische Universität Chemnitz, Chemnitz, Germany, 2005.
  13. C. Helmberg, Semidefinite Programming, www-user.tu-chemnitz.de/helmberg/semidef.
  14. C. Helmberg, SBmethod—a C++ Implementation of the Spectral Bundle Method, Tech. Report ZIB-Report 00-35, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, 2000.
  15. R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK, 1985.
  16. A. S. Lewis, Convex analysis on the Hermitian matrices, SIAM J. Optim., 6 (1996), pp. 164–177.
  17. A. Lewis and M. Overton, Eigenvalue optimization, Acta Numerica, 5 (1996), pp. 149–190.
  18. L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25 (1979), pp. 1–7. [ISI] [MathRev]
  19. B. Mohar, Some applications of Laplacian eigenvalues of graphs, in Graph Symmetry: Algebraic Methods and Applications, G. Hahn and G. Sabidussi, eds., NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 497, Kluwer, Dordrecht, The Netherlands, 1997, pp. 227–275.
  20. A. Nemirovski, Prox-method with rate of convergence $O(1/t)$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM J. Optim., 15 (2004), pp. 229–251. [MathRev]
  21. M. L. Overton, On minimizing the maximum eigenvalue of a symmetric matrix, SIAM J. Matrix Anal. Appl., 9 (1988), pp. 256–268. [MathRev]
  22. M. L. Overton, Large-scale optimization of eigenvalues, SIAM J. Optim., 2 (1992), pp. 88–120. [ZentralblattMath] [MathRev]
  23. J. Sturm, Using SeDuMi $1.02$, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11–12 (1999), pp. 625–653.
  24. K. Toh, M. Todd, and R. Tutuncu, SDPT3—a MATLAB software package for semidefinite programming, Optim. Methods Softw., 11 (1999), pp. 545–581.
  25. H. van der Holst, L. Lovász, and A. Schrijver, The Colin de Verdière graph parameter, in Graph Theory and Combinatorial Biology, L. Lovász et al., eds., Bolyai Soc. Math. Stud. 7, János Bolyai Mathematical Society, Budapest, 1999, pp. 29–85.
  26. L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Rev., 38 (1996), pp. 49–95.
  27. L. Vandenberghe, S. Boyd, and A. E. Gamal, Optimizing dominant time constant in RC circuits, IEEE Trans. Comput. Aided Design, 2 (1998), pp. 110–125.
  28. K. Weinberger and L. Saul, Unsupervised learning of image manifolds by semidefinite programming, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR-04), Washington, D. C., 2004, pp. 988–995.
  29. K. Weinberger, F. Sha, and L. Saul, Learning a kernel matrix for nonlinear dimensionality reduction, in Proceedings of the 21st International Conference on Machine Learning (ICML-04), Banff, Canada, 2004, pp. 839–846.
  30. S.-P. Wu and S. Boyd, SDPSOL: A parser/solver for semidefinite programs with matrix structure, in Advances in Linear Matrix Inequality Methods in Control, L. E. Ghaoui and S.-I. Niculescu, eds., SIAM, Philadelphia, 2000, pp. 79–91.
  31. L. Xiao and S. Boyd, Fast linear iterations for distributed averaging, Systems Control Lett., 53 (2004), pp. 65–78. [Inspec]
  32. L. Xiao and S. Boyd, Optimal scaling of a gradient method for distributed resource allocation, to appear in J. Optim. Theory Appl., 129 (2006). Available online from www.stanford.edu/boyd/fast_redstb.