FASTEST MIXING MARKOV CHAIN ON GRAPHS WITH SYMMETRIES
We show how to exploit symmetries of a graph to efficiently compute the fastest mixing Markov chain on the graph (i.e., find the transition probabilities on the edges to minimize the second-largest eigenvalue modulus of the transition probability matrix). Exploiting symmetry can lead to significant...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2010
|
| Online Access: | http://hdl.handle.net/1721.1/52441 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1826203985584848896 |
|---|---|
| author | Xiao, Lin Diaconis, Persi Boyd, Stephen P. Parrilo, Pablo A. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Xiao, Lin Diaconis, Persi Boyd, Stephen P. Parrilo, Pablo A. |
| author_sort | Xiao, Lin |
| collection | MIT |
| description | We show how to exploit symmetries of a graph to efficiently compute the fastest mixing Markov chain on the graph (i.e., find the transition probabilities on the edges to minimize the second-largest eigenvalue modulus of the transition probability matrix). Exploiting symmetry can lead to significant reduction in both the number of variables and the size of matrices in the corresponding semidefinite program, and thus enable numerical solution of large-scale instances that are otherwise computationally infeasible. We obtain analytic or semianalytic results for particular classes of graphs, such as edge-transitive and distance-transitive graphs. We describe two general approaches for symmetry exploitation, based on orbit theory and block-diagonalization, respectively, and establish a formal connection between them. |
| first_indexed | 2024-09-23T12:47:00Z |
| format | Article |
| id | mit-1721.1/52441 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:47:00Z |
| publishDate | 2010 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/524412022-09-28T09:58:48Z FASTEST MIXING MARKOV CHAIN ON GRAPHS WITH SYMMETRIES Xiao, Lin Diaconis, Persi Boyd, Stephen P. Parrilo, Pablo A. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Parrilo, Pablo A. Parrilo, Pablo A. We show how to exploit symmetries of a graph to efficiently compute the fastest mixing Markov chain on the graph (i.e., find the transition probabilities on the edges to minimize the second-largest eigenvalue modulus of the transition probability matrix). Exploiting symmetry can lead to significant reduction in both the number of variables and the size of matrices in the corresponding semidefinite program, and thus enable numerical solution of large-scale instances that are otherwise computationally infeasible. We obtain analytic or semianalytic results for particular classes of graphs, such as edge-transitive and distance-transitive graphs. We describe two general approaches for symmetry exploitation, based on orbit theory and block-diagonalization, respectively, and establish a formal connection between them. 2010-03-09T20:26:42Z 2010-03-09T20:26:42Z 2009-06 2009-04 Article http://purl.org/eprint/type/JournalArticle 1095-7197 http://hdl.handle.net/1721.1/52441 Boyd, Stephen et al. “Fastest Mixing Markov Chain on Graphs with Symmetries.” SIAM Journal on Optimization 20.2 (2009): 792-819. © 2009 Society for Industrial and Applied Mathematics https://orcid.org/0000-0003-1132-8477 en_US http://dx.doi.org/10.1137/070689413 SIAM Journal on Scientific Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Xiao, Lin Diaconis, Persi Boyd, Stephen P. Parrilo, Pablo A. FASTEST MIXING MARKOV CHAIN ON GRAPHS WITH SYMMETRIES |
| title | FASTEST MIXING MARKOV CHAIN ON GRAPHS WITH SYMMETRIES |
| title_full | FASTEST MIXING MARKOV CHAIN ON GRAPHS WITH SYMMETRIES |
| title_fullStr | FASTEST MIXING MARKOV CHAIN ON GRAPHS WITH SYMMETRIES |
| title_full_unstemmed | FASTEST MIXING MARKOV CHAIN ON GRAPHS WITH SYMMETRIES |
| title_short | FASTEST MIXING MARKOV CHAIN ON GRAPHS WITH SYMMETRIES |
| title_sort | fastest mixing markov chain on graphs with symmetries |
| url | http://hdl.handle.net/1721.1/52441 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT xiaolin fastestmixingmarkovchainongraphswithsymmetries AT diaconispersi fastestmixingmarkovchainongraphswithsymmetries AT boydstephenp fastestmixingmarkovchainongraphswithsymmetries AT parrilopabloa fastestmixingmarkovchainongraphswithsymmetries |