A semidefinite bound for mixing rates of Markov chains

Nabil Kahalé

Type: Book-Chapter

Publication Date: 1996-01-01

Citations: 21

DOI: https://doi.org/10.1007/3-540-61310-2_15

View Publication

Locations

Lecture notes in computer science - View

Similar Works

Action	Title	Year	Authors
+	A semidefinite bound for mixing rates of Markov chains	1997	Nabil Kahalé
+ PDF Chat	Fastest Mixing Markov Chain on a Graph	2004	Stephen Boyd Persi Diaconis Lin Xiao
+ PDF Chat	Geometric Bounds for Eigenvalues of Markov Chains	1991	Persi Diaconis Daniel W. Stroock
+	Fastest Mixing Reversible Markov Chains on Graphs With Degree Proportional Stationary Distributions	2014	Onur Cihan Mehmet Akar
+	Regularized modified log-Sobolev inequalities, and comparison of Markov chains	2022	Konstantin Tikhomirov Pierre Youssef
+	Fastest Mixing Reversible Markov Chain: Clique Lifted Graphs and Subgraphs	2020	Saber Jafarizadeh
+	Spectral Techniques, Semidefinite Programs, and Random Graphs	2005	Alan Frieze
+	Fast randomized entropically regularized semidefinite programming	2023	Michael Lindsey
+	A Randomized Method for Solving Semidefinite Programs	2007	B. T. Polyak Pavel Shcherbakov
+	Improved Mixing Rates of Directed Cycles with Additional Sparse Interconnections	2023	Balázs Gerencsér Julien M. Hendrickx
+	Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain	2022	Vishesh Jain Huy Tuan Pham Thuy-Duong Vuong
+ PDF Chat	Fastest Mixing Markov Chain on Graphs with Symmetries	2009	Stephen Boyd Persi Diaconis Pablo A. Parrilo Lin Xiao
+ PDF Chat	Efficient coupling on the circle	2000	Thomas Mountford M. Cranston
+	Sum-of-Squares proofs of logarithmic Sobolev inequalities on finite Markov chains	2021	Oisín Faust Hamza Fawzi
+	The smallest eigenvalue for reversible Markov chains	2004	Xiao‐Dong Zhang
+	Bounding Fastest Mixing	2004	Sébastien Roch
+ PDF Chat	The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem	2006	Jun Sun Stephen Boyd Lin Xiao Persi Diaconis
+	Convergence rates for reversible Markov chains without the assumption of nonnegative definite matrices	2010	Yong-Hua Mao
+	An $\widetilde\mathcal{O}(m/\varepsilon^3.5)$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints	2020	Yin Tat Lee Swati Padmanabhan
+	General mixing time bounds for finite Markov chains via the absolute spectral gap	2013	Daniel C. Jerison

Works That Cite This (16)

Action	Title	Year	Authors
+ PDF Chat	Efficient Simulation of High Dimensional Gaussian Vectors	2018	Nabil Kahalé
+ PDF Chat	Relations entre isopérimétrie et trou spectral pour les chaînes de Markov finies	1999	Laurent Miclo
+	Lectures on finite Markov chains	1997	Laurent Saloff‐Coste
+	Graph Embeddings and Laplacian Eigenvalues	2000	Stephen Guattery Gary L. Miller
+ PDF Chat	A distributed dynamical scheme for fastest mixing Markov chains	2009	Michael M. Zavlanos Daniel E. Koditschek George J. Pappas
+	Optimal Embeddings and Eigenvalues in Support Theory	2007	Erik G. Boman Stephen Guattery Bruce Hendrickson
+ PDF Chat	Fastest Mixing Markov Chain on a Graph	2004	Stephen Boyd Persi Diaconis Lin Xiao
+	On the Quality of Spectral Separators	1998	Stephen Guattery Gary L. Miller
+ PDF Chat	The Path Resistance Method for Bounding the Smallest Nontrivial Eigenvalue of a Laplacian	1999	Stephen Guattery T. Leighton Gary L. Miller
+	Logarithmic Sobolev, isoperimetry and transport inequalities on graphs	2016	Yu Tao Ran Wang Li Ming Wu

Works Cited by This (10)

Action	Title	Year	Authors
+ PDF Chat	Comparison Theorems for Reversible Markov Chains	1993	Persi Diaconis Laurent Saloff‐Coste
+	Characterization of the subdifferential of some matrix norms	1992	G. A. Watson
+	Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow	1992	Alistair Sinclair
+ PDF Chat	Geometric Bounds for Eigenvalues of Markov Chains	1991	Persi Diaconis Daniel W. Stroock
+	What do we know about the Metropolis algorithm?	1995	Persi Diaconis Laurent Saloff‐Coste
+ PDF Chat	Eigenvalue Bounds on Convergence to Stationarity for Nonreversible Markov Chains, with an Application to the Exclusion Process	1991	James Allen Fill
+ PDF Chat	Approximate counting, uniform generation and rapidly mixing Markov chains	1989	Alistair Sinclair Mark Jerrum
+ PDF Chat	Approximating the Permanent	1989	Mark Jerrum Alistair Sinclair
+	Random walks in a convex body and an improved volume algorithm	1993	László Lovász Miklós Simonovits
+	Semidefinite Programming	1996	Lieven Vandenberghe Stephen Boyd