Reducing Samples for Fourier Transforms
One of the most important algorithms discovered last century was the fast Fourier Transform, or FFT. With it a computer can quickly decompose a signal into its distinct frequencies, and that ability has made many other technologies possible. Now researchers at MIT have finally found a new algorithm that can perform Fourier Transform better than FFT.
Last year the researchers revealed an algorithm that could outperform FFT by hundreds of times, in some situations, and now they have improved it by reducing the necessary number of samples it needs. What that means is that the new algorithm can perform the Fourier Transform with less information than typically required. It is still not at the theoretical minimum number of samples, but is still a large step forward.
Technologies that could potentially benefit from this new algorithm include MRI machines and radio telescopes. Both rely on taking multiple Fourier samples and processing them together, to form a complete image. By reducing the number of samples taken, the time spent in an MRI machine or the number of telescopes being used could also be reduced.