A Theory of Super-Resolution from Short-Time Fourier Transform Measurements

While spike trains are obviously not band-limited, the theory of super-resolution tells us that perfect recovery of unknown spike locations and weights from low-pass Fourier transform measurements is possible provided that the minimum spacing, $\mathrm{\Delta }$, between spikes is not too small. Specifically, for a measurement cutoff frequency of $f_c$, Donoho [2] showed that exact recovery is possible if the spikes (on $\mathbb{R}$) lie on a lattice and $\mathrm{\Delta }>1\mathrm{/}{f}_c$, but does not specify a corresponding recovery method. Cand$\grave{\text{e}}$s and Fernandez-Granda [3, 4] provide a convex programming method for the recovery of periodic spike trains (i.e., spike trains on the torus $\mathbb{T}$), which succeeds provably if $\mathrm{\Delta }>2\mathrm{/}{f}_c$ and $f_c \geq 128$orif$\Delta > 1.26/f_c$and$f_c \geq 10^3$, and does not need the spikes within the fundamental period to lie on a lattice. In this paper, we develop a theory of super-resolution from short-time Fourier transform (STFT) measurements. Specifically, we present a recovery method similar in spirit to the one in [3] for pure Fourier measurements. For a STFT Gaussian window function of width $\sigma =1\mathrm{/}(4f_c)$ this method succeeds provably if $\Delta

1/f_c$,withoutrestrictionson$f_c$. Our theory is based on a measure-theoretic formulation of the recovery problem, which leads to considerable generality in the sense of the results being grid-free and applying to spike trains on both $\mathbb{R}$ and $\mathbb{T}$. The case of spike trains on $\mathbb{R}$ comes with significant technical challenges. For recovery of spike trains on $\mathbb{T}$ we prove that the correct solution can be approximated—in weak-* topology—by solving a sequence of finite-dimensional convex programming problems.