This work establishes regularity conditions for consistency and asymptotic normality of the multiple parameter maximum likelihood estimator (MLE) from censored data, where the censoring mechanism is in the form of 1-bit measurements. The underlying distribution of the uncensored data is assumed to belong to the exponential family, with natural parameters expressed as a linear combination of the predictors, known as generalized linear model (GLM). As part of the analysis, the Fisher information matrix is also derived for both censored and uncensored data, which helps to quantify the impact of censoring and assess the performance of the MLE. The choice of a GLM allows one to consider a variety of practical examples where 1-bit estimation is of interest. In particular, it is shown how the derived results can be used to analyze two practically relevant scenarios: the Gaussian model with both unknown mean and variance, and the Poisson model with an unknown mean.

Approximate Message Passing (AMP) algorithms are a class of iterative procedures for computationally-efficient estimation in high-dimensional inference and estimation tasks. Due to the presence of an ‘Onsager’ correction term in its iterates, forN×Mdesign matrices A with i.i.d. Gaussian entries, the asymptotic distribution of the estimate at any iteration of the algorithm can be exactly characterized in the large system limit asM/N→ δ ∈ (0,∞) via a scalar recursion referred to as state evolution. In this paper, we show that appropriate functionals of the iterates, in fact, concentrate around their limiting values predicted by these asymptotic distributions with rates exponentially fast inNfor a large class of AMP-style algorithms, including those that are used when high-dimensional generalized linear regression models are assumed to be the data-generating process, like the generalized AMP algorithm, or those that are used when the measurement matrix is assumed to be rotationally invariant instead of i.i.d. Gaussian, like vector AMP and generalized vector AMP. In practice, these more general AMP algorithms have many applications, for example in communications or imaging, and this work provides the first study of finite sample behavior of such algorithms.

This work considers a co-located MIMO radar with MTtransmitting and MRreceiving antennas in a so-called massive MIMO regime, that is, where the number of virtual spatial antennas N = MTMRis large. Recently, it has been demonstrated that as N grows to infinity, one can fully characterize the false alarm and detection probabilities with very minimal assumptions on the disturbance vector. In this work, these results are partially refined and a lower bound on the probability of detection is provided for any fixed, finite N under certain randomness models for the noise. This result can serve as a rule of thumb for the design of massive MIMO radar systems by indicating the number of antennas required to attain a desired target detection probability.

Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: might it be possible to infer properties of the community structure (for instance, the number and sizes of communities) even in situations where actually finding those communities is believed to be computationally hard? We show the answer is no. In particular, we consider certain hypothesis testing problems between models with different community structures, and we show (in the low-degree polynomial framework) that testing between two options is as hard as finding the communities. In addition, our methods give the first computational lower bounds for testing between two different "planted" distributions, whereas previous results have considered testing between a planted distribution and an i.i.d. "null" distribution.

It is well known that central order statistics exhibit a central limit behavior and converge to a Gaussian distribution as the sample size grows. This paper strengthens this known result by establishing an entropic version of the central limit theorem that ensures a stronger mode of convergence using the relative entropy. This upgrade in convergence is shown at the expense of extra regularity conditions, which can be considered as mild. To prove this result, ancillary results on order statistics are derived, which might be of independent interest. For instance, a rather general bound on the moments of order statistics, and an upper bound on the mean squared error of estimating the$p \in (0,1)$-th quantile of an unknown cumulative distribution function, are derived. Finally, a discussion on the necessity of the derived conditions for convergence and on the rate of convergence and monotonicity of the relative entropy is provided.

A common goal in many research areas is to reconstruct an unknown signal$\mathbf {x}$from noisy linear measurements. Approximate message passing (AMP) is a class of low-complexity algorithms that can be used for efficiently solving such high-dimensional regression tasks. Often, it is the case that side information (SI) is available during reconstruction, for example in online learning applications. For this reason, a novel algorithmic framework that incorporates SI into AMP, referred to as approximate message passing with side information (AMP-SI), has been recently introduced. In this work, we provide rigorous performance guarantees for AMP-SI when there are statistical dependencies between the signal and SI pairs and the entries of the measurement matrix are independent and identically distributed (i.i.d.) Gaussian. We also allow for statistical dependencies within the elements of the signal itself, by considering a flexible AMP-SI framework incorporating both separable and non-separable denoisers. The AMP-SI performance is shown to be provably tracked by a scalar iteration referred to as state evolution (SE). Moreover, we provide numerical examples that demonstrate empirically that the SE can predict the AMP-SI mean square error accurately.

It is well known that central order statistics exhibit a central limit behavior and converge to a Gaussian distribution as the sample size n grows. This paper strengthens this known result by establishing an entropic version of the central limit theorem (CLT) that ensures a stronger mode of convergence using the relative entropy. In particular, an order $O(1/\sqrt n )$ rate of convergence is established under mild conditions on the parent distribution of the sample generating the order statistics. To prove this result, ancillary results on order statistics are derived, which might be of independent interest.

$\alpha$-posteriors and their variational approximations distort standard posterior inference by downweighting the likelihood and introducing variational approximation errors. We show that such distortions, if tuned appropriately, reduce the Kullback--Leibler (KL) divergence from the true, but perhaps infeasible, posterior distribution when there is potential parametric model misspecification. To make this point, we derive a Bernstein--von Mises theorem showing convergence in total variation distance of $\alpha$-posteriors and their variational approximations to limiting Gaussian distributions. We use these limiting distributions to evaluate the KL divergence between true and reported posteriors. We show that the KL divergence is minimized by choosing $\alpha$ strictly smaller than one, assuming there is a vanishingly small probability of model misspecification. The optimized value of $\alpha$ becomes smaller as the misspecification becomes more severe. The optimized KL divergence increases logarithmically in the magnitude of misspecification and not linearly as with the usual posterior. Moreover, the optimized variational approximations of $\alpha$-posteriors can induce additional robustness to model misspecification beyond that obtained by optimally downweighting the likelihood.

Sparse regression codes with approximate message passing (AMP) decoding have gained much attention in recent times. The concepts underlying this coding scheme extend to unsourced random access with coded compressed sensing (CCS), as first demonstrated by Fengler, Jung, and Caire. Specifically, their approach employs a concatenated coding framework with an inner AMP decoder followed by an outer tree decoder. In their original implementation, these two components work independently of each other, with the tree decoder acting on the static output of the AMP decoder. This article introduces a novel framework where the inner AMP decoder and the outer decoder operate in tandem, dynamically passing information back and forth to take full advantage of the underlying CCS structure. This scheme necessitates the redesign of the outer code as to enable belief propagation in a computationally tractable manner. The enhanced architecture exhibits significant performance benefits over a range of system parameters. The error performance of the proposed scheme can be accurately predicted through a set of equations known as state evolution of AMP. These findings are supported both analytically and through numerical methods.

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.

SLOPE is a relatively new convex optimization procedure for high-dimensional linear regression via the sorted ℓ1penalty: the larger the rank of the fitted coefficient, the larger the penalty. This non-separable penalty renders many existing techniques invalid or inconclusive in analyzing the SLOPE solution. In this paper, we develop an asymptotically exact characterization of the SLOPE solution under Gaussian random designs through solving the SLOPE problem using approximate message passing (AMP). This algorithmic approach allows us to approximate the SLOPE solution via the much more amenable AMP iterates. Explicitly, we characterize the asymptotic dynamics of the AMP iterates relying on a recently developed state evolution analysis for non-separable penalties, thereby overcoming the difficulty caused by the sorted ℓ1penalty. Moreover, we prove that the AMP iterates converge to the SLOPE solution in an asymptotic sense, and numerical simulations show that the convergence is surprisingly fast. Our proof rests on a novel technique that specifically leverages the SLOPE problem. In contrast to prior literature, our work not only yields an asymptotically sharp analysis but also offers an algorithmic, flexible, and constructive approach to understanding the SLOPE problem.

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.

The LASSO is a well-studied method for use in high-dimensional linear regression where one wishes to recover a sparse vector b from noisy observations y measured through a n-by-p matrix X with the model y = Xb + w where w is a vector of independent, mean-zero noise. We study the linear asymptotic regime where the under sampling ratio, n/p, approaches a constant greater than 0 in the limit.Using a carefully constructed approximate message passing (AMP) algorithm that converges to the LASSO estimator and recent finite sample theoretical performance guarantees for AMP, we provide large deviations bounds between various measures of LASSO loss and their concentrating values predicted by the AMP state evolution that shows exponentially fast convergence (in n) when the measurement matrix X is i.i.d. Gaussian. This work refines previous asymptotic analysis of LASSO loss in [Bayati and Montanari, 2012].

Sparse regression codes with approximate message passing (AMP) decoding have gained much attention in recent times. The concepts underlying this coding scheme extend to unsourced access with coded compressed sensing (CCS), as first pointed out by Fengler, Jung, and Caire. More specifically, their approach uses a concatenated coding framework with an inner AMP decoder followed by an outer tree decoder. In the original implementation, these two components work independently of each other, with the tree decoder acting on the static output of the AMP decoder. This article introduces a novel framework where the inner AMP decoder and the outer tree decoder operate in tandem, dynamically passing information back and forth to take full advantage of the underlying CCS structure. The enhanced architecture exhibits significant performance benefit over a range of system parameters.

Vector Approximate Message Passing is a computationally-efficient iterative algorithm for estimation in high-dimensional regression problems. Due to the presence of an `Onsager' correction term in its iterates, for a wide class of N × M design matrices, namely those that are right orthogonally-invariant, the asymptotic distribution of the algorithm's estimate of the signal at any iteration can be exactly characterized in the large system limit as M/N → δ ∈ (0,∞) via a scalar recursion referred to as state evolution. In this paper, we show that appropriate functionals of the iterates in fact concentrate around their limiting values predicted by these asymptotic distributions with rates exponentially fast in N.

This work considers a random sample X1,X2,…,Xndrawn independently and identically distributed from some known parent distribution PXwith X(1)≤ X(2)≤ … ≤ X(n)being the order statistics of the sample. Under the assumption of an invertible cumulative distribution function associated with the parent distribution PX, a distribution-free property is established showing that the f-divergence between the joint distribution of order statistics and the product distribution of order statistics does not depend on PX. Moreover, it is shown that the mutual information between two subsets of order statistics also satisfies a distribution-free property; that is, it does not depend on PX. Furthermore, the decoupling rates between X(r)and X(m)(i.e., rates at which the mutual information approaches zero) are characterized for various choices of (r,m). The work also considers discrete distributions, which do not satisfy the previously-stated invertibility assumption, and it is shown that no such distribution-free property holds: the mutual information between order statistics does depend on the parent distribution PX. Upper bounds on the decoupling rates in the discrete setting are also established.

We determine statistical and computational limits for estimation of a rank-one matrix (the spike) corrupted by an additive gaussian noise matrix, in a sparse limit, where the underlying hidden vector (that constructs the rank-one matrix) has a number of non-zero components that scales sub-linearly with the total dimension of the vector, and the signal-to-noise ratio tends to infinity at an appropriate speed. We prove explicit low-dimensional variational formulas for the asymptotic mutual information between the spike and the observed noisy matrix and analyze the approximate message passing algorithm in the sparse regime. For Bernoulli and Bernoulli-Rademacher distributed vectors, and when the sparsity and signal strength satisfy an appropriate scaling relation, we find all-or-nothing phase transitions for the asymptotic minimum and algorithmic mean-square-errors. These jump from their maximum possible value to zero, at well defined signal-to-noise thresholds whose asymptotic values we determine exactly. In the asymptotic regime the statistical-to-algorithmic gap diverges indicating that sparse recovery is hard for approximate message passing.

A common goal in many research areas is to reconstruct an unknown signal x from noisy linear measurements. Approximate message passing (AMP) is a class of low-complexity algorithms for efficiently solving such high-dimensional regression tasks. Often, it is the case that side information (SI) is available during reconstruction. For this reason a novel algorithmic framework that incorporates SI into AMP, referred to as approximate message passing with side information (AMP-SI), has been recently introduced. An attractive feature of AMP is that when the elements of the signal are exchangeable, the entries of the measurement matrix are independent and identically distributed (i.i.d.) Gaussian, and the denoiser applies the same non-linearity at each entry, the performance of AMP can be predicted accurately by a scalar iteration referred to as state evolution (SE). However, the AMP-SI framework uses different entry-wise scalar denoisers, based on the entry-wise level of the SI, and therefore is not supported by the standard AMP theory. In this work, we provide rigorous performance guarantees for AMP-SI when the input signal and SI are drawn i.i.d. according to some joint distribution subject to finite moment constraints. Moreover, we provide numerical examples to support the theory which demonstrate empirically that the SE can predict the AMP-SI mean square error accurately.

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.

SLOPE is a relatively new convex optimization procedure for high-dimensional linear regression via the sorted $\ell_1$ penalty: the larger the rank of the fitted coefficient, the larger the penalty. This non-separable penalty renders many existing techniques invalid or inconclusive in analyzing the SLOPE solution. In this paper, we develop an asymptotically exact characterization of the SLOPE solution under Gaussian random designs through solving the SLOPE problem using approximate message passing (AMP). This algorithmic approach allows us to approximate the SLOPE solution via the much more amenable AMP iterates. Explicitly, we characterize the asymptotic dynamics of the AMP iterates relying on a recently developed state evolution analysis for non-separable penalties, thereby overcoming the difficulty caused by the sorted $\ell_1$ penalty. Moreover, we prove that the AMP iterates converge to the SLOPE solution in an asymptotic sense, and numerical simulations show that the convergence is surprisingly fast. Our proof rests on a novel technique that specifically leverages the SLOPE problem. In contrast to prior literature, our work not only yields an asymptotically sharp analysis but also offers an algorithmic, flexible, and constructive approach to understanding the SLOPE problem.

Approximate message passing (AMP) is a class of low-complexity, scalable algorithms for solving high-dimensional linear regression tasks where one wishes to recover an unknown signal from noisy, linear measurements. AMP is an iterative algorithm that performs estimation by updating an estimate of the unknown signal at each iteration and the performance of AMP (quantified, for example, by the mean squared error of its estimates) depends on the choice of a “denoiser” function that is used to produce these signal estimates at each iteration. An attractive feature of AMP is that its performance can be tracked by a scalar recursion referred to as state evolution. Previous theoretical analysis of the accuracy of the state evolution predictions has been limited to the use of only separable denoisers or block-separable denoisers, a class of denoisers that underperform when sophisticated dependencies exist between signal entries. Since signals with entrywise dependencies are common in image/video-processing applications, in this work we study the high-dimensional linear regression task when the dependence structure of the input signal is modeled by a Markov random field prior distribution. We provide a rigorous analysis of the performance of AMP, demonstrating the accuracy of the state evolution predictions, when a class of non-separable sliding-window denoisers is applied. Moreover, we provide numerical examples where AMP with sliding-window denoisers can successfully capture local dependencies in images.

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.

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.

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.

Approximate message passing (AMP) is a class of efficient algorithms for solving high-dimensional linear regression tasks where one wishes to recover an unknown signal βο from noisy, linear measurements y = Aβ0+ w. When applying a separable denoiser at each iteration, the performance of AMP (for example, the mean squared error of its estimates) can be accurately tracked by a simple, scalar iteration referred to as state evolution. Although separable denoisers are sufficient if the unknown signal has independent and identically distributed entries, in many real-world applications, like image or audio signal reconstruction, the unknown signal contains dependencies between entries. In these cases, a coordinate-wise independence structure is not a good approximation to the true prior of the unknown signal. In this paper we assume the unknown signal has dependent entries, and using a class of non-separable sliding-window denoisers, we prove that a new form of state evolution still accurately predicts AMP performance. This is an early step in understanding the role of non-separable denoisers within AMP, and will lead to a characterization of more general denoisers in problems including compressive image reconstruction.

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.

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 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.

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.