We consider communication over the Gaussian multiple-access channel in the regime where the number of users grows linearly with the codelength. We investigate coded CDMA schemes where each user's information is encoded via a linear code before being modulated with a signature sequence. We propose an efficient approximate message passing (AMP) decoder that can be tailored to the structure of the linear code, and provide an exact asymptotic characterization of its performance. Based on this result, we consider a decoder that integrates AMP and belief propagation and characterize the tradeoff between spectral efficiency and signal-to-noise ratio, for a given target error rate. Simulation results are provided to demonstrate the benefits of the concatenated scheme at finite lengths.

We consider the problem of signal estimation in a generalized linear model (GLM). GLMs include many canonical problems in statistical estimation, such as linear regression, phase retrieval, and 1-bit compressed sensing. Recent work has precisely characterized the asymptotic minimum mean-squared error (MMSE) for GLMs with i.i.d. Gaussian sensing matrices. However, in many models there is a significant gap between the MMSE and the performance of the best known feasible estimators. We address this issue by considering GLMs defined via spatially coupled sensing matrices. We propose an efficient approximate message passing (AMP) algorithm for estimation and prove that with a simple choice of spatially coupled design, the MSE of a carefully tuned AMP estimator approaches the asymptotic MMSE as the dimensions of the signal and the observation grow proportionally. To prove the result, we first rigorously characterize the asymptotic performance of AMP for a GLM with a generic spatially coupled design. This characterization is in terms of a deterministic recursion (‘state evolution’) that depends on the parameters defining the spatial coupling. Then, using a simple spatially coupled design and a judicious choice of functions for the AMP algorithm, we analyze the fixed points of the resulting state evolution and show that it achieves the asymptotic MMSE. Numerical results for phase retrieval and rectified linear regression show that spatially coupled designs can yield substantially lower MSE than i.i.d. Gaussian designs at finite dimensions when used with AMP algorithms.

We consider the problem of signal estimation in a generalized linear model (GLM). GLMs cover many canonical problems in statistical estimation including linear regression and phase retrieval. Recent work has precisely characterized the asymptotic minimum mean-squared error (MMSE) for GLMs with i.i.d. Gaussian sensing matrices. However, in many models there is a significant gap between the MMSE and the performance of the best known feasible estimators. In this work we address this gap by considering GLMs defined via spatially coupled sensing matrices. We propose an efficient approximate message passing (AMP) algorithm for estimation and prove that with a simple choice of spatially coupled design, the MSE of a carefully tuned AMP estimator approaches the asymptotic MMSE. Numerical results show that for finite signal dimensions, spatially coupled designs can yield substantially lower MSE than i.i.d. Gaussian designs when used with AMP algorithms.

We study the Gaussian multiple access channel (MAC) in the asymptotic regime where the number of users grows linearly with the codelength. We analyze coding schemes based on random linear models with approximate message passing (AMP) decoding. For fixed target error rate and number of bits per user, we obtain the exact tradeoff between energy-per-bit and the user density achievable in the large system limit. We show that a spatially coupled coding scheme with AMP decoding achieves near-optimal tradeoff for a large range of user densities. We also study the spectral efficiency versus energy-per-bit tradeoff in the regime where the number of bits per user is large.

This paper studies a generalization of sparse superposition codes (SPARCs) for communication over the complex additive white Gaussian noise (AWGN) channel. In a SPARC, the codebook is defined in terms of a design matrix, and each codeword is a generated by multiplying the design matrix with a sparse message vector. In the standard SPARC construction, information is encoded in the locations of the non-zero entries of the message vector. In this paper we generalize the construction and consider modulated SPARCs, where information is encoded in both the locations and the values of the non-zero entries of the message vector. We focus on the case where the non-zero entries take values from a phase-shift keying (PSK) constellation. We propose a computationally efficient approximate message passing (AMP) decoder, and obtain analytical bounds on the state evolution parameters which predict the error performance of the decoder. Using these bounds we show that PSK-modulated SPARCs are asymptotically capacity achieving for the complex AWGN channel, with either spatial coupling or power allocation. We also provide numerical simulation results to demonstrate the error performance at finite code lengths. These results show that introducing modulation to the SPARC design can significantly reduce decoding complexity without sacrificing error performance.

Sparse superposition codes, also referred to as sparse regression codes (SPARCs), are a class of codes for efficient communication over the AWGN channel at rates approaching the channel capacity. In a standard SPARC, codewords are sparse linear combinations of columns of an i.i.d. Gaussian design matrix, while in a spatially coupled SPARC the design matrix has a block-wise structure, where the variance of the Gaussian entries can be varied across blocks. A well-designed spatial coupling structure can significantly enhance the error performance of iterative decoding algorithms such as Approximate Message Passing (AMP). In this paper, we obtain a non-asymptotic bound on the probability of error of spatially coupled SPARCs with AMP decoding. Applying this bound to a simple band-diagonal design matrix, we prove that spatially coupled SPARCs with AMP decoding achieve the capacity of the AWGN channel. The bound also highlights how the decay of error probability depends on each design parameter of the spatially coupled SPARC. An attractive feature of AMP decoding is that its asymptotic mean squared error (MSE) can be predicted via a deterministic recursion called state evolution. Our result provides the first proof that the MSE concentrates on the state evolution prediction for spatially coupled designs. Combined with the state evolution prediction, this result implies that spatially coupled SPARCs with the proposed band-diagonal design are capacity-achieving. Using the proof technique used to establish the main result, we also obtain a concentration inequality for the MSE of AMP applied to compressed sensing with spatially coupled design matrices. Finally, we provide numerical simulation results that demonstrate the finite length error performance of spatially coupled SPARCs. The performance is compared with coded modulation schemes that use LDPC codes from the DVB-S2 standard.

We study a generalization of sparse regression codes (SPARCs) for communication over the complex AWGN channel. In a SPARC, the codebook is defined in terms of a design matrix, and each codeword is a generated by multiplying the design matrix with a sparse message vector. In the standard SPARC construction, information is encoded in the locations of the nonzero entries of the message vector. In this paper we generalize the construction and consider modulated SPARCs, where information is encoded in both the locations and the values of the non-zero entries of the message vector. We focus on the case where the non-zero entries take values from a Phase Shift Keying (PSK) constellation. We propose a computationally efficient Approximate Message Passing (AMP) decoder, and obtain analytical bounds on the state evolution parameters which predict the error performance of the AMP decoder. Using these bounds, we show that PSK-modulated SPARCs are asymptotically capacity achieving for the complex AWGN channel. We also provide numerical simulation results to demonstrate the error performance at finite code lengths. These results show that introducing modulation to the SPARC design can significantly reduce decoding complexity without sacrificing error performance.

We analyze the performance of spatially coupled sparse regression codes (SC-SPARCs) over the AWGN channel with a sliding window approximate message passing (AMP) decoder. In an SC-SPARC, the codewords are sparse linear combinations of columns of a Gaussian matrix that has a block-wise band-diagonal structure. In this paper we introduce and motivate the sliding-window AMP decoder for SC-SPARCs, and present the first steps towards a fully rigorous proof that the SC-SPARCs with sliding window AMP decoding are asymptotically capacity-achieving. We also provide numerical simulation results demonstrating the error performance of the sliding window AMP decoder at finite code lengths.

We consider the design and analysis of spatially coupled sparse regression codes (SC-SPARCs), which were recently introduced by Barbier et al. for efficient communication over the additive white Gaussian noise channel. SC-SPARCs can be efficiently decoded using an Approximate Message Passing (AMP) decoder, whose performance in each iteration can be predicted via a set of equations called state evolution. In this paper, we give an asymptotic characterization of the state evolution equations for SC-SPARCs. For any given base matrix (that defines the coupling structure of the SC-SPARC) and rate, this characterization can be used to predict whether AMP decoding will succeed in the large system limit. We then consider a simple base matrix defined by two parameters (ω, Λ), and show that AMP decoding succeeds in the large system limit for all rates . The asymptotic result also indicates how the parameters of the base matrix affect the decoding progression. Simulation results are presented to evaluate the performance of SC-SPARCs defined with the proposed base matrix.

Sparse regression codes (SPARCs) are a recent coding technique for the AWGN channel where the codewords are linear combinations of columns of a design matrix. In a spatially coupled sparse regression code (SC-SPARC), the design matrix has a block-wise band-diagonal structure. SC-SPARCs can be decoded using an efficient Approximate Message Passing (AMP) decoder, whose performance can be predicted using a recursion known as state evolution. In this work, we obtain non-asymptotic bounds for the state evolution parameters. These bounds are used to describe the decoding progression in terms of the code parameters and the gap from capacity.