Kalendarium
Thesis defence: Enhancing Iterative Algorithms with Spatial Coupling
Disputation
From:
2024-11-08 09:15
to
13:00
Place: E-house, E:1406.
Contact: mgeni_makambi [dot] mashauri [at] eit [dot] lth [dot] se
Mgeni Makambi Mashauri defends his thesis: Enhancing Iterative Algorithms with Spatial Coupling
Iterative algorithms are becoming more common in modern systems. This ranges from algorithms for communication systems receivers, machine learning, group testing, and various computation problems. The success of these algorithms lies in the ability to simplify computation by breaking down the system into components and exchanging messages on graphs. The graph has the components as nodes and connections between them as edges. This separation is needed since attempting to solve the problem without dividing it into parts results into an optimal solution, the joint maximum a posterior (MAP) solution, but the computational complexity is prohibitive. With the systems divided into separate parts it often seems reasonable to use the best component for each part to achieve good performance. This, however, results into degraded performance compared to the optimal overall solution. To get improved performance the components have to exchange information iteratively in a number of cycles a process known as belief propagation (BP). This principle has been applied with much success in various areas such as the design of turbo codes and low density parity-check (LDPC) codes for reliable communication.
Other examples include iterative receivers for cancelling intersymbol interference (ISI) and better performance of modulation and coding in coded modulation. Choosing component codes for communication systems with iterative systems is often a process which involves compromises. For example, if one chooses a strong code to work with a particular detector, the resulting performance in the waterfall region becomes poor but the error floor is improved whereas choosing a weak code results in improved waterfall region but poor error floor. One can also optimize the code, for example, by tuning the degree distribution of LDPC codes to achieve good performance but the optimization introduces weak components that compromise the error floor. Furthermore, the optimization can work well for a given set of channel conditions, but the optimized code may not work well if the conditions are changed. These problems are a result of the fact that we have limitations from two aspects. First, we are limited by the component (e.g. codes or detectors) choice which sets the limit on the MAP threshold. A strong code will then have a good MAP threshold and good error floor wheres a weak code will have a bad MAP threshold and bad error floor. It is important to note that the MAP threshold is the best we can do with the choice of the components but it can still be away from the ultimate information theoretical limit of the system (this corresponds to the capacity in communication systems for example). A second limitation comes from the decoding algorithm. The BP algorithm is not globally optimal for most graph used, thus setting a limit which is termed the BP threshold. A strong code has then a bad BP threshold whereas a weak code has a better BP threshold. This thesis focuses on improving the performance of iterative algorithms by tackling the limitations highlighted.
We propose improved algorithms and, more importantly, we apply the concept of spatial coupling to improve the performance and robustness of the systems. We do this in two parts. In the first part we apply the concept on channels with ISI showing that we can obtain robust performance with changing channel conditions and changing detector type. We propose three schemes of coupling and compute the BP and MAP thresholds as well as perform finite length simulations. In the second part, we investigate non-adaptive quantitative group testing using sparse graphs. We propose improvements of the algorithms and show that with spatial coupling we can obtain improved and robust performance.
Link to thesis i LU Research Portal:
https://portal.research.lu.se/en/publications/enhancing-iterative-algorithms-with-spatial-coupling