  While the recent theory of compressed sensing provides an opportunity to
overcome the Nyquist limit in recovering sparse signals, a solution approach
usually takes a form of inverse problem of the unknown signal, which is
crucially dependent on specific signal representation. In this paper, we
propose a drastically different two-step Fourier compressive sampling framework
in continuous domain that can be implemented as a measurement domain
interpolation, after which a signal 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 spectral domain, which shows that a
low-rank interpolator in the spectral domain can enjoy all the benefit of
sparse recovery with performance guarantees. Most notably, the proposed
low-rank interpolation approach can be regarded as a generalization 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 and the optimal
incoherence parameter. 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 FRI signals confirmed that the proposed low-rank interpolation approach has
significant better phase transition than the conventional CS approaches.
