Defence of Yauhen Yakimenka's PhD thesis

On 15 March at 14:15 Yauhen Yakimenka will defend his thesis on „Failure Structures of Message-Passing Algorithms in Erasure Decoding and Compressed Sensing" for obtaining the degree of Doctor of Philosophy in computer science. The event will take place at J. Liivi 2-405.

Yauhen Yakimenka's supervisor is Assoc. Prof. Vitaly Skachek (Institute of Computer Science, UT). Opponents Prof. Jörg Kliewer (New Jersey Institute of Technology, USA) and Prof. Jens Zumbrägel (University of Passau, Germany).

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.

DSpace - https://dspace.ut.ee/handle/10062/63284