A Tutorial on Fast Fourier Sampling [How to apply it to problems]
Abstract
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.
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 http://www-personal.umich.edu/~markiwen/WebPage/AAFFT.tgz. 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.Files
| Name | Size | Download all |
|---|---|---|
|
md5:9701105c8ec70d1ccde6a0fcf5fd254f
|
1.3 MB | Preview Download |
Additional details
- Eprint ID
- 10091
- Resolver ID
- CaltechAUTHORS:GILieeespm08
- Created
-
2008-04-11Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field