Asymptotic Achievability of the Cramér–Rao Bound For Noisy Compressive Sampling

Abstract

We consider a model of the form ${bf y}={bf Ax}+{bf n}$, where ${bf x}inBBC^{M}$ is sparse with at most $L$ nonzero coefficients in unknown locations, ${bf y}inBBC^{N}$ is the observation vector, ${bf A}inBBC^{Ntimes M}$ is the measurement matrix and ${bf n}inBBC^{N}$ is the Gaussian noise. We develop a CramÉr–Rao bound on the mean squared estimation error of the nonzero elements of ${bf x}$, corresponding to the genie-aided estimator (GAE) which is provided with the locations of the nonzero elements of ${bf x}$. Intuitively, the mean squared estimation error of any estimator without the knowledge of the locations of the nonzero elements of ${bf x}$ is no less than that of the GAE. Assuming that $L/N$ is fixed, we establish the existence of an estimator that asymptotically achieves the CramÉr–Rao bound without any knowledge of the locations of the nonzero elements of ${bf x}$ as $Nrightarrowinfty$ , for ${bf A}$ a random Gaussian matrix whose elements are drawn i.i.d. according to ${cal N}(0,1)$ .