ECE 590.10: Graphical Models and Inference

Course Information

• Syllabus (updated 01/14/14)
  

• Textbook

  • Course Notes

• Supplemental Materials

  • Modern Coding Theory by Tom Richardson and Rudiger Urbanke (MCT)
    

  • Information, Physics and Computation by Marc Mezard and Andrea Montanari (IPC)
    

  • Information Theory, Inference and Learning Algorithms by David J. C. MacKay (ITILA)
    

  • Error Correction Coding: Mathematical Methods and Algorithms by Todd K. Moon (ECCMMA)
    

  • Probabilistic Graphical Models by Daphne Koller and Nir Friedman (PGM)
    

Lecture Notes, Reading, and Slides

• Lecture Slides: Factor Graphs
  

• Suggested Reading 1: IPC Chap. 1, IPC Chap. 3, MCT Chap. 1, ITILA Chap. 2

• Suggested Reading 2: IPC Chap. 9-9.1, IPC Chap. 10-10.2.2, ITILA Chap. 21

• Suggested Reading 3: IPC Chap. 14-14.2.2, MCT Chap. 2.1-2.5, ITILA Chap. 26

• Lecture Slides: Belief Propagation
  

• Course Notes: Introduction to Coding
  

• Course Notes: Factor Graph Duality
  

• Course Notes: Linear Programming Decoding
  

• Course Notes: Peeling Decoder (handout with exercises)
  

• Course Notes: Density Evolution (handout with exercises)
  

• Course Notes: Bethe Approximation
  

• Course Notes: Compressed Sensing
  

• scribe template

Handouts

• Homework 1
  

• Homework 2
  

• Homework 3
  

• Homework 4
  

• Homework 5
  

• Homework 6
  

• Class Project
  

Other Books, Papers, and Web Resources

Miscellaneous

• EPFL Course on Related Material

• MATLAB Coding Examples (updated 11/06/13)
  

Factor Graphs

• Factor Graphs and the Sum-Product Algorithm by Kschischang, Frey, and Loeliger
  

• The Generalized Distributive Law (a unification of many algorithms by Aji and McEliece)
  

• Partition Functions of Normal Factor Graphs by Forney and Vontobel
  

• Codes on Graphs: Duality and MacWilliams Identities by Forney
  

• On the Uniqueness of Loopy Belief Propagation Fixed Points by Heskes

• Sudoku: An Application of Message Passing by Bauke et al.

Coding Theory

• How to Compute Weight Enumerators of Convolutional Codes (very nice tutorial by McEliece)
  

• Low-Density Parity-Check Codes by Gallager
  

• A Recursive Approach to Low Complexity Codes by Tanner
  

• Efficient Erasure Codes by Luby et al.
  

• The Capacity of Low-Density Parity-Check Codes under Message-Passing Decoding by Richardson and Urbanke
  

• Low density parity check codes with semi-random parity check matrix by Ping, Leung, and Phamdo

• Stopping set distribution of LDPC code ensembles by Orlitsky, Viswanathan, and Zhang (their results are easily generalized to minimum distance)
  

• Pascal Vontobel's site on Pseudocodewords
  

• Spatial Coupling Tutorial
  

• Deterministic Constructions for Large Girth Protograph LDPC Codes by Pradhan, Subramanian, and Thangaraj
  

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels by Arikan
  

• Introduction to Polar Codes by Mori
  

• Systematic Polar Coding by Arikan
  

• Construction and Block Error Rate Analysis of Polar Codes Over AWGN Channel Based on Gaussian Approximation by Wu, Li, and Sun
  

From CDMA to Compressed Sensing (from a graphical models perspective)

• Iterative multiuser joint decoding: unified framework and asymptotic analysis by Boutros and Caire
  

• A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors by Tanaka
  

• A CDMA multiuser detection algorithm on the basis of belief propagation by Kabashima
  

• Analysis of Belief Propagation for Non-Linear Problems: The Example of CDMA (or: How to Prove Tanaka's Formula) by Montanari and Tse
  

• Asymptotic Mean-Square Optimality of Belief Propagation for Sparse Linear Systems by Guo and Wang
  

• A single-letter characterization of optimal noisy compressed sensing by Baron, Guo, and Shamai
  

Compressed Sensing (from a graphical models perspective)

• Compressed Sensing by Donoho
  

• Bayesian Compressive Sensing Via Belief Propagation by Baron, Sarvotham, and Baraniuk
  

• Exploiting Structure in Wavelet-Based Bayesian Compressive Sensing by He and Carin
  

• Message Passing Algorithms for Compressed Sensing by Donoho, Maleki, and Montanari
  

• Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices by Krzakala, Mezard, Sausset, Sun, and Zdeborova

• Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing by Donoho, Javanmard, Montanari
  

• Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior by Som and Schniter
  

K-SAT

• Analytic and algorithmic solution of random satisfiability problems by Mezard, Parisi, and Zecchina

• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation by Montanari, Ricci-Tersenghi, and Semerjian

• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms by Ricci-Tersenghi and Semerjian

Linear Programming Decoding

• Using Linear Programming to Decode Binary linear Codes by Feldman, Karger, and Wainwright
  

• Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes by Vontobel and Koetter
  

• Decomposition Methods for Large Scale LP Decoding by Barman et al.
  

• A Unified Framework for Linear-Programming Based Communication Receivers by Flanagan
  

• An Integer Programming Model for the Sudoku Problem by Bartlett et al.

• Sudoku: Strategy versus Structure by Provan

Martingales

• A recent tutorial on concentration of measure by Raginsky and Sason
  

• A nice introduction to Martingales
  

• Concentration-of-measure inequalities (the first 3 chapters give a very clear introduction)
  

Available Software

• Matlab code for undirected graphical models

• Open source C library for Discrete Approximate Inference in graphical models

• Inference package for undirected graphical models

• LDPC Decoding in Matlab

Note: These packages have not been tested by me. Please give me feedback on their quality if you try them.