Statistical Physics for Communications and Computer Science
| Instructor | Nicolas Macris and Ruediger Urbanke |
| Office | INR 134 |
| Phone | +4121 6938114 |
| nicolas.macris@epfl.ch | |
| Office Hours | By appointment |
Lectures: Wednesdays 15h15 - 17h00, room BC02
Language: English
ECTS Crédits: 4, exam form: project.
Description
The aim of the course is to introduce the student to those fundamental notions of statistical physics which have found applications in communications, signal processing 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, compressed sensing and the random constraint satisfaction problem. 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.
Tentative plan:
Part I: Models.
1. Models and Questions: Codes, Compressive Sensing and Satisfiability.
2. A few notions of statistical physics.
3. Formulation of coding, compressed sensing, satisfiability as spin-glasses.
4. The Curie-Weiss model and phase transitions.
Part II: Message passing algorithms.
5. Marginalization, Sum-Product and Belief Propagation.
6. Coding: belief propagation and density evolution.
7. Interlude: BP to TAP for the Sherrington-Kirkpatrick spin-glass.
8. Compressive sensing: Approximate message passing and state evolution.
9. Random K-sat: BP guided decimation.
Part III: Advanced topics.
10. The Bethe free energy and the replica symmetric formulas.
11. The Maxwell construction.
12. Spatial coupling and nucleation.
13. The cavity method and application to K-sat.
14. Random K-sat: survey propagation guided decimation.
Notes:
We have a set of notes in progress on which we work on. This statphyscom.pdf will be updated weekly to the most recent version.
Weekly Schedule
| Date | Topic | Assignment | Due Date | Remarks | ||
|---|---|---|---|---|---|---|
| Feb 18 | Models and questions | hw1.pdf | always two weeks later | |||
| Feb 25 | no class today | |||||
| March 4 | Stat mech and reformulation of models | hw2.pdf | ||||
| March 11 | Reformulation of coding and compressed sensing | hw3.pdf | ||||
| March 18 | Reformulation - continuation | hw4.pdf | ||||
| March 25 | Marginalization and Belief Propagation | hw5.pdf | ||||
| April 1 | Application to coding, Density Evolution | hw6.pdf | ||||
| April 8 | Easter break: self study the Curie-Weiss model | – | – | |||
| April 15 | SK model: Belief Propagation and Thoules-Anderson-Palmer equations | hw8.pdf | ||||
| April 22 | SK continuation | – | – | |||
| April 29 and May 1 | Compressive sensing: AMP | hw9.pdf | ||||
| May 8 | Compressive sensing: state evolution, Donoho-Tanner phase curve | hw10.pdf | ||||
| May 13 | Bethe free energy and replica solution | project | ||||
| May 20 | no class | project | ||||
| May 27 | Replica solution for the BEC; potential function; Maxwell construction | project | ||||
| Possible final projects | project-1.pdf | project-2.pdf | ||||
Bibliography:
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
| graded homeworks | 30% | for 6 of the weekly assignments |
| final project | 70% | |
| —————————- | ——- | |
| total | 100% |