Super-resolution, subspace methods, and non-harmonic Fourier matrices

This talk is concerned with the super-resolution problem of recovering a discrete measure on the torus consisting of S atoms, given M consecutive noisy Fourier coefficients. Super-resolution recovery is sensitive to noise when the distance between two atoms is less than 1/M and many algorithms fail in this regime. In this talk, we connect this problem to the minimum singular value of non-harmonic Fourier matrices. New results for the latter are presented, and as consequences, we derive results regarding the super-resolution limit of subspace methods (namely, MUSIC and ESPRIT). These results rigorously establish the super-resolution phenomena of these algorithms that were empirically discovered long ago, and numerical results indicate that our bounds are sharp or nearly sharp. Information theoretic lower bounds imply that both algorithms are near optimal for super-resolution. Time permitting, we will discuss how to quantize the Fourier measurements using distributed beta encoding in order to minimize the reconstruction error using either convex or subspace methods. Joint work with Albert Fannjiang, Sinan Gunturk, and Wenjing Liao.