ECE 590.17: Factor Graphs and Machine Learning

Course Information

• Syllabus (updated 11/07/25)
  

  • Lecture: 1:25 - 2:40 MW @ Gross Hall 318
    

• Textbook

  • Course Notes

• Supplemental Materials

  • Graphical Models, Exponential Families, and Variational Inference by Wainwright and Jordan

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

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

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

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

Lecture Notes and Reading

• Lecture 1: History of Graphical Models & Inference

• Lecture 2: Probability and Information Measures

• Lecture 3: Introduction to Factor Graphs

Slides

• Lecture 1 Slides: History of Graphical Models & Inference

• Factor Graphs
  

• Belief Propagation
  

Handouts

• Homework 0 (not graded)
  

Other Books, Papers, and Web Resources

Miscellaneous

• EPFL Course on Related Material

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.

• Course Notes: Factor Graph Duality
  

• Course Notes: Bethe Approximation
  

Coding Theory

• Course Notes: Density Evolution (handout with exercises)
  

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

• Low-Density Parity-Check Codes by Gallager
  

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

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

• Course Notes: Linear Programming Decoding
  

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

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

• Sudoku: Strategy versus Structure by Provan

Available Software

• Matlab code for undirected graphical models

• Open source C library for Discrete Approximate Inference in 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.