Measurement Bounds for Compressed Sensing with Missing Data

In this paper, we study the feasibility of the exact recovery of a sparse vector from its linear measurements when there are missing data. For this setting, the random sampling approach employed in compressed sensing is known to provide excellent reconstruction accuracy. However, when there is missing data, the theoretical guarantees associated with the sparse vector recovery have not been well studied. Therefore, in this paper, we derive an upper bound on the minimum number of measurements required to ensure faithful recovery of a sparse signal when the generation of missing data is modeled using an erasure channel. We show that the number of measurements required scales as-[log(1-p + Cp)]^-1 to overcome the missing data with arbitrarily high probability, where p is the probability of observing (not missing) a measurement and 0 < C < 1 is a constant that depends on the properties of the measurement matrix and the recovery algorithm. Our analysis is based on the restricted isometric property of the measurement matrix whose entries as well as the dimension are random.