Performance bounds for sparse estimation with random noise

The problem considered in this paper is to estimate a deterministic vector representing elements in an overcomplete dictionary. The vector is assumed to be sparse and is to be estimated from measurements corrupted by Gaussian noise. Our goal is to derive a lower bound on the mean-squared error (MSE) achievable in this setting. To this end, an appropriate definition of unbiasedness in the sparse setting is developed, and the unbiased Crameacuter-Rao bound (CRB) is derived. The resulting bound is shown to be identical to the MSE of the oracle estimator. Combined with the fact that the CRB is achieved at high signal-to-noise ratios by the maximum likelihood technique, our result provides a new interpretation for the common practice of using the oracle estimator as a gold standard against which practical approaches are compared.