Message Passing Algorithms for Statistical Estimation and Communication

Abstract

This thesis studies two high-dimensional statistical estimation problems: matrix sketching, and communication over many-user channels. Efficient recovery schemes, based on belief propagation (BP) and Approximate Message Passing (AMP), are developed for these problems. We first consider matrix sketching, where the goal is to recover an n1 x n2 low-rank matrix with k-sparse singular vectors from a small number of linear measurements (sketch). We propose a sketching scheme and an algorithm that can recover the singular vectors with high probability, with sample- and time-complexity both depending only on k and not on the ambient dimensions n1 and n2. Our sketching operator uses a combination of a sparse parity check matrix and a partial DFT matrix. Our main contribution is the design and analysis of a two-stage BP algorithm which recovers the singular vectors by exploiting the simultaneously sparse and low-rank structure of the matrix. We derive a non-asymptotic bound on the probability of exact recovery, which holds for any n1 x n2 sparse, low-rank matrix. We also show how to adapt the scheme to tackle matrices that are approximately sparse and low-rank. The theoretical results are validated by extensive numerical simulations and comparisons with existing schemes that use convex optimization for recovery. We then consider communication over the Gaussian multiple-access channel (GMAC) in a many-user regime where the number of users grows linearly with the code length. Coded CDMA schemes are investigated where each user's information is encoded via a linear code before being modulated with a signature sequence. We propose an efficient AMP decoder that can be tailored to the structure of the linear code, and provide an exact asymptotic characterization of its performance, in terms of the tradeoff between spectral efficiency and signal-to-noise ratio, for a given target error rate. In particular, we consider an AMP decoder which integrates a BP algorithm for decoding the linear code. Simulation results are provided to demonstrate the state-of-the-art performance of the proposed schemes with spatially coupled (SC) signature matrices. Moreover, we consider the same communication problem with random user activity, where the receiver may know some statistics about the number of active users, but does not know the exact number nor the identities of the active users. We illustrate how to extend the CDMA-type schemes to incorporate random user activity, and provide rigorous asymptotic guarantees on the error probabilities. We also derive two sets of new achievability bounds, one finite-length and the other asymptotic, to benchmark the performance of practical schemes. The finite-length bounds are derived through an error-exponent type analysis on Gaussian random codebooks and maximum-likelihood decoding. The asymptotic bounds are based on SC signature matrices and AMP decoding, and derived using suitable replica potential functions. We compare the error performance of the CDMA-type schemes with the achievability bounds.