Computational Resolution Limit: Theory and Algorithm

Given an image that is generated by the convolution of point sources with a band-limited function, the deconvolution problem is to reconstruct the source number, position, and amplitude. This problem arises from many important applications in imaging and signal processing, and there are many interesting results available. However, the theoretical understanding of the problem is far from complete. The aim of this paper is to provide an attempt. We propose the concept of computational resolution limit on the separation distance between the sources such that the exact recovery of source number is possible in the presence of noise. We derived a sharp upper bound on the resolution limit. Our result reveals the importance of the sparse of sources on the ill-posedness of the deconvolution problem. Stability results for recovering the source position are further derived when the separation distance is beyond our upper bound. Moreover, we propose a new MUSIC-type algorithm to recover the source number. It performs well even in the case when the separation distance of sources is close to the resolution limit. The proof of our results is based on a multipole expansion method and a novel non-linear approximation theory in Vandermonde space. These results paved the way to a mathematical theory of super-resolution which will be addressed in a forthcoming paper.