Fastest Mixing Markov Chain on a Graph
From MaRDI portal
Publication:4652267
DOI10.1137/S0036144503423264zbMath1063.60102OpenAlexW2134711723MaRDI QIDQ4652267
Persi Diaconis, Lin Xiao, Stephen P. Boyd
Publication date: 25 February 2005
Published in: SIAM Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0036144503423264
semidefinite programmingsubgradient methodfast mixingMarkov chains, second largest eigenvalue modulus
Computational methods in Markov chains (60J22) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical mathematical programming methods (65K05) Semidefinite programming (90C22) Optimality conditions and duality in mathematical programming (90C46) Continuous-time Markov processes on discrete state spaces (60J27)
Related Items
Variational analysis of the Ky Fan \(k\)-norm, The generalized distance spectrum of a graph and applications, Matrix Relaxations in Combinatorial Optimization, Graph diameter, eigenvalues, and minimum-time consensus, Eigen-stratified models, Optimization of steerable sensor network for threat detection, Optimal strategies in the average consensus problem, Is ADMM always faster than average consensus?, Inequalities for the spectra of symmetric doubly stochastic matrices, Efficient projection onto the intersection of a half-space and a box-like set and its generalized Jacobian, Optimal scaling of a gradient method for distributed resource allocation, Randomized Shortest-Path Problems: Two Related Models, Spectrally optimized pointset configurations, A general selective averaging method for piecewise constant signal and image processing, Comparison inequalities and fastest-mixing Markov chains, Fastest expected time to mixing for a Markov chain on a directed graph, A Spectral Approach to Network Design, Distributed set-valued estimation in sensor networks with limited communication data rate, Efficient and Reliable Overlay Networks for Decentralized Federated Learning, Optimal spatially-dependent diffusion tensors, On random walks and switched random walks on homogeneous spaces, Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization, Dimension reduction for maximum matchings and the fastest mixing Markov chain, A divide-and-conquer algorithm for distributed optimization on networks, A decentralized smoothing quadratic regularization algorithm for composite consensus optimization with non-Lipschitz singularities, Accelerating distributed average consensus by exploring the information of second-order neighbors, Linear Time Average Consensus and Distributed Optimization on Fixed Graphs, Unnamed Item, Safe Metropolis-Hastings algorithm and its application to swarm control, Proximal gradient/semismooth Newton methods for projection onto a polyhedron via the duality-gap-active-set strategy, Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian, Localization and approximations for distributed non-convex optimization, Golden ratio proximal gradient ADMM for distributed composite convex optimization, Geometric bounds on the fastest mixing Markov chain, A sum-over-paths extension of edit distances accounting for all sequence alignments, Spectral and graph-theoretic bounds on steady-state-probability estimation performance for an ergodic Markov chain, Maximum Kolmogorov-Sinai entropy versus minimum mixing time in Markov chains, Randomized leader election, Hearing the clusters of a graph: A distributed algorithm, Communication constraints in the average consensus problem, Recent advances in optimization and game theoretic control for networked systems, A graph-theoretic approach on optimizing informed-node selection in multi-agent tracking control, The geometric properties of a class of nonsymmetric cones, Finding the projection onto the intersection of a closed half-space and a variable box, Optimizing the asymptotic convergence rate of the Diaconis-Holmes-Neal sampler, Random walk centrality for temporal networks, Revisiting EXTRA for Smooth Distributed Optimization, Improved mixing rates of directed cycles by added connection, Remarks and open problems on the minimum permanent of acyclic doubly stochastic matrices, Unnamed Item, Faster response in bounded-update-rate, discrete-time linear networks using delayed self-reinforcement, Fast algorithm for singly linearly constrained quadratic programs with box-like constraints, Symmetry in semidefinite programs, Mean square average-consensus under measurement noises and fixed topologies: necessary and sufficient conditions, Maximizing algebraic connectivity for certain families of graphs, Markov chain mixing time on cycles, Fast linear iterations for distributed averaging, Characterizing limits and opportunities in speeding up Markov chain mixing, A semismooth Newton-CG based dual PPA for matrix spectral norm approximation problems, A MARKOV-PROCESS INSPIRED CA MODEL OF HIGHWAY TRAFFIC, Cohesive networks using delayed self reinforcement, A Distributed ADMM-like Method for Resource Sharing over Time-Varying Networks, Decentralized and privacy-preserving low-rank matrix completion, Markov Chain Approach to Probabilistic Guidance for Swarms of Autonomous Agents, A decentralized algorithm for spectral analysis, Fastest mixing Markov chain problem for the union of two cliques, On the Convergence of Decentralized Gradient Descent, A framework for decentralised feedback connectivity control with application to sensor networks, Rapid Mixing and Markov Bases, On stochastic mirror descent with interacting particles: convergence properties and variance reduction, Fastest mixing reversible Markov chain on friendship graph: trade-off between transition probabilities among friends and convergence rate, Distributed networked set-membership filtering with ellipsoidal state estimations, Average consensus with weighting matrix design for quantized communication on directed switching graphs, The impact of multi-group multi-layer network structure on the performance of distributed consensus building strategies, EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization, Emergence of Balance from a Model of Social Dynamics, Consensus on simplicial complexes: Results on stability and synchronization, A graph theoretical approach to input design for identification of nonlinear dynamical models, Adaptive online distributed optimization in dynamic environments, Combinatorial Algorithms for Minimizing the Maximum Laplacian and Signless Laplacian Eigenvalues of Weighted Graphs, Random Walks, Directed Cycles, and Markov Chains, Fastest random walk on a path, Optimizing the Diffusion System Based on Continuous-Time Consensus Algorithm
Uses Software
