A Tutorial on Fast Fourier Sampling

Authors

A.C. Gilbert, M.J. Strauss, J.A. Tropp

Year

2008

Journal Paper

Algorithm

Fast Fourier Sampling

Source

IEEE Signal Processing Magazine

Identifiers

DOI 10.1109/MSP.2007.915000

Abstract¶

This article describes a computational method, called the Fourier sampling algorithm. The algorithm takes a small number of (correlated) random samples from a signal and processes them efficiently to produce an approximation of the DFT of the signal. The algorithm offers provable guarantees on the number of samples, the running time, and the amount of storage. As we will see, these requirements are exponentially better than the FFT for some cases of interest.

Summary¶

Surveys fast Fourier sampling methods for recovering sparse or compressible frequency structure without computing a full transform. The tutorial frames sparse Fourier ideas as randomized sublinear algorithms for signal processing.