|Introduction. Definition of the Fourier transform, both the Discrete Fourier Transform (DFT) and Walsh-Hadamard transform (WH). |
Presentation of the FFT for DFT by Cooley and Tukey (1967) and the so-called WH transform (for WH), buth running in O(n log n) time.
List of examples of where DFT/WH are used in computer science and signal processing.
|Morgenstern's lower bound for computation of the (unnormalized) FT, and shortcomings of the result.|
Pan's lower bound, assuming "synchronicity" of the underlying algorithm.
Jacques Morgenstern. Note on a lower bound on the linear complexity of the fast Fourier transform. J. ACM, 20(2):305–306, April 1973.
|Papadimitriou's lower bound|
Christos H. Papadimitriou. 1979. Optimality of the Fast Fourier transform. J. ACM 26, 1 (January 1979), 95-102. DOI=http://dx.doi.org/10.1145/322108.322118
|Ailon's lower bound for FT|
A Lower Bound for Fourier Transform Computation in a Linear Model Over 2x2 Unitary Gates Using Matrix Entropy. Chicago J. Theor. Comput. Sci. 2013 (2013)
An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model. TOCT 8(1): 4:1-4:14 (2016)
|"Nearly Optimal Sparse Fourier Transform"|
Hassanieh, Indyk, Katabi, Price
Tomorrow I will start talking about the exciting subject of "sparse Fourier transform".
We have prior knowledge that a signal is sparse in the frequency domain, and we want to both find the support (in the frequency domain) and the energy, phase of each nonzero frequency.
All of this in sub-linear time.
I will talk about the EXACTLY sparse case only, based on this paper:
"Nearly Optimal Sparse Fourier Transform" (Hassanieh, Indyk, Katabi, Price).
In the same paper, the authors also discuss the "approximately sparse" case, which is
more realistic, and requires a bit more work to prove. If you are looking for a project, the "approximately sparse" case is a good option.