ORIGINATOR
John Daugman

DETAILS OF PROJECT
Existing Fast Fourier Transform algorithms (such as the butterfly, Cooley-Tukey) in the general case handle complex-valued data. When the data are purely real-valued, as with acoustical signals or images, important simplifications are possible because of Hermitian (conjugate) symmetry: The Fourier Transform of real-valued only data has a real part which is even-symmetric and an imaginary part which is odd-symmetric. These symmetries in the Fourier domain are exploited in special versions of the FFT when dealing with real-valued inputs, such as the DCT (Discrete Cosine Transform) which is the standard for JPEG image compression.

When transforming higher-dimensional data, such as a video sequence digitized in three dimensions (two in space and one in time), the normal FFT has a complexity of order O(N^{3}log{N}) where N is the number of pixels (as opposed to a size dependence of O(N^{6}) without FFT). This project will seek to develop variants of the FFT for data in three dimensions (or more) which exploit the following simplifications to maximize the algorithms' computational efficiency:

• the input data are purely real-valued (equally imaginary), rather than complex-valued;

• the input data are purely positive, as in the case of image pixel values from a CCD (light being only positive);

• the input data are purely integers, as with sampled acoustical or image pixel values, rather than floating-point values.