Large-System Estimation Performance in Noisy Compressed Sensing with Random Support - a Bayesian Analysis

Compressed sensing (CS) enables measurement reconstruction by using sampling rates below the Nyquist rate, as long as the amplitude vector of interest is sparse. In this work, we first derive and analyze the Bayesian Cramér-Rao Bound (BCRB) for the amplitude vector when the set of indices (the support) of its non-zero entries is known. We consider the following context: (i) The dictionary is non-stochastic but randomly generated; (ii) the number of measurements and the support cardinality grow to infinity in a controlled manner, i.e. the ratio of these quantities converges to a constant; (iii) the support is random; and (iv) the vector of non-zero amplitudes follow a multidimensional generalized normal distribution. Using results from random matrix theory, we obtain closed-form approximations of the BCRB. These approximations can be formulated in a very compact form in low and high SNR regimes. Secondly, we provide a statistical analysis of the variance and the statistical efficiency of the oracle linear mean-square-error (LMMSE) estimator. Finally, we present results from numerical investigations in the context of non-bandlimited finite-rate-of-innovation (FRI) signal sampling. We show that the performance of Bayesian mean square error (BMSE) estimators that are aware of the cardinality of the support, such as OMP and CoSaMP, are in good agreement with the developed lower bounds in the high SNR regime. Conversely, sparse estimators exploiting only the knowledge of the parameter vector and the noise variance in form of a-priori distributions of these parameters, like LASSO and BPDN, are not efficient at high SNR. However, at low SNR their BMSE is lower than that of the former estimators and may be close to the BCRB.