Asymptotic Achievability of the Cramer-Rao Bound for Noisy Compressive Sampling

We consider a model of the form y = Ax + n, where x is an element of C-M is sparse with at most L nonzero coefficients in unknown locations, y is an element of C-N is the observation vector, A is an element of C-NxM is the measurement matrix and n is an element of C-N is the Gaussian noise. We develop a Cramer-Rao bound on the mean squared estimation error of the nonzero elements of x, corresponding to the genie-aided estimator (GAE) which is provided with the locations of the nonzero elements of x. Intuitively, the mean squared estimation error of any estimator without the knowledge of the locations of the nonzero elements of 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 Cramer-Rao bound without any knowledge of the locations of the nonzero elements of x as N -> infinity, for A a random Gaussian matrix whose elements are drawn i.i.d. according to N(0, 1).