Being able to compute the Fourier transform of an input signal is crucial in photonics—for example, in determining the spatial frequencies in an image. The standard method of computing a discrete Fourier transform (DFT) is by using the fast Fourier transform (FFT) algorithm. However, algorithms faster than the FFT would be desirable. Researchers at the Massachusetts Institute of technology (Cambridge, MA) have developed two algorithms that are faster than the FFT for all sparse signals. (A sparse signal is one in which some of its Fourier coefficients are near enough to zero that they can be ignored.) While other algorithms have previously been developed to improve on the FFT for sparse signals, none of them have improved on the FFT’s runtime for the whole range of sparse signals.
For a signal with k nonzero Fourier coefficients, and a length n of the input signal that is a power of 2, the researchers show two new DFT algorithms. The first is an O(k log n)-time algorithm for the exactly k-sparse case (where k is small). (O means “on the order of.”) The second is an O(k log n log(n/k))-time algorithm for the general case. In contrast, the FFT computes the DFT in O(n log n) time. Contact Haitham Hassanieh at [email protected].
