Compressive sensing: To compress or not to compress

In this paper, we consider the compressive sensing scheme from the information theory point of view and derive the lower bound of the probability of error for CS when length N of the information vector is large. The result has been shown that, for an i.i.d. Gaussian distributed signal vector with unit variance, if the measurement matrix is chosen such that the ratio of the minimum and maximum eigenvalues of the covariance matrices is greater or equal to 4/(M/K+1), then the probability of error is lower bounded by a non-positive value; which implies that the information can be perfectly recovered from the CS scheme. On the other hand, if the measurement matrix is chosen such that the minimum and maximum eigenvalues of the covariance matrices are equal, then the error is certain and the perfect recovery can never be achieved.