Analysis of LM2-NB Decoding

The Matlab script below approximates the solution of the differential equations described in Section III-B of the IEEE Transactions on Information Theory paper, “Analysis of Verification-Based Decoding on the q-ary Symmetric Channel for Large q”, by Fan Zhang and Henry Pfister. It is conjectured (but not known) that these differential equations provide the correct threshold for the LM2NB decoding algorithm. A density evolution approach for the same problem can be found in the IEEE Transactions on Information Theory paper, “Density evolution analysis of node-based verification-based algorithms in compressed sensing”, by Yaser Eftekhari, Anoosheh Heidarzadeh, Amir H. Banihashemi, and Ioannis Lambadaris. There is some numerical evidence that the threshold results given by these two papers differ and that the second paper is more accuracte. Due to the complexity of the formulas in the second paper, this is hard to verify analytically.

Matlab script to analyze LM2-NB

Inference via Message Passing (IMP) for Matrix Completion

The 2010 ISTC paper, “IMP: A message-passing algorithm for matrix completion” by Byung-Hak Kim, Arvind Yedla, and Henry Pfister, describes a two-step approach to matrix completion. The code used to generate Figure 3 is contained here: