In this paper we develop a general theory of compressed sensing for analog signals, in close similarity to prior results for vectors in finite dimensional spaces that are sparse in a given orthonormal basis. The signals are modeled by functions in a reproducing kernel Hilbert space. Sparsity is defined as the minimal number of terms in expansions based on the kernel functions. Minimizing this number is under certain conditions equivalent to minimizing an atomic norm, the pre-dual of the supremum norm for functions in the Hilbert space. The norm minimizer is shown to exist based on a compactness argument. Recovery based on minimizing the atomic norm is robust and stable, so it provides controllable accuracy for recovery when the signal is only approximately sparse and the measurement is corrupted by noise. As applications of the theory, we include results on the recovery of sparse bandlimited functions and functions that have a sparse inverse short-time Fourier transform.
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, ( ), between spikes is not too small. Specifically, for a measurement cutoff frequency of (f_c ), Donoho (SIAM J Math Anal 23(5):1303–1331, 1992) showed that exact recovery is possible if the spikes (on ( R )) lie on a lattice and ( > 1 f_c ), but does not specify a corresponding recovery method. Candes and Fernandez-Granda (Commun Pure Appl Math 67(6):906–956, 2014; Inform Inference 5(3):251–303, 2016) provide a convex programming method for the recovery of periodic spike trains (i.e., spike trains on the torus ( T )), which succeeds provably if ( > 2 f_c ) and (f_c 128 ) or if ( > 1.26 f_c ) and (f_c 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 Candes and Fernandez-Granda (2014) for pure Fourier measurements. For a STFT Gaussian window function of width ( = 1 (4f_c) ) this method succeeds provably if ( > 1 f_c ), without restrictions on (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 ( R ) and ( T ). The case of spike trains on ( R ) comes with significant technical challenges. For recovery of spike trains on ( T ) we prove that the correct solution can be approximated—in weak-* topology—by solving a sequence of finite-dimensional convex programming problems.