Leaner Fourier transforms
Bob Lawrence (VE1RLL)
Posts: 1,720
The fast Fourier transform, one of the most important algorithms of the 20th century, revolutionized signal processing. The algorithm allowed computers to quickly perform Fourier transforms fundamental operations that separate signals into their individual frequencies leading to developments in audio and video engineering and digital data compression.
But ever since its development in the 1960s, computer scientists have been searching for an algorithm to better it.
Last year MIT researchers Piotr Indyk and Dina Katabi did just that, unveiling an algorithm that in some circumstances can perform Fourier transforms hundreds of times more quickly than the fast Fourier transform (FFT).
Now Indyk, a professor of computer science and engineering and a member of the Theory of Computation Group within the Computer Science and Artificial Intelligence Laboratory (CSAIL), and his team have gone a step further, significantly reducing the number of samples that must be taken from a given signal in order to perform a Fourier transform operation.
Close to theoretical minimum
In a paper to be presented at the ACM-SIAM Symposium on Discrete Algorithms in January, Indyk, postdoc Michael Kapralov, and former student Eric Price will reveal an algorithm that can perform Fourier transforms using close to the theoretical minimum number of samples. They have also bettered even this, developing an algorithm that uses the minimum possible number of signal samples.
This could significantly reduce the time it takes medical devices such as magnetic resonance imaging (MRI) and nuclear magnetic resonance (NMR) machines to scan patients, or allow astronomers to take more detailed images of the universe, Indyk says.
The Fourier transform is a fundamental mathematical notion that allows signals to be broken down into their component parts. When you listen to someone speak, for example, you can hear a dominant tone, which is the principal frequency in their voice. But there are many other underlying frequencies, which is why the human voice is not a single tone, its much richer than that, Indyk says. So in order to understand what the spectrum looks like, we need to decompose the sounds into their basic frequencies, and that is exactly what the Fourier transform does.
The development of the FFT automated this process for the first time, allowing computers to rapidly manipulate and compress digital signals into a more manageable form. This is possible because not all of the frequencies within a digital signal are equal. Indeed, in nature many signals contain just a few dominant frequencies and a number of far less important ones, which can be safely disregarded. These are known as sparse signals.
In real life, often when you look at a signal, there are only a small number of frequencies that dominate the spectrum, Indyk says. So we can compress [the signal] by keeping only the top 10 percent of these.
Indyk and Katabis previous work focused on the length of time their algorithm needed to perform a sparse Fourier transform operation. However, in many applications, the number of samples the algorithm must take of the signal can be as important as its running time.
Applications in medical imaging, astronomy
One such example is in MRI scanning, Indyk says. The device acquires Fourier samples, basically snapshots of the body lying inside the machine, which it uses to recover the inner structure of the body, he says. In this situation, the number of samples taken is directly proportionate to the amount of time that the patient has to spend in the machine.
So by allowing the MRI scanner to produce an image of the body using a fraction of the samples needed by existing devices, it could significantly reduce the time patients must spend lying still inside the narrow, noisy machines.
The team is also investigating the idea of using the new sparse Fourier transform algorithm in astronomy. They are working with researchers at the MIT Haystack Observatory, who specialize in radio astronomy, to use the system in interferometry, in which signals from an array of telescopes are combined to produce a single, high-resolution image of space. Applying the sparse Fourier transform algorithm to the telescope signals would reduce the number of observations needed to produce an image of the same quality, Indyk says.
Thats important, he says, because these are really massive data sets, and to make matters worse, much of this data is distributed because there are several different, separated telescopes, and each of them acquires some of the information, and then it all has to be sent to the same place to be processed.
Whats more, radio telescopes are extremely expensive to build, so an algorithm that allows astronomers to use fewer of them, or to obtain better quality images from the same number of sensors, could be extremely important, he says.
News Source: http://web.mit.edu/newsoffice/2013/leaner-fourier-transforms-1211.html
Martin Strauss, a professor of mathematics, electrical engineering, and computer science at the University of Michigan, who develops fundamental algorithms for applications such as signal processing and massive data sets, says work by Indyk and others makes sparse Fourier transform algorithms advantageous over the celebrated FFT on a larger class of problems than before. The current paper squeezes out nearly all [of the performance] that is possible with these methods, he says.
But ever since its development in the 1960s, computer scientists have been searching for an algorithm to better it.
Last year MIT researchers Piotr Indyk and Dina Katabi did just that, unveiling an algorithm that in some circumstances can perform Fourier transforms hundreds of times more quickly than the fast Fourier transform (FFT).
Now Indyk, a professor of computer science and engineering and a member of the Theory of Computation Group within the Computer Science and Artificial Intelligence Laboratory (CSAIL), and his team have gone a step further, significantly reducing the number of samples that must be taken from a given signal in order to perform a Fourier transform operation.
Close to theoretical minimum
In a paper to be presented at the ACM-SIAM Symposium on Discrete Algorithms in January, Indyk, postdoc Michael Kapralov, and former student Eric Price will reveal an algorithm that can perform Fourier transforms using close to the theoretical minimum number of samples. They have also bettered even this, developing an algorithm that uses the minimum possible number of signal samples.
This could significantly reduce the time it takes medical devices such as magnetic resonance imaging (MRI) and nuclear magnetic resonance (NMR) machines to scan patients, or allow astronomers to take more detailed images of the universe, Indyk says.
The Fourier transform is a fundamental mathematical notion that allows signals to be broken down into their component parts. When you listen to someone speak, for example, you can hear a dominant tone, which is the principal frequency in their voice. But there are many other underlying frequencies, which is why the human voice is not a single tone, its much richer than that, Indyk says. So in order to understand what the spectrum looks like, we need to decompose the sounds into their basic frequencies, and that is exactly what the Fourier transform does.
The development of the FFT automated this process for the first time, allowing computers to rapidly manipulate and compress digital signals into a more manageable form. This is possible because not all of the frequencies within a digital signal are equal. Indeed, in nature many signals contain just a few dominant frequencies and a number of far less important ones, which can be safely disregarded. These are known as sparse signals.
In real life, often when you look at a signal, there are only a small number of frequencies that dominate the spectrum, Indyk says. So we can compress [the signal] by keeping only the top 10 percent of these.
Indyk and Katabis previous work focused on the length of time their algorithm needed to perform a sparse Fourier transform operation. However, in many applications, the number of samples the algorithm must take of the signal can be as important as its running time.
Applications in medical imaging, astronomy
One such example is in MRI scanning, Indyk says. The device acquires Fourier samples, basically snapshots of the body lying inside the machine, which it uses to recover the inner structure of the body, he says. In this situation, the number of samples taken is directly proportionate to the amount of time that the patient has to spend in the machine.
So by allowing the MRI scanner to produce an image of the body using a fraction of the samples needed by existing devices, it could significantly reduce the time patients must spend lying still inside the narrow, noisy machines.
The team is also investigating the idea of using the new sparse Fourier transform algorithm in astronomy. They are working with researchers at the MIT Haystack Observatory, who specialize in radio astronomy, to use the system in interferometry, in which signals from an array of telescopes are combined to produce a single, high-resolution image of space. Applying the sparse Fourier transform algorithm to the telescope signals would reduce the number of observations needed to produce an image of the same quality, Indyk says.
Thats important, he says, because these are really massive data sets, and to make matters worse, much of this data is distributed because there are several different, separated telescopes, and each of them acquires some of the information, and then it all has to be sent to the same place to be processed.
Whats more, radio telescopes are extremely expensive to build, so an algorithm that allows astronomers to use fewer of them, or to obtain better quality images from the same number of sensors, could be extremely important, he says.
News Source: http://web.mit.edu/newsoffice/2013/leaner-fourier-transforms-1211.html
Martin Strauss, a professor of mathematics, electrical engineering, and computer science at the University of Michigan, who develops fundamental algorithms for applications such as signal processing and massive data sets, says work by Indyk and others makes sparse Fourier transform algorithms advantageous over the celebrated FFT on a larger class of problems than before. The current paper squeezes out nearly all [of the performance] that is possible with these methods, he says.
Comments
So I suspect that with radar, sonar, and a few other substantial secrets, the teams of FFT calculators were very hush hush at that time.
Using active-sonar (pinging) became interpreted as an act of war at some point.
That's true of most everything. If I just read/listened here in the forum instead of making 10K+ smartarse posts, I'd be much smarter at this stage of the game.
But at least I am posting less and reading more that my early daze ... when I really did post way too much. The internet doesn't handle enthusiasm very well.
Regarding FFT...
While I understand that they are quite powerful and useful for tracking subs and airplanes, I just can't quite figure out a project that I would need them for. I really don't want to join any arms race or empower any superpower to flex its might.
China is attempting a moon landing today, but it really is more of a technological show of force... proving it can do what the USA and Russia have done. It is disheartening to see technology being so too faced. The truth is that the USA was able to put a man on the moon because it created a safe haven for hundreds of German engineers that were with the U2 program. And that was in response to Stalin's rocketry and Russia's space program.
And awful lot of innovation seems to be weapon systems first, and later evolve into public use.
I do suspect that faster MRI imaging is important. It seems that lung cancer diagnosis still requires CT scans as MRI are too slow. And it seems that while a single lung Xray is not a big radiation dose, a CT scan is something like 100 times the dose of a single Xray.
But I also fear that some country out there is going to jump on a faster FFT calculation for there submarines or fighter jet radar.
Imagine a Christmas tree that plays in LED synchronization the mood of songs like "Blue Christmas" or "Let It Snow"
I've considered making bar lighting effects products with FFT empowered micros.
BTW, there is a stark difference between a bar in the USA and a bar in Thailand
Here is a webpage from the Guys:
sFFT
And some codes as well.
Duane J
Yes, the topic is FFT. Another FFT application? Being able to isolate one speaker in a crowd. Use your imagination.
Its certainly the basis of much data compression, such as JPG, MPG...
One rather fascinating use of the FFT algorithm is in the Schonhage-Strassen integer multiply algorithm, asymptotically
the best multiply (and thus divide and reciprocal) for multi-precision arithmetic.
And these days we mustn't forget wavelet transforms, much more flexible and general than Fourier transforms. For instance
JPEG2000 uses wavelet compression in place of the DCT.
re:Here is a webpage from the Guys:
sFFT
And some codes as well.
Cool!! thanks.
What you are saying there is a very big thing if it's true because:
1) The Fast Fourier Transform is generally regarded as being unknown in the second world war having been discovered by John Tukey of Princeton in 1965.
2) Yes it was later discovered that Gauss had written about such a technique in 1805. And subsequently unrecognized.
3) An awful lot of the "secret" stuff going on by the Brits during WWII, code breaking etc, is now published. I have not heard mention of the FFT in there.
Thinking about it, having young girls calculate FFT by hand makes no sense for radar or sonar type applications, you would still be far away from any useful real-time operation. i.e. they will have completed calculating your FFT from radar data some days after the bombers had been over and bombed your city!
I wonder what she was really talking about?
As far as the these other techniques and the Propeller are concerned, is their code size small enough to fit in the COG?
As soon as you have to shift work out of COG space you might be losing any performance benefits they may have.
Well, it is true that I met this lady while carrying a text about FFT and she did make these claims. I can't vouch for whether she was lying or telling the truth or that my memory of events is not quite right. It was about 1983-4.
But it did make sense that she had worked with FFT as an awful lot of people that are adept in classical music have above average skills and knowledge in maths. She certain did seem to know more than I did.
It would not be the first time I ran into a glimpse of something that was supposed to be 'top secret'. And maybe not the last. It certainly is interesting that before 1965, nobody was supposed to have known about them.
Due to WWII, the USA and UK stopped all development on television. The video screen was apparently used for military radar on our side and while the Germans had radar... theirs was more crude.. used mainly for fire control in fixed gun emplacements.
Governments would not be any fun if they told us all and everything, would they?
Could it be that she was doing calculations for Loran navigational maps as another application? I begin to wonder if I imagined that the story took place in WWII in the UK. She may have been at a US university or something and much later.
Curious. She wouldn't happen to still be alive somewhere would she?
Those young girls doing calculations in those times were called "computers". After all that is what they did. Often they had no idea about the maths behind the calculations they were doing or even what they were for. They just followed whatever algorithmic steps they were given.
So this lady must have been something more than that.
It does seem that she did follow steps of some sort. But she happened to know the maths was FFTs.
that has something to say. Maybe the application would be spatial transforms relating to aerial
arrays and perhaps phased arrays and their design? The history of x-ray crystallography must also
be pertinent.
(*) It describes the meeting at which the British engineers first revealed the magnetron to the US
engineers, and the rather inciteful comment by one of the latter that "Ah! It's a whistle".
The Fourier transform, and many others related to it, are basically summations of many sine wave of different frequency, phase, and amplitudes.
But, there was another, more obscure, transform that can generate similar results by the summations of many repeating number sequences.As I recall it was named after a guy in the early 1800s. One could call it digital but was devised much before digital methods could be done.
I remember an article in early issues of Byte Magazine.
Anyone recall what this was called?
I searched for alternates to Fourier but had no luck or didn't recognize what I was looking at.
Thanks.
Duane J
Another orthogonal transform is the Walsh-Hadamard transform that can be implemented with additions and subtraction, and no multiplications. There is the Haar transform, which is something like a sparse version of the Walsh-Hadamard transform. And then there is the Discrete Cosine Transform (DCT), which is used in JPEG and the various H.26x and MPEG standards.
see this
" Attached is a DTMF input demo I did awhile back that uses the Goertzel algorithm to detect the tones. It includes an Excel worksheet for computing the bandwidth of the filters.
http://en.wikipedia.org/wiki/Goertzel_algorithm
-Phil
http://forums.parallax.com/showthread.php/119568-Propeller-DTMF?p=876749#post876749"