Indexed on: 25 Jan '16Published on: 25 Jan '16Published in: Computer Science - Information Theory
While the recent theory of compressed sensing or compressive sampling (CS) provides an opportunity to overcome the Nyquist limit in recovering sparse signals, a recovery algorithm usually takes the form of penalized least squares or constraint optimization framework that is crucially dependent on the signal representation. In this paper, we propose a drastically different two-step Fourier CS framework that can be implemented as a measurement domain data interpolation, after which the image reconstruction can be done using classical analytic reconstruction methods. The main idea is originated from the fundamental duality between the sparsity in the primary space and the low-rankness of a structured matrix in the reciprocal spaces, which shows that the low-rank interpolator as a digital correction filter can enjoy all the benefit of sparse recovery with performance guarantees. Most notably, the proposed low-rank interpolation approach can be regarded as a generation of recent spectral compressed sensing to recover large class of finite rate of innovations (FRI) signals at near optimal sampling rate. Moreover, for the case of cardinal representation, we can show that the proposed low-rank interpolation will benefit from inherent regularization. Using the powerful dual certificates and golfing scheme, we show that the new framework still achieves the near-optimal sampling rate for general class of FRI signal recovery, and the sampling rate can be further reduced for the class of cardinal splines. Numerical results using various type of signals confirmed that the proposed low-rank interpolation approach has significant better phase transition than the conventional CS approaches.