| Instructor | Nicolas Macris and Ruediger Urbanke |
| Office | INR 134 |
| Phone | +4121 6938114 |
| [email protected] and [email protected] | |
| Office Hours | By appointment |
Lectures: Wednesdays 12h15 – 14h00, 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 statphys.pdf will be updated weekly to the most recent version.
Tentative Weekly Program
| Date | Topic | Assignment | Due Date | Remarks | ||
|---|---|---|---|---|---|---|
| Feb 22 and Feb 29 | Models and questions: coding, compressed sensing, K-sat (chap 1) | hmw1.pdf | always two weeks later | |||
| March 8 | Stat mech basic principles (chap 2) | hmw2.pdf | ||||
| March 15 and 22 | Reformulation of coding and compressed sensing as spin glasses (chap 3) | hmw3.pdf | ||||
| March 29 | Curie-Weiss model: exact solution (chap 4) | hmw4.pdf | ||||
| April 5 | Marginalization, Belief Propagation (chap 5) | hmw5.pdf | ||||
| April 12 | Application to coding and Density evolution (chap 6) | hmw6.pdf | ||||
| April 19 | Easter Break | |||||
| April 26 | BEC: coding and density evolution (chap 6) | |||||
| May 3 | Compressive sensing: AMP algo (chap 8) | hmw7.pdf | ||||
| May 10 | Compressed sensing:state evolution and Donoho-Tanner transition curve (chap 8) | hmw8.pdf | ||||
| May 17 | Bethe free energy (chap 11) | |||||
| May 24 | Replica solution, potential function, Maxwell construction (chap 12) | |||||
| May 31 | Spatial coupling: review (chap 13) | |||||
| Final Project | Binary rank-one matrix factorization | project.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 half of weekly assignments (among your choice) |
| final project | 70% | |
| —————————- | ——- | |
| total | 100% |