Alexandre Graell i Amat
Department of Electrical Engineering
Chalmers University of Technology
SE-412 96 Gothenburg, Sweden
Email: alexandre dot graell at chalmers dot se
Phone: +46 31772 1753
Adjunct Research Scientist
N-5008 Bergen, Norway
05/23: PhD position on the Theory for the Privacy-Security Trade-off in Federated Learning
We are looking for a talented and motivated Ph.D. candidate in the area of privacy-preserving federated learning. This position is funded by theWallenberg AI, autonomous systems, and software program (WASP), a major national initiative for strategic basic research, education, and faculty recruitment in artificial intelligence, and the largest individual research program in Sweden. More information can be found here
03/23: Paper on finite-length scaling of SC-LDPC codes in the IEEE Transactions on Information Theory
Our paper "Finite-Length Scaling of SC-LDPC Codes With a Limited Number of Decoding Iterations" has been accepted for publication in the IEEE Transactions on Information Theory.
Abstract: We propose four finite-length scaling laws to predict the frame error rate (FER) performance in the waterfall region of spatially-coupled low-density parity-check code ensembles under full belief propagation (BP) decoding with a limit on the number of decoding iterations and a scaling law for sliding window decoding, also with limited iterations. The laws for full BP decoding provide a choice between accuracy and computational complexity; a good balance between them is achieved by the law that models the number of decoded bits after a certain number of BP iterations by a time-integrated Ornstein-Uhlenbeck process. This framework is developed further to model sliding window decoding as a race between the integrated Ornstein-Uhlenbeck process and an absorbing barrier that corresponds to the left boundary of the sliding window. The proposed scaling laws yield accurate FER predictions for the semi-structured code ensembles proposed by Olmos and Urbanke. Check our paper in [IEEEXplore]
03/23: Two papers on coding for DNA storage at the IEEE Information Theory Workshop (ITW), Saint Malo, France
Our following two papers have been accepted for presentation at ITW 2023:
I. Maarouf, E. Rosnes, and A. Graell i Amat, "Achievable Information Rates and Concatenated Codes for the DNA Nanopore Sequencing Channel"
Abstract: The errors occurring in DNA-based storage are correlated in nature, which is a direct consequence of the synthesis and sequencing processes. In this paper, we consider the memory-k nanopore channel model recently introduced by Hamoum et al., which models the inherent memory of the channel. We derive the maximum a posteriori (MAP) decoder for this channel model. The derived MAP decoder allows us to compute achievable information rates for the true DNA storage channel assuming a mismatched decoder matched to the memory-k nanopore channel model, and quantify the loss in performance assuming a small memory length--and hence limited decoding complexity. Furthermore, the derived MAP decoder can be used to design error-correcting codes tailored to the DNA storage channel. We show that a concatenated coding scheme with an outer low-density parity-check code and an inner convolutional code yields excellent performance.
Check our paper in [arXiv]
L. Welter, I. Maarouf, A. Lenz, A. Wacther-Zeh, E. Rosnes, and A. Graell i Amat, "Index-Based Concatenated Codes for the Multi-Draw DNA Storage Channel"
Abstract: We consider error-correcting coding for DNA-based storage. We model the DNA storage channel as a multi-draw IDS channel where the input data is chunked into M short DNA strands, which are copied a random number of times, and the channel outputs a random selection of N noisy DNA strands. The retrieved DNA strands are prone to insertion, deletion, and substitution (IDS) errors. We propose an index-based concatenated coding scheme consisting of the concatenation of an outer code, an index code, and an inner synchronization code, where the latter two tackle IDS errors. We further propose a mismatched joint index-synchronization code maximum a posteriori probability decoder with optional clustering to infer symbolwise a posteriori probabilities for the outer decoder. We compute achievable information rates for the outer code and present Monte-Carlo simulations on experimental data.
Check our paper in [arXiv]
02/23: Paper on unsourced multiple access in the IEEE Transactions on Information Theory
Our paper "Unsourced Multiple Access With Random User Activity" has been accepted for publication in the IEEE Transactions on Information Theory.
Abstract: To account for the massive uncoordinated random access scenario, which is relevant for the Internet of Things, Polyanskiy (2017) proposed a novel formulation of the multiple-access problem, commonly referred to as unsourced multiple access, where all users employ a common codebook and the receiver decodes up to a permutation of the messages. We extend this seminal work to the case where the number of active users is random and unknown a priori. We define a random-access code accounting for both misdetection (MD) and false alarm (FA), and derive a random-coding achievability bound for the Gaussian multiple access channel. Our bound captures the fundamental trade-off between MD and FA. It suggests that the lack of knowledge of the number of active users entails a small penalty in energy efficiency when the target MD and FA probabilities are high. However, as the target MD and FA probabilities decrease, the energy efficiency penalty becomes significant. For example, in a typical IoT scenario, the required energy per bit to achieve both MD and FA probabilities below 0.1, predicted by our bound, is only 0.5-0.7 dB higher than that predicted by the bound in Polyanskiy (2017) for a known number of active users. This gap increases to 3-4 dB when the target MD and/or FA probability is 0.001. Taking both MD and FA into account, we use our bound to benchmark the energy efficiency of slotted ALOHA with multi-packet reception, of a decoder that treats interference as noise, and of some recently proposed coding schemes. Numerical results suggest that, when the target MD and FA probabilities are high, it is effective to estimate the number of active users, then treat this estimate as the true value, and use a coding scheme that performs well for the case of known number of active users. However, this approach becomes energy inefficient when the requirements on MD and FA probabilities are stringent.
Check our paper in [arXiv][IEEEXplore]
01/23: Paper on coded federated learning in the IEEE Transactions on Communications
Our paper "CodedPaddedFL and CodedSecAgg: Straggler Mitigation and Secure Aggregation in Federated Learning" has been accepted for publication in the IEEE Transactions on Communications.
Abstract: We present two novel federated learning (FL) schemes that mitigate the effect of straggling devices by introducing redundancy on the devices’ data across the network. Compared to other schemes in the literature, which deal with stragglers or device dropouts by ignoring their contribution, the proposed schemes do not suffer from the client drift problem. The first scheme, CodedPaddedFL, mitigates the effect of stragglers while retaining the privacy level of conventional FL. It combines one-time padding for user data privacy with gradient codes to yield straggler resiliency. The second scheme, CodedSecAgg, provides straggler resiliency and robustness against model inversion attacks and is based on Shamir's secret sharing. We apply CodedPaddedFL and CodedSecAgg to a classification problem. For a scenario with 120 devices, CodedPaddedFL achieves a speed-up factor of 18 for an accuracy of 95% on the MNIST dataset compared to conventional FL. Furthermore, it yields similar performance in terms of latency compared to a recently proposed scheme by Prakash et al. without the shortcoming of additional leakage of private data. CodedSecAgg outperforms the state-of-the-art secure aggregation scheme LightSecAgg by a speed-up factor of 6.6-18.7 for the MNIST dataset for an accuracy of 95%. Check our paper in [IEEEXplore]
01/23: Two papers accepted at the IEEE International Conference on Communications (ICC), Rome, Italy
Our following two papers have been accepted for presentation at ICC 2023:
K.-H. Ngo, A. Graell i Amat, and G. Durisi, "Irregular Repetition Slotted ALOHA Over the Binary Adder Channel"
Abstract: We propose an irregular repetition slotted ALOHA (IRSA) based random-access protocol for the binary adder channel (BAC). The BAC captures important physical-layer concepts, such as packet generation, per-slot decoding, and information rate, which are neglected in the commonly considered collision channel model. We divide a frame into slots and let users generate a packet, to be transmitted over a slot, from a codebook. In a state-of-the-art scheme proposed by Paolini et al. (2022), the codebook is constructed as the parity-check matrix of a BCH code. Here, we construct the codebook from independent and identically distributed binary symbols to obtain a random-coding achievability bound. Our per-slot decoder progressively discards incompatible codewords from a list of candidate codewords, and can be improved by shrinking these candidate lists across iterations. In a regime of practical interests, our scheme can resolve more colliding users in a slot and thus achieves a higher average sum rate than the scheme in Paolini et al. (2022).
V. Ninkovic, D. Vukobratovic, C. Häger, H. Wymeeersch, and A. Graell i Amat, "Rateless Autoencoder Codes: Trading off Decoding Delay and Reliability"
Abstract: Most of today’s communication systems are designed to target reliable message recovery after receiving the entire encoded message (codeword). However, in many practical scenarios, the transmission process may be interrupted before receiving the complete codeword. This paper proposes a novel rateless
autoencoder (AE)-based code design suitable for decoding the transmitted message before the noisy codeword is fully received. Using particular dropout strategies applied during the training process, rateless AE codes allow to trade off between decoding delay and reliability, providing a graceful improvement of the latter with each additionally received codeword symbol. The proposed rateless AEs significantly outperform the conventional AE designs for scenarios where it is desirable to trade off reliability for lower decoding delay.
10/22: Postdoc position in my group on secure and private federated learning
I'm looking for an exceptional candidate with strong mathematical skills to work on the theory and design of novel secure and private federated learning schemes. Click here for more information and to apply. The review of applications will begin on November 15, 2022, and the application portal will be closed on December 5, 2022.
09/22: Paper in the IEEE Transactions on Information Theory
Our paper "Concatenated Codes for Multiple Reads of a DNA Sequence" has been accepted for publication in the IEEE Transactions on Information Theory.
Abstract: Decoding sequences that stem from multiple transmissions of a codeword over an insertion, deletion, and substitution channel is a critical component of efficient deoxyribonucleic acid (DNA) data storage systems. In this paper, we consider a concatenated coding scheme with an outer nonbinary low-density parity-check code or a polar code and either an inner convolutional code or a time-varying block code. We propose two novel decoding algorithms for inference from multiple received sequences, both combining the inner code and channel to a joint hidden Markov model to infer symbolwise a posteriori probabilities (APPs). The first decoder computes the exact APPs by jointly decoding the received sequences, whereas the second decoder approximates the APPs by combining the results of separately decoded received sequences and has a complexity that is linear with the number of sequences. Using the proposed algorithms, we evaluate the performance of decoding multiple received sequences by means of achievable information rates and Monte-Carlo simulations. We show significant performance gains compared to a single received sequence. In addition, we succeed in improving the performance of the aforementioned coding scheme by optimizing both the inner and outer codes.
Check our paper in [arXiv][IEEEXplore]
09/22: Paper in the IEEE Transactions on Information Theory
Our paper "Successive Cancellation Decoding of Single Parity-Check Product Codes: Analysis and Improved Decoding" has been accepted for publication in the IEEE Transactions on Communications.
Abstract: A product code with single parity-check component codes can be described via the tools of a multi-kernel polar code, where the rows of the generator matrix are chosen according to the constraints imposed by the product code construction. Following this observation, successive cancellation decoding of such codes is introduced. In particular, the error probability of single parity-check product codes over binary memoryless symmetric channels under successive cancellation decoding is characterized. A bridge with the analysis of product codes introduced by Elias is also established for the binary erasure channel. Successive cancellation list decoding of single parity-check product codes is then described. For the provided example, simulations over the binary input additive white Gaussian channel show that successive cancellation list decoding outperforms belief propagation decoding applied to the code graph. Finally, the performance of the concatenation of a product code with a high-rate outer code is investigated via distance spectrum analysis. Examples of concatenations performing within 0.7 dB from the random coding union bound are provided.
09/22: Paper in the IEEE Transactions on Communications
Our paper "Generalized Spatially-Coupled Parallel Concatenated Codes With Partial Repetition" has been accepted for publication in the IEEE Transactions on Communications.
Abstract: A new class of spatially-coupled turbo-like codes (SC-TCs), dubbed generalized spatially coupled parallel concatenated codes (GSC-PCCs), is introduced. These codes are constructed by applying spatial coupling on parallel concatenated codes (PCCs) with a fraction of information bits repeated q times. GSC-PCCs can be seen as a generalization of the original spatially-coupled parallel concatenated codes proposed by Moloudi et al. . To characterize the asymptotic performance of GSC-PCCs, we derive the corresponding density evolution equations and compute their decoding thresholds. The threshold saturation effect is observed and proven. Most importantly, we rigorously prove that the rate-R GSC-PCC ensemble with 2-state convolutional component codes achieves at least a fraction 1-R/R+q of the capacity of the binary erasure channel (BEC) for repetition factor q ≥ 2 and this multiplicative gap vanishes as q tends to infinity. To the best of our knowledge, this is the first class of SC-TCs that are proven to be capacity-achieving. Further, the connection between the strength of the component codes, the decoding thresholds of GSC-PCCs, and the repetition factor is established. The superiority of the proposed codes with finite blocklength is exemplified by comparing their error performance with that of existing SC-TCs via computer simulations.
Check our paper in [IEEEXplore]
05/22: Ph.D. position in decentralized learning available in my group!
I am looking for a Ph.D. student in edge computing and decentralized learning. If you are interested, apply at the following link:
05/22: Four papers at IEEE International Conference on Communications (ICC), Seoul, Korea
We will present the following papers this week at ICC 2022:
Coding for Straggler Mitigation in Federated Learning [arXiv, extended version]
Error Floor Analysis of Irregular Repetition ALOHA [arXiv]
Robust Performance Over Changing Intersymbol Interference Channels by Spatial Coupling [arXiv]
Symbol-Based Over-the-Air Digital Predistortion Using Reinforcement Learning [arXiv]