We study the Gaussian multiple access channel with random user activity, in the regime where the number of users is proportional to the code length. 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 derive two achievability bounds on the probabilities of missed detection, false alarm, and active user error, and propose an efficient CDMA-type scheme whose performance can be compared against these bounds. The first bound is a finite-length result based on Gaussian random codebooks and maximum-likelihood decoding. The second is an asymptotic bound, established using spatially coupled Gaussian codebooks and approximate message passing (AMP) decoding. These bounds can be used to compute an achievable tradeoff between the active user density and energy-per-bit, for a fixed user payload and target error rate. The efficient CDMA scheme uses a spatially coupled signature matrix and AMP decoding, and we give rigorous asymptotic guarantees on its error performance. Our analysis provides the first state evolution result for spatially coupled AMP with matrix-valued iterates, which may be of independent interest. Numerical experiments demonstrate the promising error performance of the CDMA scheme for both small and large user payloads, when compared with the two achievability bounds.

We consider the problem of localizing change points in a generalized linear model (GLM), a model that covers many widely studied problems in statistical learning including linear, logistic, and rectified linear regression. We propose a novel and computationally efficient approximate message passing (AMP) algorithm for estimating both the signals and the change point locations, and rigorously characterize its performance in the high-dimensional limit where the number of parameters $p$ is proportional to the number of samples $n$. This characterization is in terms of a state evolution recursion, which allows us to precisely compute performance measures such as the asymptotic Hausdorff error of our change point estimates, and allows us to tailor the algorithm to take advantage of any prior structural information of the signals and change points. Moreover, we show how our AMP iterates can be used to efficiently compute a Bayesian posterior distribution over the change point locations in the high-dimensional limit. We validate our theory via numerical experiments, and demonstrate the favorable performance of our estimators on both synthetic and real data in the settings of linear, logistic, and rectified linear regression.

In thepooled dataproblem, the goal is to identify the categories associated with a large collection of items via a sequence of pooled tests. Each pooled test reveals the number of items in the pool belonging to each category. A prominent special case is quantitative group testing (QGT), which is the case of pooled data with two categories. We consider these problems in the non-adaptive and linear regime, where the fraction of items in each category is of constant order. We propose a scheme with aspatially coupledBernoulli test matrix and an efficient approximate message passing (AMP) algorithm for recovery. We rigorously characterize its asymptotic performance in both the noiseless and noisy settings, and prove that in the noiseless case, the AMP algorithm achievesalmost-exactrecovery with a number of tests sublinear in the total number of itemsp. Although there exist other efficient schemes for noiseless QGT and pooled data that achieve recovery with order-optimal sample complexity ((Θ(p/logp) tests, there are no guarantees on their performance in the presence of noise, even at low noise-levels. In comparison, our scheme achieves recovery in the noiseless case with a number of tests sublinear inp, and its performance degrades gracefully in the presence of noise. Numerical simulations illustrate the benefits of the spatially coupled scheme at finite dimensions, showing that it outperforms i.i.d. test designs as well as other recovery algorithms based on convex programming.

We consider the problem of parameter estimation in a high-dimensional generalized linear model. Spectral methods obtained via the principal eigenvector of a suitable data-dependent matrix provide a simple yet surprisingly effective solution. However, despite their wide use, a rigorous performance characterization, as well as a principled way to preprocess the data, are available only for unstructured (i.i.d. Gaussian and Haar orthogonal) designs. In contrast, real-world data matrices are highly structured and exhibit non-trivial correlations. To address the problem, we consider correlated Gaussian designs capturing the anisotropic nature of the features via a covariance matrix $\Sigma$. Our main result is a precise asymptotic characterization of the performance of spectral estimators. This allows us to identify the optimal preprocessing that minimizes the number of samples needed for parameter estimation. Surprisingly, such preprocessing is universal across a broad set of statistical models, which partly addresses a conjecture on optimal spectral estimators for rotationally invariant designs. Our principled approach vastly improves upon previous heuristic methods, including for designs common in computational imaging and genetics. The proposed methodology, based on approximate message passing, is broadly applicable and opens the way to the precise characterization of spiked matrices and of the corresponding spectral methods in a variety of settings.

We consider the problem of localizing change points in high-dimensional linear regression. We propose an Approximate Message Passing (AMP) algorithm for estimating both the signals and the change point locations. Assuming Gaussian covariates, we give an exact asymptotic characterization of its estimation performance in the limit where the number of samples grows proportionally to the signal dimension. Our algorithm can be tailored to exploit any prior information on the signal, noise, and change points. It also enables uncertainty quantification in the form of an efficiently computable approximate posterior distribution, whose asymptotic form we characterize exactly. We validate our theory via numerical experiments, and demonstrate the favorable performance of our estimators on both synthetic data and images.

We study the Gaussian multiple access channel with random user activity, in the regime where the number of users is proportional to the code length. 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 first derive achievability bounds on the error probabilities by analyzing Gaussian random codebooks with maximum-likelihood decoding. We then propose an efficient CDMA-type scheme based on a spatially coupled signature matrix and approximate message passing (AMP) decoding. Rigorous asymptotic guarantees on the error performance of the AMP decoder are derived. A numerical comparison indicates that the asymptotic error guarantees of the spatially coupled scheme are significantly better than those obtained via the finite-length achievability bounds.

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.

In mixed linear regression, each observation comes from one of L regression vectors (signals), but we do not know which one. The goal is to estimate the signals from the unlabeled observations. We propose a novel approximate message passing (AMP) algorithm for estimation and rigorously characterize its performance in the high-dimensional limit. This characterization is in terms of a state evolution recursion, which allows us to precisely compute performance measures such as the asymptotic mean-squared error. This can be used to tailor the AMP algorithm to take advantage of any known structural information about the signals. Using state evolution, we derive an optimal choice of AMP ‘denoising’ functions that minimizes the estimation error in each iteration. Numerical simulations are provided to validate the theoretical results, and show that AMP significantly outperforms other estimators including spectral methods, expectation maximization, and alternating minimization. Though our numerical results focus on mixed linear regression, the proposed AMP algorithm can be applied to a broader class of models including mixtures of generalized linear models and max-affine regression.

We consider the problem of mixed sparse linear regression with two components, where two k-sparse signals β_1, β_2 ∈ R^p are to be recovered from n unlabelled noisy linear measurements. The sparsity is allowed to be sublinear in the dimension (k = o(p)), and the additive noise is assumed to be independent Gaussian with variance σ^2. Prior work has shown that the problem suffers from a k/SNR^2 -to- k^2/SNR^2 statistical-to-computational gap, resembling other computationally challenging high- dimensional inference problems such as Sparse PCA and Robust Sparse Mean Estimation (Brennan and Bresler, 2020b); here SNR := ∥β1∥^2/σ^2 = ∥β2∥^2/σ^2 is the signal-to-noise ratio. We establish the existence of a more extensive k/SNR^2 -to- k^2 (SNR+1)^2/SNR^2 computational barrier for this problem through the method of low-degree polynomials, but show that the problem is computationally hard only in a very narrow symmetric parameter regime. We identify a smooth information-computation tradeoff between the sample complexity n and runtime exp( Θ(k^2(SNR + 1)^2/(nSNR^2))) for any randomized algorithm in this hard regime. Via a simple reduction, this provides novel rigorous evidence for the existence of a computational barrier to solving exact support recovery in sparse phase retrieval with sample complexity n = o(k^2). Our second contribution is to analyze a simple thresholding algorithm which, outside of the narrow regime where the problem is hard, solves the associated mixed regression detection problem in O(np) time and matches the sample complexity required for (non-mixed) sparse linear regression of k(SNR+1)/SNR log p; this allows the recovery problem to be subsequently solved by state-of-the-art techniques from the dense case. As a special case of our results, we show that this simple algorithm is order-optimal among a large family of algorithms in solving exact signed support recovery in sparse linear regression. To the best of our knowledge, this is the first thorough study of the interplay between mixture symmetry, signal sparsity, and their joint impact on the computational hardness of mixed sparse linear regression.

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 problem of regression in a generalized linear model (GLM) with multiple signals and latent variables. This model, which we call a matrix GLM, covers many widely studied problems in statistical learning, including mixed linear regression, max-affine regression, and mixture-of-experts. The goal in all these problems is to estimate the signals, and possibly some of the latent variables, from the observations. We propose a novel approximate message passing (AMP) algorithm for estimation in a matrix GLM and rigorously characterize its performance in the high-dimensional limit. This characterization is in terms of a state evolution recursion, which allows us to precisely compute performance measures such as the asymptotic mean-squared error. The state evolution characterization can be used to tailor the AMP algorithm to take advantage of any structural information known about the signals. Using state evolution, we derive an optimal choice of AMP `denoising' functions that minimizes the estimation error in each iteration. The theoretical results are validated by numerical simulations for mixed linear regression, max-affine regression, and mixture-of-experts. For max-affine regression, we propose an algorithm that combines AMP with expectation-maximization to estimate the intercepts of the model along with the signals. The numerical results show that AMP significantly outperforms other estimators for mixed linear regression and max-affine regression in most parameter regimes.

We consider the problem of recovering an$n_{1} \times n_{2}$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 a sample complexity and running time that both depend only on$k$and not on the ambient dimensions$n_{1}$and$n_{2}$. Our sketching operator, based on a scheme for compressed sensing by Li et al. and Bakshi et al., 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 iterative algorithm which recovers the singular vectors by exploiting the simultaneously sparse and low-rank structure of the matrix. We derive a nonasymptotic bound on the probability of exact recovery, which holds for any$n_{1}\times n_{2} $sparse, low-rank matrix. We also show how the scheme can be adapted 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 consider the problem of signal estimation in generalized linear models defined via rotationally invariant design matrices. Since these matrices can have an arbitrary spectral distribution, this model is well suited for capturing complex correlation structures which often arise in applications. We propose a novel family of approximate message passing (AMP) algorithms for signal estimation, and rigorously characterize their performance in the high-dimensional limit via a state evolution recursion. Our rotationally invariant AMP has complexity of the same order as the existing AMP derived under the restrictive assumption of a Gaussian design; our algorithm also recovers this existing AMP as a special case. Numerical results showcase a performance close to Vector AMP (which is conjectured to be Bayes-optimal in some settings), but obtained with a much lower complexity, as the proposed algorithm does not require a computationally expensive singular value decomposition.

We consider the problem of recovering an n×n 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 a sample complexity and running time that both depend only on k and not on the ambient dimension n. Our sketching operator, based on a scheme for compressed sensing by Li et al. [1] and Bakshi et al. [2], 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 iterative algorithm which recovers the singular vectors by exploiting the simultaneously sparse and low-rank structure of the matrix. We derive a nonasymptotic bound on the probability of exact recovery. The theoretical result is validated by numerical simulations.

We consider the problem of estimating a signal from measurements obtained via a generalized linear model. We focus on estimators based on approximate message passing (AMP), a family of iterative algorithms with many appealing features: the performance of AMP in the high-dimensional limit can be succinctly characterized under suitable model assumptions; AMP can also be tailored to the empirical distribution of the signal entries, and for a wide class of estimation problems, AMP is conjectured to be optimal among all polynomial-time algorithms. However, a major issue of AMP is that in many models (such as phase retrieval), it requires an initialization correlated with the ground-truth signal and independent from the measurement matrix. Assuming that such an initialization is available is typically not realistic. In this paper, we solve this problem by proposing an AMP algorithm initialized with a spectral estimator. With such an initialization, the standard AMP analysis fails since the spectral estimator depends in a complicated way on the design matrix. Our main contribution is a rigorous characterization of the performance of AMP with spectral initialization in the high-dimensional limit. The key technical idea is to define and analyze a two-phase artificial AMP algorithm that first produces the spectral estimator, and then closely approximates the iterates of the true AMP. We also provide numerical results that demonstrate the validity of the proposed approach.

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.

We study the problem of estimating a rank-1 signal in the presence of rotationally invariant noise--a class of perturbations more general than Gaussian noise. Principal Component Analysis (PCA) provides a natural estimator, and sharp results on its performance have been obtained in the high-dimensional regime. Recently, an Approximate Message Passing (AMP) algorithm has been proposed as an alternative estimator with the potential to improve the accuracy of PCA. However, the existing analysis of AMP requires an initialization that is both correlated with the signal and independent of the noise, which is often unrealistic in practice. In this work, we combine the two methods, and propose to initialize AMP with PCA. Our main result is a rigorous asymptotic characterization of the performance of this estimator. Both the AMP algorithm and its analysis differ from those previously derived in the Gaussian setting: at every iteration, our AMP algorithm requires a specific term to account for PCA initialization, while in the Gaussian case, PCA initialization affects only the first iteration of AMP. The proof is based on a two-phase artificial AMP that first approximates the PCA estimator and then mimics the true AMP. Our numerical simulations show an excellent agreement between AMP results and theoretical predictions, and suggest an interesting open direction on achieving Bayes-optimal performance.

Consider two remote nodes (encoder and decoder), each with a binary sequence. The encoder's sequence X differs from the decoder's sequence Y by a small number of edits (deletions and insertions). The goal is to construct a message M, to be sent via a one-way error free link, such that the decoder can reconstruct X using M and Y. In this paper, we devise a coding scheme for this one-way synchronization model. The scheme is based on multiple layers of Varshamov-Tenengolts (VT) codes combined with off-the-shelf linear error-correcting codes, and uses a list decoder. We bound the expected list size of the decoder under certain assumptions, and validate its performance via numerical simulations. We also consider an alternative decoder that uses only the constraints from the VT codes (i.e., does not require a linear code), and has a smaller redundancy at the expense of a slightly larger average list size.

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.

Motivated by the sequence reconstruction problem from traces in DNA-based storage, we consider the problem of designing codes for the deletion channel when multiple observations (or traces) are available to the decoder. We propose simple binary and non-binary codes based on Varshamov-Tenengolts (VT) codes. The proposed codes split the codeword in blocks and employ a VT code in each block. The availability of multiple traces helps the decoder to identify deletion-free copies of a block, and to avoid mis-synchronization while decoding. The encoding complexity of the proposed scheme is linear in the codeword length; the decoding complexity is linear in the codeword length, and quadratic in the number of deletions and the number of traces. The proposed scheme offers an explicit low-complexity technique for correcting deletions using multiple traces.

This paper considers the problem of approximating a Boolean function f using another Boolean function from a specified class. Two classes of approximating functions are considered: k-juntas, and linear Boolean functions. The n input bits of the function are assumed to be independently drawn from a distribution that may be biased. The quality of approximation is measured by the mismatch probability between f and the approximating function g. For each class, the optimal approximation and the associated mismatch probability is characterized in terms of the biased Fourier expansion of f. The technique used to analyze the mismatch probability also yields an expression for the noise sensitivity of f in terms of the biased Fourier coefficients, under a general i.i.d. input perturbation model.

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.

Sparse superposition codes, or sparse regression codes, are a recent class of codes for reliable communication over the AWGN channel at rates approaching the channel capacity. Approximate message passing (AMP) decoding, a computationally efficient technique for decoding SPARCs, has been proven to be asymptotically capacity-achieving for the AWGN channel. In this paper, we refine the asymptotic result by deriving a large deviation bound on the probability of an AMP decoding error. This bound gives insight into the error performance of the AMP decoder for large but finite problem sizes, giving an error exponent as well as guidance on how the code parameters should be chosen at finite block lengths. For an appropriate choice of code parameters, we show that for any fixed rate less than the channel capacity, the decoding error probability decays exponentially in n/(logn)2T, where T, the number of AMP iterations required for successful decoding, is bounded in terms of the gap from capacity.

This paper addresses the problem of efficient encoding of non-binary Varshamov-Tenengolts (VT) codes. We propose a linear-time encoding method to systematically map binary message sequences onto VT codewords. The method provides a new lower bound on the size of q-ary VT codes of length n.

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.

The problem of estimating a high-dimensional sparse vector θ ∈ ℝnfrom an observation in i.i.d. Gaussian noise is considered. An empirical Bayes shrinkage estimator, derived using a Bernoulli-Gaussian prior, is analyzed and compared with the well-known soft-thresholding estimator using squared-error loss as a measure of performance. We obtain concentration inequalities for the Stein's unbiased risk estimate and the loss function of both estimators. Depending on the underlying θ, either the proposed empirical Bayes (eBayes) estimator or soft-thresholding may have smaller loss. We consider a hybrid estimator that attempts to pick the better of the soft-thresholding estimator and the eBayes estimator by comparing their risk estimates. It is shown that: i) the loss of the hybrid estimator concentrates on the minimum of the losses of the two competing estimators, and ii) the risk of the hybrid estimator is within order 1/√n of the minimum of the two risks. Simulation results are provided to support the theoretical results.

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.

Sparse superposition codes are a recent class of codes introduced by Barron and Joseph for efficient communication over the AWGN channel. With an appropriate power allocation, these codes have been shown to be asymptotically capacity-achieving with computationally feasible decoding. However, a direct implementation of the capacity-achieving construction does not give good finite length error performance. In this paper, we consider sparse superposition codes with approximate message passing (AMP) decoding, and describe a variety of techniques to improve their finite length performance. These include an iterative algorithm for SPARC power allocation, guidelines for choosing codebook parameters, and estimating a critical decoding parameter online instead of precomputation. We also show how partial outer codes can be used in conjunction with AMP decoding to obtain a steep waterfall in the error performance curves. We compare the error performance of AMP-decoded sparse superposition codes with coded modulation using LDPC codes from the WiMAX standard.

This paper considers insertion and deletion channels with the additional assumption that the channel input sequence is implicitly divided into segments such that at most one edit can occur within a segment. No segment markers are available in the received sequence. We propose code constructions for the segmented deletion, segmented insertion, and segmented insertion-deletion channels based on subsets of Varshamov- Tenengolts codes chosen with predetermined prefixes and/or suffixes. The proposed codes, constructed for any finite alphabet, are zero error and can be decoded segment by segment. We also derive an upper bound on the rate of any zero-error code for the segmented edit channel, in terms of the segment length. This upper bound shows that the rate scaling of the proposed codes as the segment length increases is the same as that of the maximal code.

Approximate message passing (AMP) refers to a class of efficient algorithms for statistical estimation in highdimensional problems such as compressed sensing and lowrank matrix estimation. This paper analyzes the performance of AMP in the regime where the problem dimension is large but finite. For concreteness, we consider the setting of highdimensional regression, where the goal is to estimate a highdimensional vector β0 from a noisy measurement y = Aβ0+ ω. AMP is a low-complexity, scalable algorithm for this problem. Under suitable assumptions on the measurement matrix A, AMP has the attractive feature that its performance can be accurately characterized in the large system limit by a simple scalar iteration called state evolution. Previous proofs of the validity of state evolution have all been asymptotic convergence results. In this paper, we derive a concentration inequality for AMP with Gaussian matrices with independent and identically distributed (i.i.d.) entries and finite dimension n × N. The result shows that the probability of deviation from the state evolution prediction falls exponentially in n. This provides theoretical support for empirical findings that have demonstrated excellent agreement of AMP performance with state evolution predictions for moderately large dimensions. The concentration inequality also indicates that the number of AMP iterations t can grow no faster than order (log n/log log n) for the performance to be close to the state evolution predictions with high probability. The analysis can be extended to obtain similar non-asymptotic results for AMP in other settings such as low-rank matrix estimation.

This paper considers the problem of estimating a high-dimensional vector of parameters Θ ∈ Rn from a noisy observation. The noise vector is independent identically distributed Gaussian with known variance. For a squared-error loss function, the James-Stein (JS) estimator is known to dominate the simple maximum-likelihood (ML) estimator when the dimension n exceeds two. The JS-estimator shrinks the observed vector toward the origin, and the risk reduction over the ML-estimator is greatest for Θ that lie close to the origin. JS-estimators can be generalized to shrink the data toward any target subspace. Such estimators also dominate the ML-estimator, but the risk reduction is significant only when Θ lies close to the subspace. This leads to the question: in the absence of prior information about Θ, how do we design estimators that give significant risk reduction over the ML-estimator for a wide range of Θ? In this paper, we propose shrinkage estimators that attempt to infer the structure of Θ from the observed data in order to construct a good attracting subspace. In particular, the components of the observed vector are separated into clusters, and the elements in each cluster shrunk toward a common attractor. The number of clusters and the attractor for each cluster are determined from the observed vector. We provide concentration results for the squared-error loss and convergence results for the risk of the proposed estimators. The results show that the estimators give significant risk reduction over the ML-estimator for a wide range of Θ, particularly for large n. Simulation results are provided to support the theoretical claims.

We consider insertion and deletion channels with the additional assumption that the channel input sequence is implicitly divided into segments such that at most one edit can occur within a segment. We further assume that there are no segment markers in the received sequence. We propose code constructions for the segmented deletion, segmented insertion, and segmented insertion-deletion channels based on subsets of VT codes chosen with pre-determined prefixes and/or suffixes. The proposed codes are zero-error, can be decoded segment-by-segment, and their rate scaling as the segment length increases is the same as that of the maximal code.

Sparse regression codes (SPARCs) are a recent class of codes for reliable communication over the AWGN channel at rates approaching the channel capacity. Approximate message passing (AMP) decoding, a computationally efficient technique for decoding SPARCs, has been proven to be asymptotically capacity-achieving for the AWGN channel. In this paper, we refine the asymptotic results by deriving a large deviations bound on the probability of AMP decoding error. This bound shows that for an appropriate choice of code parameters and any fixed rate smaller than the AWGN capacity, the probability of decoding error decays exponentially in n/(log n)2Twhere T is the number of AMP iterations required for successful decoding. The number of iterations T is inversely proportional to the logarithm of the ratio of channel capacity to rate. For the above choice of code parameters, the complexity of the AMP decoder scales as a low-order polynomial in the block length n.

A coding scheme is proposed for synchronization from a small number of deletions via a one-way error-free link. The scheme is based on multiple layers of Varshamov-Tenengolts codes combined with off-the-shelf linear error-correcting codes.

Sparse superposition codes were recently introduced by Barron and Joseph for reliable communication over the additive white Gaussian noise (AWGN) channel at rates approaching the channel capacity. The codebook is defined in terms of a Gaussian design matrix, and codewords are sparse linear combinations of columns of the matrix. In this paper, we propose an approximate message passing decoder for sparse superposition codes, whose decoding complexity scales linearly with the size of the design matrix. The performance of the decoder is rigorously analyzed and it is shown to asymptotically achieve the AWGN capacity with an appropriate power allocation. Simulation results are provided to demonstrate the performance of the decoder at finite blocklengths. We introduce a power allocation scheme to improve the empirical performance, and demonstrate how the decoding complexity can be significantly reduced by using Hadamard design matrices.

This paper studies the performance of sparse regression codes for lossy compression with the squared-error distortion criterion. In a sparse regression code, code words are linear combinations of subsets of columns of a design matrix. It is shown that with minimum-distance encoding, sparse regression codes achieve the Shannon rate-distortion function for i.i.d. Gaussian sources R*(D) as well as the optimal excess-distortion exponent. This completes a previous result which showed that R*(D) and the optimal exponent were achievable for distortions below a certain threshold. The proof of the rate-distortion result is based on the second moment method, a popular technique to show that a non-negative random variable X is strictly positive with high probability. In our context, X is the number of code words within target distortion D of the source sequence. We first identify the reason behind the failure of the standard second moment method for certain distortions, and illustrate the different failure modes via a stylized example. We then use a refinement of the second moment method to show that R*(D) is achievable for all distortion values. Finally, the refinement technique is applied to Suen's correlation inequality to prove the achievability of the optimal Gaussian excess-distortion exponent.

This paper studies the performance of Approximate Message Passing (AMP), in the regime where the problem dimension is large but finite. We consider the setting of high-dimensional regression, where the goal is to estimate a high-dimensional vector β0from an observation y = Aβ0+ w. AMP is a low-complexity, scalable algorithm for this problem. It has the attractive feature that its performance can be accurately characterized in the asymptotic large system limit by a simple scalar iteration called state evolution. Previous proofs of the validity of state evolution have all been asymptotic convergence results. In this paper, we derive a concentration result for AMP with i.i.d. Gaussian measurement matrices with finite dimension n × N. The result shows that the probability of deviation from the state evolution prediction falls exponentially in n. Our result provides theoretical support for empirical findings that have demonstrated excellent agreement of AMP performance with state evolution predictions for moderately large dimensions.

This paper considers the problem of estimating a high-dimensional vector θ ∈ ℝnfrom a noisy one-time observation. The noise vector is assumed to be i.i.d. Gaussian with known variance. For the squared-error loss function, the James-Stein (JS) estimator is known to dominate the simple maximum-likelihood (ML) estimator when the dimension n exceeds two. The JS-estimator shrinks the observed vector towards the origin, and the risk reduction over the ML-estimator is greatest for θ that lie close to the origin. JS-estimators can be generalized to shrink the data towards any target subspace. Such estimators also dominate the ML-estimator, but the risk reduction is significant only when θ lies close to the subspace. This leads to the question: in the absence of prior information about θ, how do we design estimators that give significant risk reduction over the ML-estimator for a wide range of θ? In this paper, we attempt to infer the structure of θ from the observed data in order to construct a good attracting subspace for the shrinkage estimator. We provide concentration results for the squared-error loss and convergence results for the risk of the proposed estimators, as well as simulation results to support the claims. The estimators give significant risk reduction over the ML-estimator for a wide range of θ, particularly for large n.

Sparse superposition codes were recently introduced by Barron and Joseph for reliable communication over the AWGN channel at rates approaching the channel capacity. In this code, the codewords are sparse linear combinations of columns of a design matrix. In this paper, we propose an approximate message passing decoder for sparse superposition codes. The complexity of the decoder scales linearly with the size of the design matrix. The performance of the decoder is rigorously analyzed and it is shown to asymptotically achieve the AWGN capacity. We also provide simulation results to demonstrate the performance of the decoder at finite block lengths, and introduce a power allocation that significantly improves the empirical performance.

Consider two remote nodes having binary sequences X and Y, respectively. Y is an edited version of X, where the editing involves random deletions, insertions, and substitutions, possibly in bursts. The goal is for the node with Y to reconstruct X with minimal exchange of information over a noiseless link. The communication is measured in terms of both the total number of bits exchanged and the number of interactive rounds of communication. This paper focuses on the setting where the number of edits is o(n/log n), where n is the length of X. We first consider the case where the edits are a mixture of insertions and deletions (indels), and propose an interactive synchronization algorithm with near-optimal communication rate and average computational complexity of O(n) arithmetic operations. The algorithm uses interaction to efficiently split the source sequence into substrings containing exactly one deletion or insertion. Each of these substrings is then synchronized using an optimal one-way algorithm based on the single-deletion correcting channel codes of Varshamov and Tenengolts. We then build on this synchronization algorithm in three different ways. First, it is modified to work with a single round of interaction. The reduction in the number of rounds comes at the expense of higher communication, which is quantified. Next, we present an extension to the practically important case where the insertions and deletions may occur in (potentially large) bursts. Finally, we show how to synchronize the sources to within a target Hamming distance. This feature can be used to differentiate between substitution and indel edits. In addition to theoretical performance bounds, we provide several validating simulation results for the proposed algorithms.

We study the rate-distortion performance of Sparse Regression Codes where the codewords are linear combinations of subsets of columns of a design matrix. It is shown that with minimum-distance encoding and squared error distortion, these codes achieve R*(D), the Shannon rate-distortion function for an i.i.d. Gaussian source. This completes a previous result which showed that R*(D) was achievable for distortions below a certain threshold. The proof is based on the second moment method, a popular technique to show that a non-negative random variable X is strictly positive with high probability. We first identify the reason behind the failure of the vanilla second moment method for this problem, and then introduce a refinement to show that R*(D) is achievable for all distortions.

Many storage channels admit reading and rewriting of the content at a given cost. We consider rewritable channels with a hidden state which models the unknown characteristics of the memory cell. In addition to mitigating the effect of write noise, rewrites can help the write controller obtain a better estimate of the hidden state. The paper has two contributions. The first is a lower bound on the capacity of a general rewritable channel with hidden state. The lower bound is obtained using a coding scheme that combines Gelfand-Pinsker coding with superposition coding. The rewritable AWGN channel is discussed as an example. The second contribution is a simple coding scheme for a rewritable channel where the write noise and hidden state are both uniformly distributed. It is shown that this scheme is asymptotically optimal as the number of rewrites gets large.

We study a new class of codes for lossy compression with the squared-error distortion criterion, designed using the statistical framework of high-dimensional linear regression. Codewords are linear combinations of subsets of columns of a design matrix. Called a sparse superposition or sparse regression codebook, this structure is motivated by an analogous construction proposed recently by Barron and Joseph for communication over an Additive White Gaussian Noise channel. For independent identically distributed (i.i.d) Gaussian sources and minimum-distance encoding, we show that such a code can attain the Shannon rate-distortion function with the optimal error exponent, for all distortions below a specified value. It is also shown that sparse regression codes are robust in the following sense: a codebook designed to compress an i.i.d Gaussian source of variance σ2with (squared-error) distortion D can compress any ergodic source of variance less than σ2to within distortion D. Thus, the sparse regression ensemble retains many of the good covering properties of the i.i.d random Gaussian ensemble, while having a compact representation in terms of a matrix whose size is a low-order polynomial in the block-length.

We propose computationally efficient encoders and decoders for lossy compression using a sparse regression code. The codebook is defined by a design matrix and codewords are structured linear combinations of columns of this matrix. The proposed encoding algorithm sequentially chooses columns of the design matrix to successively approximate the source sequence. It is shown to achieve the optimal distortion-rate function for independent identically distributed (i.i.d) Gaussian sources under the squared-error distortion criterion. For a given rate, the parameters of the design matrix can be varied to tradeoff distortion performance with encoding complexity. An example of such a tradeoff as a function of the block length n is the following. With computational resource (space or time) per source sample of O((n/log n)2), for a fixed distortion-level above the Gaussian distortion-rate function, the probability of excess distortion decays exponentially in n. The sparse regression code is robust in the following sense: for any ergodic source, the proposed encoder achieves the optimal distortion-rate function of an i.i.d Gaussian source with the same variance. Simulations show that the encoder has good empirical performance, especially at low and moderate rates.

We propose computationally efficient encoders and decoders for lossy compression using a Sparse Regression Code. Codewords are structured linear combinations of columns of a design matrix. The proposed encoding algorithm sequentially chooses columns of the design matrix to successively approximate the source sequence. It is shown to achieve the optimal distortion-rate function for i.i.d Gaussian sources with squared-error distortion. For a given rate, the parameters of the design matrix can be varied to trade off distortion performance with encoding complexity. An example of such a trade-off is: computational resource (space or time) per source sample of O((n/ log n)2) and probability of excess distortion decaying exponentially in n/ log n, where n is the block length. The Sparse Regression Code is robust in the following sense: for any ergodic source, the proposed encoder achieves the optimal distortion-rate function of an i.i.d Gaussian source with the same variance. Simulations show that the encoder has very good empirical performance, especially at low and moderate rates.

Sparse Superposition or Sparse Regression codes were recently introduced by Barron and Joseph for communication over the AWGN channel. The code is defined in terms of a design matrix; codewords are linear combinations of subsets of columns of the matrix. These codes achieve the AWGN channel capacity with computationally feasible decoding. We have shown that they also achieve the optimal rate-distortion function for Gaussian sources. Further, the sparse regression codebook has a partitioned structure that facilitates random binning and superposition. In this paper, we review existing results concerning Sparse Regression codes and discuss directions for future research.

New lower bounds are obtained for the capacity of a binary channel with deletions and insertions. Each input bit to the channel is deleted with probability d, or an extra bit is inserted after it with probability i, or it is transmitted unmodified with probability 1-d-i. This paper builds on the idea introduced in [1] of using a sub-optimal decoder that decodes the positions of the deleted and inserted runs, in addition to the transmitted codeword. The mutual information between the channel input and output sequences is expressed as the sum of the rate achieved by this decoder and the rate loss due to its sub-optimality. The main contribution is an analytical lower bound for the rate loss term which leads to an improvement in the capacity lower bound of [1]. For the special case of the deletion channel, the new bound is larger than the previous best lower bound for deletion probabilities up to 0.3.

A single-letter achievable rate region is proposed for the two-receiver discrete memoryless broadcast channel with generalized feedback. The coding strategy involves block-Markov superposition coding using Marton's coding scheme for the broadcast channel without feedback as the starting point. If the message rates in the Marton scheme are too high to be decoded at the end of a block, each receiver is left with a list of messages compatible with its output. Resolution information is sent in the following block to enable each receiver to resolve its list. The key observation is that the resolution information of the first receiver is correlated with that of the second. This correlated information is efficiently transmitted via joint source-channel coding, using ideas similar to the Han-Costa coding scheme. Using the result, we obtain an achievable rate region for the stochastically degraded additive white Gaussian noise broadcast channel with noisy feedback from only one receiver. It is shown that this region is strictly larger than the no-feedback capacity region.

This paper considers a binary channel with deletions and insertions, where each input bit is transformed in one of the following ways: it is deleted with probability d, or an extra bit is added after it with probability i, or it is transmitted unmodified with probability 1-d-i. A computable lower bound on the capacity of this channel is derived. The transformation of the input sequence by the channel may be viewed in terms of runs as follows: some runs of the input sequence get shorter/longer, some runs get deleted, and some new runs are added. It is difficult for the decoder to synchronize the channel output sequence to the transmitted codeword mainly due to deleted runs and new inserted runs. The main idea is a mutual information decomposition in terms of the rate achieved by a suboptimal decoder that determines the positions of the deleted and inserted runs in addition to decoding the transmitted codeword. The mutual information between the channel input and output sequences is expressed as the sum of the rate achieved by this decoder and the rate loss due to its suboptimality. Obtaining computable lower bounds on each of these quantities yields a lower bound on the capacity. The bounds proposed in this paper provide the first characterization of achievable rates for channels with general insertions, and for channels with both deletions and insertions. For the special case of the deletion channel, the proposed bound improves on the previous best lower bound for deletion probabilities up to 0.3.

We study a class of codes for compressing memoryless Gaussian sources, designed using the statistical framework of high-dimensional linear regression. Codewords are linear combinations of subsets of columns of a design matrix. With minimum-distance encoding we show that such a codebook can attain the rate-distortion function with the optimal error-exponent, for all distortions below a specified value. The structure of the codebook is motivated by an analogous construction proposed recently by Barron and Joseph for communication over an AWGN channel.

Many storage channels admit reading and rewriting of the content at a given cost. We consider rewritable channels with uniform write noise and a hidden state which models the unknown characteristics of the memory cell. In addition to mitigating the effect of the write noise, rewrites can help the write controller obtain a better estimate of the hidden state. We present two coding strategies, each of which yields a lower bound on the rewrite capacity. We show that the second strategy is asymptotically optimal as the number of rewrites gets large.

Consider a binary channel with deletions and insertions, where each input bit is transformed in one of the following ways: it is deleted with probability d, or an extra bit added after it with probability i, or it is transmitted unmodified with probability 1 - d - i. We obtain a lower bound on the capacity of this channel. The transformation of the input sequence by the channel may be viewed in terms of runs as follows: some runs of the input sequence get shorter/longer, some runs get deleted, and some new runs are added. The capacity is difficult to compute mainly due to the last two phenomena: deleted runs, and new inserted runs. We consider a decoder which first decodes the positions of the deleted and inserted runs, and then the transmitted codeword. Analyzing the performance of such a decoder leads to a computable lower bound on the capacity.

The two-channel multiple descriptions problem for an independent and identically distributed (i.i.d.) source, with feed-forward to one or both side-decoders is considered. A single-letter achievable rate-region is derived; it enlarges the best known rate-region for multiple descriptions without feed-forward. The proof of the result uses a block-Markov superposition source coding strategy. In point-to-point source coding, feed-forward does not decrease the rate-distortion function of an i.i.d. source. In contrast, an example is provided to show that the derived region can be strictly larger than the optimal multiple description rate-distortion region without feed-forward.

A new single-letter achievable rate region is proposed for the two-user discrete memoryless multiple-access channel(MAC) with noiseless feedback. The proposed region includes the Cover–Leung rate region, and it is shown that the inclusion is strict. The proof uses a block-Markov superposition strategy based on the observation that the messages of the two users are correlated given the feedback. The rates of transmission are too high for each encoder to decode the other's message directly using the feedback, so they transmit correlated information in the next block to learn the message of one another. They then cooperate in the following block to resolve the residual uncertainty of the decoder. The coding scheme may be viewed as a natural generalization of the Cover–Leung scheme with a delay of one extra block and a pair of additional auxiliary random variables. We compute the proposed rate region for two different MACs and compare the results with other known rate regions for the MAC with feedback. Finally, we show how the coding scheme can be extended to obtain larger rate regions with more auxiliary random variables.

Let X and Y be finite alphabets and PXYa joint distribution over them, with PXand PYrepresenting the marginals. For any ϵ > 0, the set of n-length sequences xnand ynthat are jointly typical according to PXYcan be represented on a bipartite graph. We present a formal definition of such a graph, known as a typicality graph, and study some of its properties. These properties arise in the study of several multiuser communication problems.

A single-letter achievable rate region is proposed for the two-receiver discrete memoryless broadcast channel with feedback. It is shown through an example that the rate-region can be strictly larger than the no-feedback capacity region. The coding strategy involves block-Markov superposition coding using Marton's scheme as the starting point. If the message rates in the Marton scheme are too high to be decoded at the end of a block, each receiver is left with a list of messages compatible with its output. In the next block, we send resolution information for each receiver to resolve its list. The key observation is that the resolution information of the first receiver is correlated with that of the second. We transmit this correlated information efficiently in the following block using ideas from the Han-Costa coding scheme.

The problem of computing the capacity-cost function of channels with feedback and the rate-distortion function of sources with feed-forward is considered. Sufficient conditions are derived on : a) the structure of the cost function for a chosen joint distribution to achieve the optimal feedback capacity-cost function, b) the structure of the distortion function for a chosen joint distribution to achieve the optimal feed-forward rate-distortion function. These structural results are useful since it is infeasible in general to directly compute the optimizations. Examples are provided to show how the results can help compute the performance limits with feedback and feed-forward.

A single-letter achievable rate region for the two-user discrete memoryless multiple-access channel is proposed. The rate region includes the Cover-Leung region, and it is shown that the inclusion is strict. The proof uses a block-Markov superposition strategy based on the observation that the messages of the two users are correlated given the feedback. The rates of transmission are too high for each encoder to decode the other's message directly using the feedback, so they transmit correlated information in the next block in order to learn the message of one another. They then cooperate in the following block to resolve the residual uncertainty of the decoder. Our scheme may be viewed as a natural generalization of the Cover-Leung scheme with a delay of one extra block and a pair of additional auxiliary random variables. The scheme can also be extended to obtain larger rate-regions with more auxiliary random variables.

The two-channel multiple descriptions problem for an i.i.d source, with feed-forward to one or both side-decoders is considered. A single-letter achievable rate-region is derived; it enlarges the best known rate-region for multiple descriptions without feed-forward. The proof of the result uses a block-Markov superposition source coding strategy. In point-to-point source coding, feed-forward does not decrease the rate-distortion function of an i.i.d source. In contrast, an example is provided to show that the derived region can be larger than the optimal multiple description rate region without feed-forward.

We study the problem of computing the rate-distortion function for sources with feed-forward and the capacity for channels with feedback. The formulas (involving directed information) for the optimal rate-distortion function with feed-forward and channel capacity with feedback are multi- letter expressions and cannot be computed easily in general. In this work, we derive conditions under which these can be computed for a large class of sources/channels with memory and distortion/cost measures. Illustrative examples are also provided.

In this work, we consider a source coding model with feed-forward. We analyze a system with a noiseless, feed-forward link where the decoder has knowledge of all previous source samples while reconstructing the present sample. The rate-distortion function for an arbitrary source with feed-forward is derived in terms of directed information, a variant of mutual information. We further investigate the nature of the rate-distortion function with feed-forward for two common types of sources- discrete memoryless sources and Gaussian sources. We then characterize the error exponent for a general source with feed-forward. The results are then extended to feed-forward with an arbitrary delay larger than the block length.

In this work, we consider a source coding model with feedforward. We analyze a system with a noiseless feedforward link where the decoder has knowledge of all previous source samples while reconstructing the present sample. The rate-distortion function for an arbitrary source with feedforward is derived in terms of directed information, a variant of mutual information. The special cases of discrete memoryless sources and Gaussian sources with feedforward are further examined. We also derive a random coding error exponent which is used to bound the probability of decoding error for a source code (with feedforward) of finite block length. The results are then extended to feedforward with an arbitrary delay larger than the block length.