M. F. Duarte and R. G. Baraniuk, "Spectral Compressive Sensing," preprint, 2011.

Abstract:  Compressive sensing (CS) is a new approach to simultaneous sensing and compression of sparse and compressible signals based on randomized dimensionality reduction. To recover a signal from its compressive measurements, standard CS algorithms seek the sparsest signal in some discrete basis or frame that agrees with the measurements. A great many applications feature smooth or modulated signals that are frequency sparse and can be modeled as a superposition of a small number of sinusoids. Unfortunately, such signals are only sparse in the discrete Fourier transform (DFT) domain when the sinusoid frequencies live precisely at the center of the DFT bins. When this is not the case, CS recovery performance degrades significantly. In this paper, we introduce a suite of spectral CS (SCS) recovery algorithms for arbitrary frequency sparse signals. The key ingredients are an over-sampled DFT frame, a signal model that inhibits closely spaced sinusoids, and classical sinusoid parameter estimation algorithms from the field of spectral estimation. Using periodogram and line spectral estimation methods (specifically Thomson’s multitaper method and root MUSIC), we demonstrate that SCS recovery significantly outperforms current state-of-the-art CS algorithms based on the DFT while providing provable bounds on the number of measurements required for stable recovery.

An example from the paper (Figure 3) illustrating the efficacy of SCS.  Experimental setup:  M = 300 noiseless random measurements of a signal of length N = 1024 composed of K = 20 complex-valued sinusoids with arbitrary real-valued frequencies. We compare the frequency spectra obtained from redundant periodograms of (a) the original signal and its recovery using (b) root MUSIC on M signal samples (SNR = 0.65dB), (c) standard CS using the orthonormal DFT basis (SNR = 5.3dB), (d) standard CS using a 10x zero-padded, redundant DFT frame (SNR = -4.4dB), (e) SCS using Algorithm 1 from the paper (SNR = 23.8dB), and (f) SCS using Algorithm 3 from the paper (SNR = 23.6dB). A software toolbox for SCS is available here.