Imaging with highly incomplete and corrupted data

We consider the problem of imaging sparse scenes from a few noisy data using an ℓ₁-minimization approach. This problem can be cast as a linear system of the form Ap = b, where A is an N × K measurement matrix. We assume that the dimension of the unknown sparse vector p ϵ ℂ^k is much larger than the dimension of the data vector b ϵ ℂ^N, i.e. K Gt; N. We provide a theoretical framework that allows us to examine under what conditions the ℓ₁-minimization problem admits a solution that is close to the exact one in the presence of noise. Our analysis shows that ℓ₁-minimization is not robust for imaging with noisy data when high resolution is required. To improve the performance of ℓ₁-minimization we propose to solve instead the augmented linear system [A|C]p = b, where the N × σ matrix C is a noise collector. It is constructed so as its column vectors provide a frame on which the noise of the data, a vector of dimension N, can be well approximated. Theoretically, the dimension σ of the noise collector should be e^N which would make its use not practical. However, our numerical results illustrate that robust results in the presence of noise can be obtained with a large enough number of columns σ ≺∼ 10K.