Compressed Sensing for Analog Signals

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.