A signal recovery scheme is developed for linear observation systems based on expectation consistent (EC) mean field approximation. Approximate message passing (AMP) is known to be consistent with the results obtained using the replica theory, which is supposed to be exact in the large system limit, when each entry of the observation matrix is independently generated from an identical distribution. However, this is not necessarily the case for general matrices. We show that EC recovery exhibits consistency with the replica theory for a wider class of random observation matrices. This is numerically confirmed by experiments for the Bayesian optimal signal recovery of compressed sensing using random row-orthogonal matrices.
Reference @cite_17 used the replica method to find a decoupled formulation for the input-output statistics of a CS system whose measurement matrix is composed of independently and identically distributed (i.i.d.) entries. As a corollary, this leads to a computationally feasible characterization of the MMSE as well. The MMSE of a similar i.i.d. setup was later evaluated directly in @cite_19 by using mathematically rigorous methods. Numerical results therein verified the accuracy of the earlier replica analysis. Finally, non-i.i.d. sensing matrices where considered in @cite_9 , where the replica method was used to find the support recovery performance of a class of CS systems.
@cite_19 @cite_9 @cite_17
2949267240 2160051394 2550925785
Compressed sensing is a signal processing technique in which data is acquired directly in a compressed form. There are two modeling approaches that can be considered: the worst-case (Hamming) approach and a statistical mechanism, in which the signals are modeled as random processes rather than as individual sequences. In this paper, the second approach is studied. In particular, we consider a model of the form @math , where each comportment of @math is given by @math , where @math are i.i.d. Gaussian random variables, and @math are binary random variables independent of @math , and not necessarily independent and identically distributed (i.i.d.), @math is a random matrix with i.i.d. entries, and @math is white Gaussian noise. Using a direct relationship between optimum estimation and certain partition functions, and by invoking methods from statistical mechanics and from random matrix theory (RMT), we derive an asymptotic formula for the minimum mean-square error (MMSE) of estimating the input vector @math given @math and @math , as @math , keeping the measurement rate, @math , fixed. In contrast to previous derivations, which are based on the replica method, the analysis carried out in this paper is rigorous. Consider a Bernoulli-Gaussian complex n-vector whose components are Vi = XiBi, with Xi C N(0, Px) and binary Bi mutually independent and iid across i. This random q-sparse vector is multiplied by a square random matrix U, and a randomly chosen subset, of average size n p, p ∈ [0,1], of the resulting vector components is then observed in additive Gaussian noise. We extend the scope of conventional noisy compressive sampling models where U is typically a matrix with iid components, to allow U satisfying a certain freeness condition. This class of matrices encompasses Haar matrices and other unitarily invariant matrices. We use the replica method and the decoupling principle of Guo and Verdu, as well as a number of information-theoretic bounds, to study the input-output mutual information and the support recovery error rate in the limit of n → ∞. We also extend the scope of the large deviation approach of Rangan and characterize the performance of a class of estimators encompassing thresholded linear MMSE and l1 relaxation. Compressed sensing deals with the reconstruction of a high-dimensional signal from far fewer linear measurements, where the signal is known to admit a sparse representation in a certain linear space. The asymptotic scaling of the number of measurements needed for reconstruction as the dimension of the signal increases has been studied extensively. This work takes a fundamental perspective on the problem of inferring about individual elements of the sparse signal given the measurements, where the dimensions of the system become increasingly large. Using the replica method, the outcome of inferring about any fixed collection of signal elements is shown to be asymptotically decoupled, i.e., those elements become independent conditioned on the measurements. Furthermore, the problem of inferring about each signal element admits a single-letter characterization in the sense that the posterior distribution of the element, which is a sufficient statistic, becomes asymptotically identical to the posterior of inferring about the same element in scalar Gaussian noise. The result leads to simple characterization of all other elemental metrics of the compressed sensing problem, such as the mean squared error and the error probability for reconstructing the support set of the sparse signal. Finally, the single-letter characterization is rigorously justified in the special case of sparse measurement matrices where belief propagation becomes asymptotically optimal.