Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExact solution to the random sequential dynamics of a message passing algorithm
59
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We analyze the random sequential dynamics of a message passing algorithm for Ising models with random interactions in the large system limit. We derive exact results for the two-time correlation functions and the speed of convergence. The {em de Almedia-Thouless} stability criterion of the static problem is found to be necessary and sufficient for the global convergence of the random sequential dynamics.
rate research
Read More
Cascade processes are responsible for many important phenomena in natural and social sciences. Simple models of irreversible dynamics on graphs, in which nodes activate depending on the state of their neighbors, have been successfully applied to describe cascades in a large variety of contexts. Over the last decades, many efforts have been devoted to understand the typical behaviour of the cascades arising from initial conditions extracted at random from some given ensemble. However, the problem of optimizing the trajectory of the system, i.e. of identifying appropriate initial conditions to maximize (or minimize) the final number of active nodes, is still considered to be practically intractable, with the only exception of models that satisfy a sort of diminishing returns property called submodularity. Submodular models can be approximately solved by means of greedy strategies, but by definition they lack cooperative characteristics which are fundamental in many real systems. Here we introduce an efficient algorithm based on statistical physics for the optimization of trajectories in cascade processes on graphs. We show that for a wide class of irreversible dynamics, even in the absence of submodularity, the spread optimization problem can be solved efficiently on large networks. Analytic and algorithmic results on random graphs are complemented by the solution of the spread maximization problem on a real-world network (the Epinions consumer reviews network).
Approximate message passing algorithms proved to be extremely effective in reconstructing sparse signals from a small number of incoherent linear measurements. Extensive numerical experiments further showed that their dynamics is accurately tracked by a simple one-dimensional iteration termed state evolution. In this paper we provide the first rigorous foundation to state evolution. We prove that indeed it holds asymptotically in the large system limit for sensing matrices with independent and identically distributed gaussian entries. While our focus is on message passing algorithms for compressed sensing, the analysis extends beyond this setting, to a general class of algorithms on dense graphs. In this context, state evolution plays the role that density evolution has for sparse graphs. The proof technique is fundamentally different from the standard approach to density evolution, in that it copes with large number of short loops in the underlying factor graph. It relies instead on a conditioning technique recently developed by Erwin Bolthausen in the context of spin glass theory.
We construct and solve a classical percolation model with a phase transition that we argue acts as a proxy for the quantum many-body localisation transition. The classical model is defined on a graph in the Fock space of a disordered, interacting quantum spin chain, using a convenient choice of basis. Edges of the graph represent matrix elements of the spin Hamiltonian between pairs of basis states that are expected to hybridise strongly. At weak disorder, all nodes are connected, forming a single cluster. Many separate clusters appear above a critical disorder strength, each typically having a size that is exponentially large in the number of spins but a vanishing fraction of the Fock-space dimension. We formulate a transfer matrix approach that yields an exact value $ u=2$ for the localisation length exponent, and also use complete enumeration of clusters to study the transition numerically in finite-sized systems.
The Vicsek fractals are one of the most interesting classes of fractals and the study of their structural properties is important. In this paper, the exact formula for the mean geodesic distance of Vicsek fractals is found. The quantity is computed precisely through the recurrence relations derived from the self-similar structure of the fractals considered. The obtained exact solution exhibits that the mean geodesic distance approximately increases as an exponential function of the number of nodes, with the exponent equal to the reciprocal of the fractal dimension. The closed-form solution is confirmed by extensive numerical calculations.
We study random XY and (dimerized) XX spin-1/2 quantum spin chains at their quantum phase transition driven by the anisotropy and dimerization, respectively. Using exact expressions for magnetization, correlation functions and energy gap, obtained by the free fermion technique, the critical and off-critical (Griffiths-McCoy) singularities are related to persistence properties of random walks. In this way we determine exactly the decay exponents for surface and bulk transverse and longitudinal correlations, correlation length exponent and dynamical exponent.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
