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