Information-theoretic analysis of support recovery from sparsely corrupted measurements

This paper studies the recovery of the support of sparse signal that is corrupted by both dense noise and gross error. The gross error is an unknown sparse vector whose nonzero entries maybe unbounded. This setup covers a wide range of applications, such as face recognition, inpainting and sensor networks. We derive the information-theoretic lower bounds on the sampling rate required to obtain a desired error rate, which depend on the properties of both the signal and the gross error. The investigations are given in the high-dimensional setting. Some illustrations are provided to further reveal the relationship of these bounds.