Summary of the Thesis:

 

The presented results are from two different—on the face of it—fields, message-passing channel decoding and compressed sensing. Channel decoding deals with reliable transmission of information. In our case, we consider the binary erasure channel (BEC). This means that a bit one sends is received either unchanged or erased completely.  A fundamental result by Shannon was as follows: whatever bad channel you have, there is always a way to send information reliably (i.e. with vanishing probability of error) if you encode large enough blocks of information together. One of the most popular algorithms used for decoding nowadays is message-passing, which is fast but not optimal, i.e. sometimes it fails while the reconstruction is still possible with a more sophisticated method. In this thesis, we try to build a bridge between these two methods. Another aforementioned problem, compressed sensing, is based on the following observation. Many important signals can be represented as sparse vectors, i.e. vectors with many zeroes. It was suggested to compress such signals on-the-fly, by implicitly multiplying them by a measurement matrix. We consider one of the suboptimal algorithms, the interval-passing algorithm. More precisely, we ask a question on what are the conditions for the algorithm to fail. We were able to give a complete graph-theoretic criterion of reconstruction success. We considered failures of both message-passing decoding and the interval-passing algorithm for compressed sensing. This allowed us to unveil many similarities and how one can translate the research tools between the algorithms.