Statistical physics for communication and computer science

Instructor Nicolas Macris and Ruediger Urbanke
Office INR 134
Phone +4121 6938114
Email [email protected] and [email protected]
Office Hours By appointment

Lectures: Wednesdays 12h15 – 14h00, room BC02

Language: English

ECTS Credits: 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-2017.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%

return to courses main menu