Lectures: Wednesdays 13h15 – 15h00, room INF213
ECTS Crédits: 4, exam form: project.
The aim of the course is to introduce the student to those fundamental notions of statistical physics which have found applications in communications and computer science. The course will focus on systems which can be described by means of an underlying graphical model. These include in particular modern coding systems, the random constraint satisfaction problem and compressed sensing. We will be interested in the behavior of such systems in the infinite size limit. In particular, we focus on the emergence of phase transitions, how they can be analyzed, and how they relate to the behavior of efficient algorithms.
The students may choose to study more deeply one or the other of the topics discussed in class, as well as recent research directions, through a term project.
1. Models and Questions: Codes, Satisfiability, and Compressive Sensing.
2. Notions of statistical physics: free energy, phase transitions, pure states.
3. Exactly solvable models – the Curie-Weiss model and Ising on a tree.
4. Statistical mechanical formulation of coding, K-sat and compressed sensing.
5. Marginalization, Sum-Product and Belief Propagation.
6. Application to LDPC codes.
7. Density evolution analysis. Maxwell construction and conjecture.
8. Approximate Message Passing for compressed sensing.
9. State evolution analysis of AMP.
10. Random K-sat: Unit Clause Propagation and Wormald’s method.
11. Belief Propagation guided decimation for K-sat.
12. Variational formulation of Belief Propagation: the Bethe free energy.
13. The cavity method. Dynamical, condensation and sat-unsat phase transitions.
14. The phase diagram of K-sat. Survey Propagation guided decimation.
This course was taught for the first time in 2010/11. We have a sparse set of notes which you can find here. We will expand them during this semester and statphys.pdf is always the latest version.
||models and questions
||stat mech principles —-
||reformulation of models –
||Curie Weiss model ——
||marginalization and BP-
||coding: Belief Propagation
||Easter break (Mar29 – Apr7)
||coding: Density Evolution
||SK model: from BP to TAP
||Compressive sensing: from BP to AMP
||Compressive sensing: State evolution
||Random K SAT: Wormald method
||Variational methods: Bethe and replica symmetric energies/entropies
Statistical Physics of Spin Glasses and Information Processing, by H. Nishimori, Oxford University Press, (2001).
Information Theory, Inference and Algorithms, by D. J. C. MacKay, Cambridge University Press (2003).
New Optimization Algorithms in Physics, Edited by A. K. Hartmann and H. Rieger, Wiley (2004).
Modern Coding Theory, by T. Richardson and R. Urbanke, Cambridge University Press, (2008).\ Information, Physics and Computation, by M. Mezard and A. Montanari, Oxford Graduate Texts, (2009).
Exams and Grading