Science

Faster Fast Fourier Transform found

A group of MIT researchers recently presented their findings regarding an improved algorithm for Fast Fourier Transforms.

Faster Fast Fourier Transform found

Researchers at MIT have discovered a new method of performing the Fast Fourier Transform algorithm which, in a large set of use cases, adds performance improvements. The MIT group submitted their paper, “Nearly Optimal Sparse Fourier Transform” to ArXiv on 12 January and presented their findings in the Symposium on Discrete Algorithms (SODA) last week.

The Fourier Transform is a popular means of mathematical analysis which decomposes functions into their constituent frequencies. The Discrete Fourier Transform (DFT) is a realisation of this as an algorithm which takes a sequence of real or complex numbers to process information stored in computers, with uses in academic areas in Computer Science and mathematics. The Fast Fourier Transform (FFT) is a set of algorithms which are able to efficiently compute the DFT in a significantly faster time. FFTs have been hailed as the Swiss Army Knife of algorithms, with wide ranging applications in graphics (image processing, filters), digital signal processing (reconstructing a signal from frequency data), compression, optics, crystallography and data searching.

FFTs work by performing a variety of optimisations on the DFT. Speeding up elements within the summation equation, such as the amount of multiplication operations involved, allows for reduced processor usage during the algorithm’s execution. This increases efficiency significantly, but there is no known proof which dictates the FFT is the fastest algorithm for computing the DFT. Renowned MIT mathematician Gilbert Strang has described the FFT as the “most important algorithm of our generation”.

The MIT researchers’ new algorithm, coined the Sparse Fourier Transform (sFFT), improves on the FFT by considering a signal to be a product of narrower slices of bandwidth. With this, the signals are treated as oscillations rather than binary up/down directions, and the same slice of bandwidth can be sampled at different times to better determine where the dominant frequencies are. This strategy, notable for its use in 4G cellular networks, allows for sparse (heavily weighted) frequencies to be identified faster. As a result, the algorithm’s worst case efficiency is equivalent to the FFT, but the average case is an improvement for many general input signals.

The sFFT algorithm, developed by two professors from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) along with their students, has been described by Professor Martin Strauss from the University of Michigan as “greatly [expanding] the number of circumstances where one can beat the traditional FFT”.

From Issue 1509

3rd Feb 2012

Discover stories from this section and more in the list of contents

Explore the edition

Read more

Peter Haynes to take over Provost role in October

News

Peter Haynes to take over Provost role in October

Professor Peter Haynes has been appointed as the new Provost and Deputy President of Imperial College. The current  Vice-Provost for Education and Student Experience, Haynes will succeed the outgoing Provost, Professor Ian Walmsley, who has served in the role since 2018. Imperial President Hugh Brady said Professors Haynes and Walmsley

By Guillaume Felix
Why RAG’s bungee jump event never took place

News

Why RAG’s bungee jump event never took place

Earlier this academic year, Imperial Raising and Giving (RAG), had announced the return of their charity bungee jump after a hiatus of 10 years. The event, however, was postponed several times, and Felix can now reveal why it was cancelled. The event, initially scheduled for November 13th, was postponed several

By Mohammad Majlisi and Nadeen Daka
Palestine protests ramp up as year ends and tensions rise

News

Palestine protests ramp up as year ends and tensions rise

Saturday 7th June: Pro-Palestinian protestors hold banners as they stand on ALERT at the Great Exhibition Road Festival. Tuesday 10th June: A student announces a hunger strike asking for Imperial to investigate Islamophobia and anti-Arab racism, form a student-staff working group on ethical investment, and divest from arms companies accused

By Mohammad Majlisi