Computational resolution limit: a theory towards super-resolution

Abstract

Given an image generated by the convolution of point sources with a band-limited function, the deconvolution problem is to reconstruct the source number, positions, and amplitudes. Rayleigh investigated the limit of this problem and formulated the Rayleigh limit, for the case of two sources with identical amplitudes. On the other hand, many numerical experiments demonstrate that a stable recovery of the sources is possible even if the sources are separated below the Rayleigh limit. This is so-called "super-resolution". In this paper, a new mathematical theory for super-resolution will be developed. The theory will address the issue when one can recover the source number exactly. The key is a new concept "computational resolution limit" which is defined to be the minimum separation distance between the sources such that exact recovery of the source number is possible. This new resolution limit is determined by the signal-to-noise ratio and the sparsity of sources, in addition to the cutoff frequency of the image. Sharp upper bound for this limit is derived, which reveals the importance of the sparsity as well as the signal-to-noise ratio to the recovery problem. The stability for recovering the source positions is further derived when the separation distance is beyond the upper bound. Moreover, a MUSIC-type algorithm is proposed to recover the source number and to verify our theoretical results on the computational resolution limit. Its performance in the super-resolution regime when the sources are separated below the Rayleigh limit is analyzed both theoretically and numerically. The results are based on a multipole expansion method and a novel non-linear approximation theory in Vandermonde space.

Tasks

Reproductions