A Caltech Library Service

A Tutorial on Fast Fourier Sampling [How to apply it to problems]

Gilnert, Anna C. and Strauss, Martin J. and Tropp, Joel A. (2008) A Tutorial on Fast Fourier Sampling [How to apply it to problems]. IEEE Signal Processing Magazine, 25 (2). pp. 57-66. ISSN 1053-5888.

See Usage Policy.


Use this Persistent URL to link to this item:


This article describes a computational method, called the Fourier sampling algorithm, that exploits this insight [10]. 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. This article describes in detail how to implement a version of Fourier sampling, it presents some evidence of its empirical performance, and it explains the theoretical ideas that underlie the analysis. Our hope is that this tutorial will allow engineers to apply Fourier sampling to their own problems. We also hope that it will stimulate further research on practical implementations and extensions of the algorithm.

Item Type:Article
Related URLs:
URLURL TypeDescription
Tropp, Joel A.0000-0003-1024-1791
Additional Information:© Copyright 2008 IEEE. Reprinted with permission. Posted online: 2008-03-21. The authors would like to thank Mark Iwen for his implementation and empirical analysis of AAFFT. AAFFT is publicly available and can be downloaded from We would also like to thank Sudipto Guha, Piotr Indyk, and Muthu Muthukrishnan for their collaboration on early versions of the Fourier sampling algorithm and its analysis [9]. We especially thank the editors of this special issue and the anonymous referees for helping us improve the exposition of this article.
Issue or Number:2
Record Number:CaltechAUTHORS:GILieeespm08
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10091
Deposited By: Archive Administrator
Deposited On:11 Apr 2008
Last Modified:03 Oct 2019 00:06

Repository Staff Only: item control page