A Fast and Accurate Reconstruction Algorithm for Compressed Sensing of Complex Sinusoids

The standard compressed sensing (CS) theory reconstructs a signal by recovering a sparse representation of the signal over a pre-specified dictionary. For CS of complex sinusoids, this dictionary is usually set to be a DFT matrix corresponding to a uniform frequency grid. However, such a setting can make conventional CS reconstruction methods degrade considerably, since component frequencies of practical signals do not necessarily align with the specified grid. To deal with this problem, we apply a linear approximation to the true unknown dictionary and establish a more accurate model for sparse approximation of practical complex sinusoids. Based on this model, signal reconstruction is reformulated as a problem that recovers two sparse coefficient vectors over two known dictionaries under the constraint that the vectors share the same support. To solve such a problem, we develop a fast iterative algorithm under a variational Bayesian inference framework. Results of extensive numerical experiments demonstrate that the algorithm can achieve CS of complex sinusoids with low computational cost as well as high reconstruction accuracy.