Sparse or dense — Message Passing (MP) or Approximate Message Passing (AMP) for Compressed Sensing signal recovery

Compressed Sensing (CS) is one of the hottest topics in signal processing these days and the design of efficient recovery algorithms is a key research challenge in CS. Whereas, a large number of recovery algorithms have been proposed in literature, the recently proposed Approximate Message Passing (AMP) [19] algorithm has gained a lot of attention because of its good performance and yet simple structure. Although Belief Propagation (BP) algorithms were previously considered to give good performance only in Sparse graphs, AMP algorithm is based on the application of BP on dense graphs. The application of BP in dense graphs asks for a re-look on the design of BP algorithms over graphs which can have a bearing on many applications including coding theory, neural networks etc. This paper aims to compare different existing variants of Message Passing algorithms on sparse and dense graphs for the CS recovery problem.