Compressed Sensing; Approximate Message Passing; State Evolution; Bayesian Methods
de
Abstract:
In recent years, the low-dimensional representation of high-dimensional signals has been recognized as an essential concept in modern signal processing. An important family of problems is subsumed under the term compressed sensing (CS). CS copes with the reconstruction or estimation of a high-dimensional vector from a (noisy) underdetermined system of linear equations, assuming that the measured vector has only a relatively low number of nonzero components. Under mild conditions on the dimensions and the structure of the system matrix (measurement matrix), reconstruction or robust estimation is feasible. However, due to the high dimension of the problem and the nonlinear (sparsity) constraint, standard methods fail. Approximate message passing (AMP), an approximate and highly simplified version of loopy belief propagation, has proven to cope efficiently with high-dimensional sparse problems. Its simplicity and fast convergence make it a preferred choice for recovery. Its Bayesian version, Bayesian approximate message passing (BAMP), which is an approximate minimum mean squared error (MMSE) estimator, is a versatile algorithm that can incorporate prior knowledge about the measured vector in the form of a prior probability density function (pdf) of its components. When there is a set of measured vectors which are not completely independent, but jointly sparse (i.e., their sets of nonzero components are identical), joint recovery proves advantageous. More specifically, when a multivariate prior for the vector components of the jointly measured vectors is available, BAMP can be extended to its vector version, the vector Bayesian approximate message passing (V-BAMP). V-BAMP is an approximate MMSE estimator for the whole set of jointly measured vectors, and its analysis methods can be derived from the scalar BAMP. Specifically, the state evolution (SE) equations provide an analytical prediction for the residual mean squared error (MSE) of the vector estimates. Understanding the dynamics of SE in terms of fixed points as a function of the signal prior, the noise parameters, and the sampling rate is of crucial importance because it uncovers the expected behavior of V-BAMP. In this work it is shown that arbitrary signal and noise correlations can be eliminated in the joint measurement case. That is, every measurement instance can be transformed into an equivalent measurement in which both the signal and the noise are uncorrelated. Furthermore, it is proven that for the widely employed Bernoulli-Gauss (BG) signal prior this property is preserved through the V-BAMP iterations. It follows that the V-BAMP is equivariant with respect to such transformations, and that the latter has to be done only once before starting V-BAMP. The inverse transform can be done at any iteration, and neither the convergence nor the MSE performance are affected. The SE equations are extended to the multivariate case and extensive simulations show the effect of having multiple measurement vectors and the effect of having correlation on the recovery. Recently, based on the analogy between the statistical physics of large disordered systems and loopy belief propagation, the replica method was used to derive the MMSE of the Bayesian estimator of the CS measurement, given its parameters, and BG signal prior with standard Gaussian nonzero signal components and uniform uncorrelated Gaussian noise. In this work the replica analysis is extended to the case with arbitrary (nonuniform) uncorrelated Gaussian noise. Together with the joint decorrelation transform and the equivariance property of V-BAMP, the replica analysis turns out to predict the dynamics of V-BAMP for any BG measurement instance with Gaussian noise. Simulations confirm the analogy between the SE analysis and the replica analysis, and demonstrate the effect of signal correlation from multiple aspects.