Universal lower bounds on sampling rates for covariance estimation

Covariance estimation from compressive samples has become particularly attractive for two main reasons. First, many applications do not require the signal itself, and second-order statistics are oftentimes sufficient. The resulting requirement on the sampling rate of the original signal can therefore be reduced. Second, signal recovery from compressive samples leads to underdetermined systems which require additional constraints, such as the popular sparsity assumption. In contrast, covariance estimation can yield overdetermined problems, even from compressive samples, so that the additional constraints on the signal can be dropped. In this paper, we provide a unified framework for deriving lower bounds on the sampling rate required for covariance estimation of stationary signals, by deriving the lower Beurling density of the difference set associated with the original sampling set. A general sampling scheme is first considered, followed by the analysis of multicoset sampling. We prove that, in both cases, the sampling rate can be arbitrarily low, as was remarked extensively in the literature.