Fastest Mixing Markov Chain on a Graph
fast mixingMarkov chains, second largest eigenvalue modulussemidefinite programmingsubgradient method
Computational methods in Markov chains (60J22) Continuous-time Markov processes on discrete state spaces (60J27) 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)
The connected graph \(G=(V,E)\) with vertex set \(V=\{1,\dots,n\}\) and edge set \(E \subseteq V \times V\) is considered. It is assumed that \(G\) is a symmetric graph with self-loops, i.e. \((i,j) \in E\) iff \((j,i) \in E\) and \((i,i) \in E\) for all \(i\). The discrete-time Markov chain \(X(t) \in V\), \(t=1,2,\dots,\) is described by transition probabilities \(p_{ij} =\text{Prob}(X(t+1)=j\mid X(t)=i)\) subjected to restrictions \(p_{ij}=p_{ji}\) for all \(i,j \in V\) and \(p_{ij}=0\) if \((i,j) \notin E\). This Markov chain has uniform distribution, the convergence to this distribution is determined by the second largest eigenvalue modulus (SLEM) of the transition probability matrix \(P=\| p_{ij}\| \). The problem of minimizing the SLEM of \(P\) is considered and is expressed as a convex semidefinite problem (SDF). It can be solved either by using standard numerical methods for SDFs for modest \(n\) (say, 1000), or by exploiting various types of symmetry and structure in the problem for larger \(n\), or by using the subgradient method for far larger \(n\) (say, 100,000) offered in the article. The fastest mixing chains are compared to those obtained by using two commonly used heuristics: the maximum degree method and Metropolis-Hastings algorithm. For many examples the fastest mixing chains are faster than those obtained by using heuristics methods. The method for obtaining arbitrary good bounds on the the optimal mixing rate is given. Various extensions of this method are described.
- Is ADMM always faster than average consensus?
- A general selective averaging method for piecewise constant signal and image processing
- Safe Metropolis-Hastings algorithm and its application to swarm control
- Maximum Kolmogorov-Sinai entropy versus minimum mixing time in Markov chains
- Improved mixing rates of directed cycles by added connection
- Randomized leader election
- Characterizing limits and opportunities in speeding up Markov chain mixing
- On stochastic mirror descent with interacting particles: convergence properties and variance reduction
- Eigen-stratified models
- Speeding up Markov chains with deterministic jumps
- The geometric properties of a class of nonsymmetric cones
- Maximizing algebraic connectivity for certain families of graphs
- Cohesive networks using delayed self reinforcement
- On the fastest finite Markov processes
- Fastest mixing reversible Markov chain on friendship graph: trade-off between transition probabilities among friends and convergence rate
- A graph theoretical approach to input design for identification of nonlinear dynamical models
- Variational analysis of the Ky Fan k-norm
- Spectrally optimized pointset configurations
- Bounding fastest mixing
- Communication constraints in the average consensus problem
- A graph-theoretic approach on optimizing informed-node selection in multi-agent tracking control
- 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
- Fast linear iterations for distributed averaging
- Decentralized and privacy-preserving low-rank matrix completion
- Graph diameter, eigenvalues, and minimum-time consensus
- Markov chain approach to probabilistic guidance for swarms of autonomous agents
- Lifting Markov chains to speed up mixing
- On the convergence of decentralized gradient descent
- Rapid mixing and Markov bases
- 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
- Matrix relaxations in combinatorial optimization
- Fastest mixing Markov chain problem for the union of two cliques
- Emergence of balance from a model of social dynamics
- Revisiting EXTRA for Smooth Distributed Optimization
- The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
- Fastest mixing Markov chain on graphs with symmetries
- A MARKOV-PROCESS INSPIRED CA MODEL OF HIGHWAY TRAFFIC
- A framework for decentralised feedback connectivity control with application to sensor networks
- Comparison inequalities and fastest-mixing Markov chains
- Distributed set-valued estimation in sensor networks with limited communication data rate
- Accelerating distributed average consensus by exploring the information of second-order neighbors
- Spectral and graph-theoretic bounds on steady-state-probability estimation performance for an ergodic Markov chain
- scientific article; zbMATH DE number 1097578 (Why is no real title available?)
- Rapidly mixing Markov chains for dismantleable constraint graphs
- Hearing the clusters of a graph: A distributed algorithm
- Linear time average consensus and distributed optimization on fixed graphs
- A semidefinite bound for mixing rates of Markov chains
- scientific article; zbMATH DE number 2151251 (Why is no real title available?)
- A more rapidly mixing Markov chain for graph colorings
- Remarks and open problems on the minimum permanent of acyclic doubly stochastic matrices
- Fastest random walk on a path
- The generalized distance spectrum of a graph and applications
- scientific article; zbMATH DE number 7626753 (Why is no real title available?)
- Efficient projection onto the intersection of a half-space and a box-like set and its generalized Jacobian
- A Spectral Approach to Network Design
- Efficient and reliable overlay networks for decentralized federated learning
- Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
- Recent advances in optimization and game theoretic control for networked systems
- Fast algorithm for singly linearly constrained quadratic programs with box-like constraints
- Random walk centrality for temporal networks
- Faster response in bounded-update-rate, discrete-time linear networks using delayed self-reinforcement
- A distributed ADMM-like method for resource sharing over time-varying networks
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- Combinatorial algorithms for minimizing the maximum Laplacian and signless Laplacian eigenvalues of weighted graphs
- Optimizing the diffusion system based on continuous-time consensus algorithm
- Optimization of steerable sensor network for threat detection
- Randomized Shortest-Path Problems: Two Related Models
- Fastest Mixing Markov Chain on a Path
- Convex optimization of graph Laplacian eigenvalues
- Consensus on simplicial complexes: results on stability and synchronization
- Adaptive online distributed optimization in dynamic environments
- Random Walks, Directed Cycles, and Markov Chains
- scientific article; zbMATH DE number 7651209 (Why is no real title available?)
- A decentralized algorithm for spectral analysis
- A semismooth Newton-CG based dual PPA for matrix spectral norm approximation problems
- Fastest expected time to mixing for a Markov chain on a directed graph
- 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
- Proximal gradient/semismooth Newton methods for projection onto a polyhedron via the duality-gap-active-set strategy
- 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
- Distributed adaptive online learning for convex optimization with weight decay
- Metropolis-Hastings transition kernel couplings
- Assigning stationary distributions to sparse stochastic matrices
- An accelerated decentralized stochastic optimization algorithm with inexact model
- Achieving violation-free distributed optimization under coupling constraints
- Variational analysis of orthogonally invariant norm cones of symmetric matrices
- Cheeger's inequalities for vertex expansion and reweighted eigenvalues
- Decentralized projected Riemannian gradient method for smooth optimization on compact submanifolds embedded in the Euclidean space
- On the convergence analysis of the decentralized projected gradient descent method
- Review of mathematical optimization in federated learning
- Optimizing doubly stochastic matrices for average consensus through swarm and evolutionary algorithms
This page was built for publication: Fastest Mixing Markov Chain on a Graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4652267)
