Statistical physics for communication and computer science

 

Instructor Nicolas Macris and Ruediger Urbanke
Office INR 134
Phone +4121 6938114
Email 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%  

return to courses main menu