Theoretical performance limits for compressive sensing with random noise

In this paper, we analyzed the performance of noisy compressive sensing theoretically, and derived both the lower bound and upper bound of the probability of error for compressive sensing, with the assumption that both the original information and the noise follow Gaussian distribution. Both the lower bound and upper bound of the probability of error for the general case without special requirement of the measurement matrix Φ are provided. It has been shown that under some condition, perfect reconstruction of the information vector is impossible, as there will always be certain error. Specially, when the Bernoulli matrix is chosen as the measurement matrix, the corresponding lower bound and upper bound of the probability of error are given with a much neat and clear expression. The corresponding Cramer-Rao lower bound is also provided. These results provide some theoretical reference of the probability of error of compressive sensing.