🗞 Geometric structure and information change in phase transitions
Eun-jin Kim and Rainer Hollerbach
Phys. Rev. E 95, 062107 – Published 6 June 2017
🔗 https://journals.aps.org/pre/abstract/10.1103/PhysRevE.95.062107
📌 ABSTRACT
We propose a toy model for a cyclic order-disorder transition and introduce a geometric methodology to understand stochastic processes involved in transitions. Specifically, our model consists of a pair of forward and backward processes (FPs and BPs) for the emergence and disappearance of a structure in a stochastic environment. We calculate time-dependent probability density functions (PDFs) and the information length L, which is the total number of different states that a system undergoes during the transition. Time-dependent PDFs during transient relaxation exhibit strikingly different behavior in FPs and BPs. In particular, FPs driven by instability undergo the broadening of the PDF with a large increase in fluctuations before the transition to the ordered state accompanied by narrowing the PDF width. During this stage, we identify an interesting geodesic solution accompanied by the self-regulation between the growth and nonlinear damping where the time scale τof information change is constant in time, independent of the strength of the stochastic noise. In comparison, BPs are mainly driven by the macroscopic motion due to the movement of the PDF peak. The total information length L between initial and final states is much larger in BPs than in FPs, increasing linearly with the deviation γ of a control parameter from the critical state in BPs while increasing logarithmically with γ in FPs. L scales as |lnD| and D−1/2 in FPs and BPs, respectively, where D measures the strength of the stochastic forcing. These differing scalings with γ and D suggest a great utility of L in capturing different underlying processes, specifically, diffusion vs advection in phase transition by geometry. We discuss physical origins of these scalings and comment on implications of our results for bistable systems undergoing repeated order-disorder transitions (e.g., fitness).
https://journals.aps.org/pre/abstract/10.1103/PhysRevE.95.062107
Eun-jin Kim and Rainer Hollerbach
Phys. Rev. E 95, 062107 – Published 6 June 2017
🔗 https://journals.aps.org/pre/abstract/10.1103/PhysRevE.95.062107
📌 ABSTRACT
We propose a toy model for a cyclic order-disorder transition and introduce a geometric methodology to understand stochastic processes involved in transitions. Specifically, our model consists of a pair of forward and backward processes (FPs and BPs) for the emergence and disappearance of a structure in a stochastic environment. We calculate time-dependent probability density functions (PDFs) and the information length L, which is the total number of different states that a system undergoes during the transition. Time-dependent PDFs during transient relaxation exhibit strikingly different behavior in FPs and BPs. In particular, FPs driven by instability undergo the broadening of the PDF with a large increase in fluctuations before the transition to the ordered state accompanied by narrowing the PDF width. During this stage, we identify an interesting geodesic solution accompanied by the self-regulation between the growth and nonlinear damping where the time scale τof information change is constant in time, independent of the strength of the stochastic noise. In comparison, BPs are mainly driven by the macroscopic motion due to the movement of the PDF peak. The total information length L between initial and final states is much larger in BPs than in FPs, increasing linearly with the deviation γ of a control parameter from the critical state in BPs while increasing logarithmically with γ in FPs. L scales as |lnD| and D−1/2 in FPs and BPs, respectively, where D measures the strength of the stochastic forcing. These differing scalings with γ and D suggest a great utility of L in capturing different underlying processes, specifically, diffusion vs advection in phase transition by geometry. We discuss physical origins of these scalings and comment on implications of our results for bistable systems undergoing repeated order-disorder transitions (e.g., fitness).
https://journals.aps.org/pre/abstract/10.1103/PhysRevE.95.062107
Physical Review E
Geometric structure and information change in phase transitions
We propose a toy model for a cyclic order-disorder transition and introduce a geometric methodology to understand stochastic processes involved in transitions. Specifically, our model consists of a pair of forward and backward processes (FPs and BPs) for…
🌀The 2017 SIAM Conference on Applications of Dynamical Systems (DS17) was held in Sandy, Utah on May 21st - May 25th, 2017. The SIAM DS conference seeks to enable in-depth technical discussions on a wide variety of major computational efforts on large-scale problems in science and engineering, foster the interdisciplinary culture required to meet these large-scale challenges, and promote the training of the next generation of computational scientists.
Use the search box in the upper right to search for a speaker, talk title, or topic. Select "Content" to see the list of other SIAM meetings with presentations available for viewing.
🔗 https://www.pathlms.com/siam/courses/4812
Use the search box in the upper right to search for a speaker, talk title, or topic. Select "Content" to see the list of other SIAM meetings with presentations available for viewing.
🔗 https://www.pathlms.com/siam/courses/4812
Friends and enemies in the Middle East. Who is connected to whom? - interactive | News | The Guardian
https://www.theguardian.com/news/datablog/ng-interactive/2014/sep/24/friends-and-enemies-in-the-middle-east-who-is-connected-to-who-interactive
https://www.theguardian.com/news/datablog/ng-interactive/2014/sep/24/friends-and-enemies-in-the-middle-east-who-is-connected-to-who-interactive
the Guardian
Friends and enemies in the Middle East. Who is connected to whom? - interactive
As the US and UK are set to again commit to military involvement in the Middle East, this interactive visualises the intricate, complex and sometimes hidden relationships and alliances across the region
🔥 Gall's Law: "A complex system that works is invariably found to have evolved from a simple system that worked."
– John Gall (1975)
– John Gall (1975)
Tutorials are short, self-paced “mini-courses” designed to introduce students to important techniques and to provide illustrations of their application in complex systems.
https://www.complexityexplorer.org/tutorials
https://www.complexityexplorer.org/tutorials
On some deep connections between computer science, statistical physics and information theory:
http://lptms.u-psud.fr/membres/mezard/edwards.pdf
http://lptms.u-psud.fr/membres/mezard/edwards.pdf
📄 Kindermann, Ross; Snell, J. Laurie (1980).
🔹 Markov Random Fields and Their Applications 🔹
(PDF): http://www.cmap.polytechnique.fr/~rama/ehess/mrfbook.pdf
🔹 Markov Random Fields and Their Applications 🔹
(PDF): http://www.cmap.polytechnique.fr/~rama/ehess/mrfbook.pdf
🗞 Review:
"Statistical physics of inference: Thresholds and algorithms"
Lenka Zdeborová, Florent Krzakala
(Submitted on 8 Nov 2015 (v1), last revised 28 Jul 2016 (this version, v4))
🔗 https://arxiv.org/pdf/1511.02476
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.
"Statistical physics of inference: Thresholds and algorithms"
Lenka Zdeborová, Florent Krzakala
(Submitted on 8 Nov 2015 (v1), last revised 28 Jul 2016 (this version, v4))
🔗 https://arxiv.org/pdf/1511.02476
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.
🗞 Review:
"Statistical Physics of Hard Optimization Problems"
Lenka Zdeborová - PhD thesis
(Submitted on 25 Jun 2008)
🔗 https://arxiv.org/pdf/0806.4112
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.
"Statistical Physics of Hard Optimization Problems"
Lenka Zdeborová - PhD thesis
(Submitted on 25 Jun 2008)
🔗 https://arxiv.org/pdf/0806.4112
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.
🌀 What physics can tell us about inference ?
Cristopher Moore, Santa Fe Institute
🎞 http://www.savoirs.ens.fr/expose.php?id=2696
This colloquium is organized around data sciences in a broad sense, with the goal of bringing together researchers with diverse backgrounds (including mathematics, computer science, physics, chemistry and neuroscience) but a common interest in dealing with large scale or high dimensional data.
There is a deep analogy between statistical inference and statistical physics; I will give a friendly introduction to both of these fields. I will then discuss phase transitions in two problems of interest to a broad range of data sciences: community detection in social and biological networks, and clustering of sparse high-dimensional data. In both cases, if our data becomes too sparse or too noisy, it suddenly becomes impossible to find the underlying pattern, or even tell if there is one. Physics both helps us locate these phase transiitons, and design optimal algorithms that succeed all the way up to this point. Along the way, I will visit ideas from computational complexity, random graphs, random matrices, and spin glass theory.
Cristopher Moore, Santa Fe Institute
🎞 http://www.savoirs.ens.fr/expose.php?id=2696
This colloquium is organized around data sciences in a broad sense, with the goal of bringing together researchers with diverse backgrounds (including mathematics, computer science, physics, chemistry and neuroscience) but a common interest in dealing with large scale or high dimensional data.
There is a deep analogy between statistical inference and statistical physics; I will give a friendly introduction to both of these fields. I will then discuss phase transitions in two problems of interest to a broad range of data sciences: community detection in social and biological networks, and clustering of sparse high-dimensional data. In both cases, if our data becomes too sparse or too noisy, it suddenly becomes impossible to find the underlying pattern, or even tell if there is one. Physics both helps us locate these phase transiitons, and design optimal algorithms that succeed all the way up to this point. Along the way, I will visit ideas from computational complexity, random graphs, random matrices, and spin glass theory.
www.savoirs.ens.fr
Savoirs ENS
Les derniers cours, séminaires, colloques et conférences enregistrées à l'Ecole Normale Supérieure (Paris)