Time-data trade-off in the sparse Fourier transform

Abdulmalik Aldharrab, Michael Davies

Research output: Contribution to conferencePaperpeer-review

Abstract / Description of output

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.
Original languageEnglish
Publication statusPublished - 28 Aug 2017
Event 25th European Signal Processing Conference (EUSIPCO) 2017 - Kos, Greece
Duration: 28 Aug 20172 Sept 2017


Conference 25th European Signal Processing Conference (EUSIPCO) 2017
Internet address


Dive into the research topics of 'Time-data trade-off in the sparse Fourier transform'. Together they form a unique fingerprint.

Cite this