Faster-Than-Fast Fourier Transform

First time accepted submitter CanEHdian writes "MIT news reports on research done resulting in a Faster-than-fast Fourier Transform algorithm. 'At the Association for Computing Machinery's Symposium on Discrete Algorithms (SODA) this week, a group of MIT researchers will present a new algorithm that, in a large range of practically important cases, improves on the fast Fourier transform. Under some circumstances, the improvement can be dramatic — a tenfold increase in speed. The new algorithm could be particularly useful for image compression, enabling, say, smartphones to wirelessly transmit large video files without draining their batteries or consuming their monthly bandwidth allotments.'"

Comments

Can it be done effectivly without an FPU?

[Anonymous Coward]

One of the things that might be cool to do with this is use it to do DSP with Arduino and similar processors. However, being very simple, they don't have a math coprocessor and are somewhat slow at floating point math. Anything to help improve that would be a boon.

Re:Can it be done effectivly without an FPU?

[rev0lt]

While I do argue with your point, there are a ton of devices that would benefit from it. Why do you think the implementations of FFT for 8/16-bit microcontrollers such as the 8051 are so popular? DSPs are popular in applications that make heavy use of FFT, but there are a ton of general purpose implementations that require FFT algoritms, ranging from multitone generation/decoding to D/A conversion. Why should I use 2 ICs (plus assorted external logic) on a given circuit, if I can easily do it in software on my general-purpose microcontroller, that besides the integrated ram and rom, also bundles me with a serial port, multiple I/O ports and a ton of "extra" features, at a fraction of the price?

Re:Can it be done effectivly without an FPU?

[mikael_j]

Well, if for some reason someone is already using Arduino boards to do a bunch of stuff it might make sense if it was just fast enough. But yeah, if you have a choice it doesn't make much sense to pick an Arduino for this task.

So far the only "usefulness" I've seen in the Arduino has been for that retro kick, being artificially limited to the kind of environment I haven't had to work in for a long time, but if I wanted to build something useful I'd probably at least want a 16-bit processor these days, the difference in price is negligible for any hobby project (hell, a 32-bit processor probably wouldn't be a major budget concern considering what you're likely to spend on the rest of your hardware when building something)...

Re:Can it be done effectivly without an FPU?

[rev0lt]

Not every FFT implementation is floating-point (I believe fixed-point implementations are quite more common than floating-point ones), and software-based floating point is not "somewhat slow", is "slow as hell". For many applications, fixed-point and good ol' lookup tables (either complete tables or sample points with interpolation) do the trick rather well.

Re:Can it be done effectivly without an FPU?

[dintech]

The Spectrum Analyser. This is one of the most common uses is staring you right in the face in almost every mp3 player.

The interesting thing is that the greater time window over which the FFT operates, you can observe finer frequency detail within that particular window at the expense of how quickly the graph or bars change over time (in simplistic terms). I wonder how this new algo will change the frequency detail/transient time detail trade-off. Do we see more detail in both domains? Less? The same?

Re:Can it be done effectivly without an FPU?

[Anonymous Coward]

A year ago, there was still easily an order of magnitude difference in price going from AVR to 32-bit microcontroller land in base deve hardware alone. You say that for one hobby item the price difference (say $10 --->$100) is neglible, because they are both smallish numbers relative to income... 1) You need to learn multiplication 2) A lot of hobbyists have the desire to do their own version of "ubiquitous" computing.. Your "negligible" price difference theory breaks down in all the cases I'm familiar with.

And please spare me with examples of ultra cheap 32-bit systems, which I know always exist at any given moment. I still remember that time when the TI eval robot had a leaked promo code. That thing took down TIs website and then of course was promptly gone... When assisting a local youth group with a robotics project I looked at numerous "inexpensive" ARM options, only to find that at any given time product availability in this domain is *inconsistent*. Say what you will, but there is almost always an Arduino clone around, and if you fry it, you don't care. If you get a special on a 32-bit ARM system, good luck buying another in 3 months.

In my business, if you absolutely *NEED* a dev board you must still be prepared to pay $300-1000 bucks for the base board alone. I'm a day-job embedded product designer that also works with hobbyists at a hackerspace, so I am not hung up on any one usage and I can tell anybody that thinks that AVRs are irrelevant are still full of shit.. Where is your raspberry pi available for sale, fucker?

Re:Can it be done effectivly without an FPU?

[SuricouRaven]

It's more than a property of the DFT - it's a much deeper mathematical truth than that. The same fundamental mathematics is used to derive the uncertainty princible in quantum mechanics: For a signal to be perfectly defined in frequency it must be infinite in time, and vice versa. When you apply the same to quantum wave-functions... the uncertainty limit isn't a limit on measurements. It's a limit on what the universe is capable of representing.

Re:Can it be done effectivly without an FPU?

[introcept]

Do you have math showing the compression consumes less power than just transmitting the raw data?

Lots of it, the power budget drives the design of the entire sensor.
The micro-controller uses a lot less energy than the packet radio so it makes sense to process the raw sensor data on-board and transmit information such as fourier coefficients, integrals and other statistics. Every packet saved is another fraciton of a second the radio can be powered down.

It's a fairly common technique with sensor networks to process raw signals at the point of collection and transmit only the useful information, it makes the most use of your bandwidth and in this case energy.

Re:Can it be done effectivly without an FPU?

[ortholattice]

the uncertainty limit isn't a limit on measurements. It's a limit on what the universe is capable of representing.

Only partially true. What many people don't know is that Heisenberg's derivation was slightly wrong because while it modeled the thing being measured with quantum mechanics, it incorrectly modeled the measuring device classically.

A rigorous analysis using qm for both was done Ozawa in 2003 (see http://arxiv.org/abs/1201.1833 which shows the correct uncertainty equations on p. 2).

From http://www.sciencedaily.com/releases/2012/01/120116095529.htm "In order to describe the fundamental uncertainty and the additional disturbance due to the measuring process, both particle and measurement device have to be treated in the framework of quantum theory,...But the product of error and disturbance can be made arbitrarily small -- even smaller than Heisenberg's original formulation"

Doesn't sound THAT useful

[tempmpi]

It doesn't improve the regular FFT but only sparse variants. Image or Audio compression nearly always uses the regular non-sparse FFT.

Re:Doesn't sound THAT useful

[Anonymous Coward]

The paper claims the opposite: "Images and audio data are equally sparse. This sparsity provides the
rationale underlying compression schemes such as MPEG and JPEG."

Re:Doesn't sound THAT useful

[Anonymous Coward]

I'm only awake due to a bathroom break, so I may not be the most clear-minded at the moment, but subtracting coefficients from the bins seems like a pretty obvious permutation of algorithmic techniques to try, and having 2/3 probability of a correct FT analysis doesn't seem like an inspiring trade-off (skimmed... perhaps they explain ways to improve this?) Is this anything more than a highly specialized, not particularly practical version of the algorithm? I'm used to working on algorithms which are much more general-case (e.g., new solutions for SCALAPACK problems).

Wish I could understand the details of FFTs

[Viol8]

I'm sure I'm not the only person who completely understands what a FFT does but simply can't get his head around the actual implementations details. I simply don't get how a signal of many mixed frequencies which essentially means the amplitude is moving all over the place can travel through some equations and a neat list of the fundamental and harmonics can pop out. Its mathematical magic to me. Wish I could "get" it. But I guess I'll just have to settle for using it.

Faster Mersenne Prime Calculations?

[DarkHelmet]

From what I know, the Great Internet Mersenne Prime Search (GIMPS) uses a Fast Fourier Transform to quickly find the square of a number. This is a required part of the Lucas-Lehmer test (the test that determines if the number is prime).

If this form of FFT can do fast squaring, it will reduce the amount of time taken to find new, large primes.

This is a potentially exciting development in this field.