Time-data trade-off in the sparse Fourier transform

It has been shown that the Discrete Fourier Transform (DFT) can be computed in sublinear time from a sublinear number of samples when the target spectrum is sparse. However, this is usually only expressed qualitatively in terms of the order of number of computations/samples. Here we investigate the explicit time-data tradeoff for the Sparse Fourier Transform (SFT) algorithm proposed by Pawar and Ramchandran using coding theoretic tools. This leads to an optimal oversampling rate and algorithm configuration that minimises computation while keeping the required number of time domain samples close to the minimum value.