Compressive sensing of a superposition of pulses

Compressive Sensing (CS) has emerged as a potentially viable technique for the efficient acquisition of high-resolution signals and images that have a sparse representation in a fixed basis. The number of linear measurements M required for robust polynomial time recovery of S-sparse signals of length N can be shown to be proportional to S logN. However, in many real-life imaging applications, the original S-sparse image may be blurred by an unknown point spread function defined over a domain Ω; this multiplies the apparent sparsity of the image, as well as the corresponding acquisition cost, by a factor of |Ω|. In this paper, we propose a new CS recovery algorithm for such images that can be modeled as a sparse superposition of pulses. Our method can be used to infer both the shape of the two-dimensional pulse and the locations and amplitudes of the pulses. Our main theoretical result shows that our reconstruction method requires merely M = O(S + |Ω|) linear measurements, so that M is sublinear in the overall image sparsity S|Ω|. Experiments with real world data demonstrate that our method provides considerable gains over standard state-of-the-art compressive sensing techniques in terms of numbers of measurements required for stable recovery.