Computational Lower Bounds for the Fourier Transform

The Fourier Transform is one of the most important linear transformation in engineering and science with applications in virtually every domain. In 1964, Cooley and Tukey discovered the Fast Fourier Transform (FFT) algorithm, which computes the transformation in time O(n log n) for a signal in n-dimensions.In spite of its importance, not much is known about lower bounds.

I will show that if you speed up FFT in a machine of finite precision (say, 32 or 64 bits) using linear operations only (multiplications and additions), then there exist Omega(n) orthogonal directions in input space that either overflow (exceed the machine's numerical upper limit) or underflow (exceed the machine's precision) at some point during the computation. A quantitative tradeoff between the speedup factor and the resulting numerical abuse will be presented.

The main technical tool is definition of a potential function for matrices M based on a function that looks a lot like Shannon entropy over the numbers M(i,j)M^{-1}(j,i). Summing these number over j (for fixed i) gives 1 by matrix inverse definition, but they may be negative or >1, hence we call them "quasi-probabilities", and accordingly the potential function "quasi-entropy".