An efficiency upper bound for inverse covariance estimation

We derive a quantitative upper bound for the efficiency of estimating entries in the inverse covariance matrix of a high dimensional distribution. We show that in order to approximate an off-diagonal entry of the density matrix of a d-dimensional Gaussian random vector, one needs at least a number of samples proportional to d. Furthermore, we show that with n a parts per thousand(a) d samples, the hypothesis that two given coordinates are fully correlated, when all other coordinates are conditioned to be zero, cannot be told apart from the hypothesis that the two are uncorrelated.