Tuesday, May 1, 2012

The possible effects of a faster Fourier Transform


This weekend my friend Ryan sent me a link to a note in technology review where they talked about a group of researchers at MIT who showed off a new algorithm to speed up the calculation of the Fast Fourier Transform (FFT), FFT is a method to decompose a signal in a sum of sines and cosines of different frequencies, allowing to study the signal itself or to compress the information carried by it. A famous example of its application is with music because the MP3 is the end result of a FFT. I have to admit that I was really surprised about the MIT development and I looked for other notes or papers about it, and I found this IEEE spectrum note where they talk a little bit more about the results the group has achieved. The basic idea of the new algorithm is to exploit the fact that some signals are “sparse”, i.e. they contain just a relatively small number of frequencies components that are significant and therefore the number of operations needed to calculate the FFT can be reduced considerably for this kind of signals.

Certainly there are a lot of applications where the traditional FFT will be still needed, but we can think of a lot of examples where the sparse FFT will be of use since a lot of phenomena are sparse in frequency such as the sound of your guitar (every chord is adjusted to an specific frequency actually), the wave propagation (A wave has normally just a small number of dominant frequencies),  and even we can study images as 2 dimensional signals with a sparse frequency content. Even though we will have to wait until the paper describing the algorithm is published, we already can imagine several fields that could benefit from this new technique in terms of speed and  even the amount of energy required in certain applications.

Imagine the improvement of having a faster algorithm for sparse signals in Particle Image Velocimetry (PIV), which is a technique researchers use to see and study the streamlines of a fluid using really small particles inside it, called tracers, and by comparing the average movement of those particles in consecutive images it is possible to estimate the instantaneous velocities in the fluid. Not one but several FFT must be calculated in order to estimate the velocity of the particles in the fluid for a single image pair, causing the PIV speed to depend almost directly on the time the FFT needs to be calculated. Since the PIV images are normally captured in such way that just the particles are visible whilst the fluid appears as part of the background, those images are likely to present just a small number of dominant frequencies and the use of the sparse FFT will result in faster PIV sensors. Those faster PIV sensors may also result in other improvements like PIV control for high speed fluids allowing researches to come up with new experiments that right now are not feasible.

It is easy to understand that less calculations needed for the FFT will result in less computation power needed and therefore the devices used to process large data series, like the meteorological or oceanographic data, will be able to crunch even more data than they actually do using the same computational power which may result in faster models for example. Weather prediction algorithms, for instance, may get more complicated since the data processing needed to feed the forecast may require less computations with sparse FFT.

We don’t know yet if the sparse FFT will also result in an increase of speed for the inverse FFT or if the quality of the reconstruction of the original signal won’t be diminished, but if we assume that, we could expect also positive effects in the video and audio stream systems since the data compression may be better without losing quality or definition, allowing the end users to receive smaller data packages that will reconstruct a high quality song or video. Even with music players, if the sparse FFT can be used to compress and reconstruct audio data without losing quality, we may find in the future music players that are even smaller and have longer battery life without sacrificing the quality of our musical experience since an increase in the speed of the FFT and its inverse will result in less computations needed and therefore less hardware and less energy consumption.

We don’t know yet for sure the exact effect of this new algorithm in the technology, but as the FFT is used in almost any device processing or transmitting data right now we can predict for sure that sparse FFT will boost some research fields and will motivate improvements in some devices or technologies that we use day to day.  This may be a small snow ball that will end up transformed in a huge snow slide in the upcoming months or years.

No comments:

Post a Comment