The matrix product approximation for the dynamic cavity method
arXiv:1904.03312 · doi:10.1088/1742-5468/ab5701
Abstract
Stochastic dynamics of classical degrees of freedom, defined on vertices of locally tree-like graphs, can be studied in the framework of the dynamic cavity method which is exact for tree graphs. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, and other technical, biological, and social networks. The central objects in the cavity method are edge messages -- conditional probabilities of two vertex variable trajectories. In this paper, we discuss a rather pedagogical derivation for the dynamic cavity method, give a detailed account of the novel matrix product edge message (MPEM) algorithm for the solution of the dynamic cavity equation as introduced in Phys. Rev. E 97, 010104(R) (2018), and present optimizations and extensions. Matrix product approximations of the edge messages are constructed recursively in an iteration over time. Computation costs and precision can be tuned by controlling the matrix dimensions of the MPEM in truncations. Without truncations, the dynamics is exact. Data for Glauber-Ising dynamics shows a linear growth of computation costs in time. In contrast to Monte Carlo simulations, the approach has a much better error scaling. Hence, it gives for example access to low probability events and decaying observables like temporal correlations. We discuss optimized truncation schemes and an extension that allows to capture models which have a continuum time limit.
arXiv comment23 pages, 14 figures; added data showing a linear temporal increase of computation costs for Glauber-Ising dynamics; codes provided at http://www.manyparticle.org/~barthel/mpem; published version
References in corpus (43)
- Statistical physics of social dynamics
- The density-matrix renormalization group in the age of matrix product states
- The density-matrix renormalization group
- The Bethe lattice spin glass revisited
- Matrix product states represent ground states faithfully
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- A class of ansatz wave functions for 1D spin systems and their relation to DMRG
- A message passing approach for general epidemic models
- Inferring the origin of an epidemic with a dynamic message-passing algorithm
- Continuous Matrix Product States for Quantum Fields
- Bayesian inference of epidemics on networks via Belief Propagation
- Entropy and Entanglement in Quantum Ground States
- Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
- An area law for entanglement from exponential decay of correlations
- A message-passing approach for recurrent-state epidemic models on networks
- One-dimensional Continuum Electronic Structure with the Density Matrix Renormalization Group and Its Implications For Density Functional Theory
- Holographic quantum states
- Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
- Dynamic message-passing equations for models with unidirectional dynamics
- Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
- Majority dynamics on trees and the dynamic cavity method
- The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
- Dynamical TAP equations for non-equilibrium Ising spin glasses
- A message-passing approach for threshold models of behavior in networks
- Multigrid Algorithms for Tensor Network States
- Dynamic mean-field and cavity methods for diluted Ising systems
- The zero-patient problem with noisy observations
- Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
- A message-passing scheme for non-equilibrium stationary states
- Inference of kinetic Ising model on sparse graphs
- Relevance of backtracking paths in epidemic spreading on networks
- One-dimensional quantum systems at finite temperatures can be simulated efficiently on classical computers
- A Cavity Master Equation for the continuous time dynamics of discrete spins models
- Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
- Generalized mean field approximation for parallel dynamics of the Ising model
- Variational approximations for stationary states of Ising-like models
- Variational perturbation and extended Plefka approaches to dynamics on random networks: the case of the kinetic Ising model
- A simple analytical description of the non-stationary dynamics in Ising spin systems
- A matrix product algorithm for stochastic dynamics on networks, applied to non-equilibrium Glauber dynamics
- Dynamics of Boolean networks - an exact solution
- Variational approximations for stochastic dynamics on graphs
- Transfer operator analysis of the parallel dynamics of disordered Ising chains
- Phase transitions and memory effects in the dynamics of Boolean networks