Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStatistical physics of inference: Thresholds and algorithms
97
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Many questions of fundamental interest in todays science can be formulated as inference problems: Some partial, or noisy, observations are performed over a set of variables and the goal is to recover, or infer, the values of the variables based on the indirect information contained in the measurements. For such problems, the central scientific questions are: Under what conditions is the information contained in the measurements sufficient for a satisfactory inference to be possible? What are the most efficient algorithms for this task? A growing body of work has shown that often we can understand and locate these fundamental barriers by thinking of them as phase transitions in the sense of statistical physics. Moreover, it turned out that we can use the gained physical insight to develop new promising algorithms. Connection between inference and statistical physics is currently witnessing an impressive renaissance and we review here the current state-of-the-art, with a pedagogical focus on the Ising model which formulated as an inference problem we call the planted spin glass. In terms of applications we review two classes of problems: (i) inference of clusters on graphs and networks, with community detection as a special case and (ii) estimating a signal from its noisy linear measurements, with compressed sensing as a case of sparse estimation. Our goal is to provide a pedagogical review for researchers in physics and other fields interested in this fascinating topic.
rate research
Read More
We review recent works on analyzing the dynamics of gradient-based algorithms in a prototypical statistical inference problem. Using methods and insights from the physics of glassy systems, these works showed how to understand quantitatively and qualitatively the performance of gradient-based algorithms. Here we review the key results and their interpretation in non-technical terms accessible to a wide audience of physicists in the context of related works.
Optimization is fundamental in many areas of science, from computer science and information theory to engineering and statistical physics, as well as to biology or social sciences. It typically involves a large number of variables and a cost function depending on these variables. Optimization problems in the NP-complete class are particularly difficult, it is believed that the number of operations required to minimize the cost function is in the most difficult cases exponential in the system size. However, even in an NP-complete problem the practically arising instances might, in fact, be easy to solve. The principal question we address in this thesis is: How to recognize if an NP-complete constraint satisfaction problem is typically hard and what are the main reasons for this? We adopt approaches from the statistical physics of disordered systems, in particular the cavity method developed originally to describe glassy systems. We describe new properties of the space of solutions in two of the most studied constraint satisfaction problems - random satisfiability and random graph coloring. We suggest a relation between the existence of the so-called frozen variables and the algorithmic hardness of a problem. Based on these insights, we introduce a new class of problems which we named locked constraint satisfaction, where the statistical description is easily solvable, but from the algorithmic point of view they are even more challenging than the canonical satisfiability.
In the so-called microscopic models of vehicular traffic, attention is paid explicitly to each individual vehicle each of which is represented by a particle; the nature of the interactions among these particles is determined by the way the vehicles influence each others movement. Therefore, vehicular traffic, modeled as a system of interacting particles driven far from equilibrium, offers the possibility to study various fundamental aspects of truly nonequilibrium systems which are of current interest in statistical physics. Analytical as well as numerical techniques of statistical physics are being used to study these models to understand rich variety of physical phenomena exhibited by vehicular traffic. Some of these phenomena, observed in vehicular traffic under different circumstances, include transitions from one dynamical phase to another, criticality and self-organized criticality, metastability and hysteresis, phase-segregation, etc. In this critical review, written from the perspective of statistical physics, we explain the guiding principles behind all the main theoretical approaches. But we present detailed discussions on the results obtained mainly from the so-called particle-hopping models, particularly emphasizing those which have been formulated in recent years using the language of cellular automata.
In statistical physics, the challenging combinatorial enumeration of the configurations of a system subject to hard constraints (microcanonical ensemble) is mapped to a mathematically easier calculation where the constraints are softened (canonical ensemble). However, the mapping is exact only when the size of the system is infinite and if the property of ensemble equivalence (EE), i.e. the asymptotic identity of canonical and microcanonical large deviations, holds. For finite systems, or when EE breaks down, statistical physics is currently believed to provide no answer to the combinatorial problem. In contrast with this expectation, here we establish exact relationships connecting conjugate ensembles in full generality, even for finite system size and when EE does not hold. We also show that in the thermodynamic limit the ensembles are directly related through the matrix of canonical (co)variances of the constraints, plus a correction term that survives only if this matrix has an infinite number of finite eigenvalues. These new relationships restore the possibility of enumerating microcanonical configurations via canonical probabilities, thus reconnecting statistical physics and combinatorics in realms where they were believed to be no longer in mutual correspondence.
These notes provide a concise introduction to important applications of the renormalization group (RG) in statistical physics. After reviewing the scaling approach and Ginzburg-Landau theory for critical phenomena, Wilsons momentum shell RG method is presented, and the critical exponents for the scalar Phi^4 model are determined to first order in an eps expansion about d_c = 4. Subsequently, the technically more versatile field-theoretic formulation of the perturbational RG for static critical phenomena is described. It is explained how the emergence of scale invariance connects UV divergences to IR singularities, and the RG equation is employed to compute the critical exponents for the O(n)-symmetric Landau-Ginzburg-Wilson theory. The second part is devoted to field theory representations of non-linear stochastic dynamical systems, and the application of RG tools to critical dynamics. Dynamic critical phenomena in systems near equilibrium are efficiently captured through Langevin equations, and their mapping onto the Janssen-De Dominicis response functional, exemplified by the purely relaxational models with non-conserved (model A) / conserved order parameter (model B). The Langevin description and scaling exponents for isotropic ferromagnets (model J) and for driven diffusive non-equilibrium systems are also discussed. Finally, an outlook is presented to scale-invariant phenomena and non-equilibrium phase transitions in interacting particle systems. It is shown how the stochastic master equation associated with chemical reactions or population dynamics models can be mapped onto imaginary-time, non-Hermitian `quantum mechanics. In the continuum limit, this Doi-Peliti Hamiltonian is represented through a coherent-state path integral, which allows an RG analysis of diffusion-limited annihilation processes and phase transitions from active to inactive, absorbing states.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
