Slashdot Mirror
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.'"
In before _____.
Key phrase:
"smartphones to wirelessly transmit large video files without ... consuming their monthly bandwidth allotments."
Everyone see the connection to the Copyright Mayhem this week?
Bueller?
My first Journal Entry ever, in 8 years! http://slashdot.org/journal/365947/aphelion-scifi-fantasy-horror-poetry-webzine
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.
Doesn't some part of Internet Security (of ____, I'll leave that to my betters to explain) rely on Fourier properties?
So if we can bust those "Faster than Fast", what next?
My first Journal Entry ever, in 8 years! http://slashdot.org/journal/365947/aphelion-scifi-fantasy-horror-poetry-webzine
It doesn't improve the regular FFT but only sparse variants. Image or Audio compression nearly always uses the regular non-sparse FFT.
Jan
So the cat gets transformed even faster.
(apologies to XKCD)
Twitter supports and protects racists - by smearing their critics with the "Hate Speech" label.
Lossy compression such as MP3, AAC, and according to TFS also video compression, are all fundamentally based on FFT (fast fourier transforms). Depending on how well this new specific method works, we could see decreases in the time it takes to encode all this stuff. Which can be quite a long time... have you ever tried to do a 2-pass MPEG 4 conversion on a feature-length digital video? Video encoding doesn't scale well to multiple cores either, so nowadays when performance increases coming mostly from adding more cores... video encoding hasn't been getting faster at the same pace it used to. I'm thinking this new FFT algorithm could make a big difference in encoding speeds.
Additionally, I know lots of audio (and I'm assuming video) effects, DSPs of the kind you find in Adobe Audition, Audacity, et al., rely on FFTs. Computing such effects could get a lot faster. With increases in both the speed of adding effects, and compression afterwards, we might be seeing a significant speedup in the overall digital audio/video-editing process.
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.
Let me get this straight - you're saying you woke up in the middle of the night intending to take a dump, and somehow ended up posting about complex mathematical algorithms on the Internet instead? Respect.
In a cell phone or wi-fi, there are FFTs all over the place. They use them for things you would never suspect ... even if you have taken a DSP course. In modern radios (cell phones or anything else connected wirelessly) the DSP is the main chip.
Every time you find a computationally efficient way to do something, you improve battery life. So, phones can stay the same size and take advantage of even more streaming content.
Does this mean we get better and faster autotune?
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.
/^[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}$/i
No matter how good you think the latest and greatest algorithm is, there is usually someone who can come up with a way to improve on it.
For example, I DO know how to structure the probes done by MSS Code Factory such that you could stuff the rule base in Oracle and use some very Oracle-specific syntax to do the probes in one query, taking the first record from a sorted result set as your "answer" to the probe. I've written similar queries for other databases, but they're constrained by how many levels deep you want to write the query for. As there is no telling how deep the query would be for MSS Code Factory, and I don't want to tie myself to an expensive product like Oracle, what I have now is pretty much the best I can do at the moment. Maybe some day I'll come up with more tuning ideas, but not right now.
Kudos to the FFT team. I look forward to reading the details, though my memory of FFT math is pretty old, fuzzy, and shaky nowadays.
I used to be heavily into computer graphics and audio processing in the university days, but I've spent decades focusing on business programming instead. Unless you really LOVE graphics and sound, and want a job in a very narrow field (including video games), I think it's inevitable that you put away the toys and pick up the tools of industry that will earn you a pay cheque.
I do not fail; I succeed at finding out what does not work.
Saying that compression uses the regular "non-sparse" algorithm is rather meaningless; they use what is available, and I don't believe there was a sparse-optimized algo until now.
Comment removed based on user account deletion
They will try to keep this under wraps as anything that speeds up video encoding/decoding will be classes as anti Hollywood and a tool for piracy.
Standby for a few mysterious disappearances of any public copies of the algorithm.
I'd rather be riding my '63 Triumph T120.
TFA trivializes the result. A reduction of up to 90% the speed is not theoretically interesting at all - it could always be overridden by difference in architecture and implementation, often making older algorithms faster. There are many better ways to describe the reduction in time complexity to the laymen.
Same deal here: I was "into" other areas of programming (mainly systems programming) but found that the job market was far more active in what you're calling "business programming" (i.e.-> MIS/IS/IT work & mostly DB-related areas, which is why "SQL's your pal").
* QUESTION - Does Oracle still provide the "OO40" middleware & API's to communicate with it (vs. ADO/RDO etc.)?
See... Last time I coded around it 1999-2001, the company I worked for used a combination of ADO (faster on READS from Oracle's DB devices) + OO40 (faster on WRITE, going BACK to the Oracle DB's devices) from a 32-bit VB6 front-end (calling stored procs from Oracle).
(That was a decade++ ago though... so, just curious & asking!)
APK
P.S.=> Nice to see a realist around here... & you're right about "engines/algorithms" too - sooner or later, someone finds a better way of doing things, even IF only in "exception" situations with specific data/conditions, etc./et al... apk
As a scientist in the filed of Fourier Transform Spectroscopy I find this perspective quite interesting, even though it is not that different from other techniques we tried to apply in the field to improve performance. Needless to say, we are quite dependent on FFT performances in this field, even more since the deployment of Imagine FTS systems. Any improvement in FFT performance is noteworthy.
Lets see if its one of those "fields" where drastic performance improvement can be met! Regardless, it's quite an interesting break for signal processing.
This is all very interesting. But can u explain to me how SODA relates to SOPA?
Another use that I can see for this technology is to use it for emergency and impromptu news broadcasting, especially when faced with dictatorial authorities (like Iran/China/Syria) which will do anything to stop unfavorable news from getting out to the world
Muchas Gracias, Señor Edward Snowden !
Has research established a theoretical minimum amount of joules required to transmit one bit of info, at the limits of computation?
--
make install -not war
... how do you get from a load of say 16 bit samples into vectors? If I have sin wave sample data in an array such as the following:
0,5,10,5,0,-5,-10,-5,0
how does that then become a sequence of vectors to calculate the FT?
0,5,10,5,0,-5,-10,-5,0
You can consider them as vectors, but normally they are considered complex numbers.
....
0 + 0i, 5 + 0i, 10 + 0i, 5 + 0i,
"His name was James Damore."
I started reading the paper, and get the general idea -- but haven't yet checked out the prereqs, pseudorandom spectrum permutations and flat filtering windows. Is there sample code of this algorithm available anywhere?
Call me a skeptic. Most images are not sparse. So unless you are transmitting images of stars on a strictly black sky this will not help much. And if we know the image is sparse there are other procesing techniques that do not require an FFT.
...in a world where mathematicians patented their Ideas and when after violators with a vengeance.
$action = empty(PHP) ? backToC() : unset(PHP) ; "when the concrete cases are understood, the abstractions are readily
And, do you know the most important area where this faster algorithm could be used? Yep, you are right, cryptography.
That statement cannot be evaluated for truth - it's not falsible - so it's at best an unproven and highly suspect theory. At worst, it's a faith-based dogma.
If you weren't made of meat, perhaps the thing you think is a universal constant would be a variable. You can't actually know, because individual humans by definition cannot attain objectivity; it can only be approximated.
It seems like most mathematicians never bother with philosophy, and vice versa, which is probably why everyone else considers both disciplines to be devoid of all "common sense". Limits on your perception and comprehension can be demonstrated to exist, therefore you can't know what all the limitations of the external universe are for certain - soldier/philosopher/mathematician Renee Descartes dealt with this in his Meditations on First Philosophy.
Not very usable for things that we need super-fast FFTs for, a gazillion times a second, like LTE.
I wonder if this is just re-discovering compressed sensing.
-- Erich
Slashdot reader since 1997
if you're running your EQ off of the time domain signal derived from the mp3, you're doing it wrong. :)
Posting a story about how a presentation will be given at SODA... about a day after SODA ended.
I actually went to this talk, which was scheduled for the first 8:30 AM timeslot as part of their evil conspiracy to get me to wake up early. The approach seemed remarkably straightforward, but I haven't gotten around to actually reading the paper yet -- I was too busy sightseeing around Kyoto.
.. how do you get from a load of say 16 bit samples into vectors? If I have sin wave sample data in an array such as the following:
It's a single vector, not vectors (pllural): that's the important distinction. All the samples form a single vector.
In other words, if you have 1024 samples, then put them into a 1024 dimensional vector.
Does that clear it up?
SJW n. One who posts facts.
Does anyone know if this technique could be used to get a sparse approximation to a non-sparse signal (i.e. assume the signal only has a small number of components, and calculate what they would be to get a best match)?
That would be really useful - for example rather than JPEG/MPEG compression doing a regular FFT and throwing away the high frequency components, maybe you could use the fast sparse algorithm to quickly calculate an approximation in the first place.
Let us try with the fourier transform :
If you have a signal, you can see it as an sum of sinusoide of various frequencies : y=C0+C1*sin (a.t)+C2*sin (2*a.t)+C3*sin (3*a.t)+C4-*sin (4*a.t)+ etc...
IF you integrate y*sin (n*a.t) then all the term sin with a different n will simply become equal to zero (over a period as much negative surface as positive), the only term which will be non zero will be the term in Cn because then you get to integrate you will only get a positive term. So by varying the integrating term you will get each C0...Cn term which will show you which frequency are used. For example if you have y=2+3*sin(2*a*t)+Sin (4*a*t) integrated over 2*pi/a periods, the integration for n=2 will give you a multiple of the term C2 , over n=3 will give you zero (sin (2*a*t)*sin(3*a*t) will be zero) over n=4 will give you a multiple of C4....
In the very end by using that serie of integration you get the amplitude in each different frequence. So instead of having a real time signal, you have a Series of Cn describing you a spectrum. In our example we will have a bar on frequence for n=2 and n=4 with height multiple of C2 and C4 (there is a/2*pi factor due to integration).
What does the FFT do, is that for DISCRETE digital value, the frequencies being multiple of the length of the sample, you can use very quick numerical algorithm to simulate that integration process, and find out the Cn very quick (thus the fast in FFT).
I don't know that I would have expressed this the way the GP did, but SuricouRaven is correct. Given a nonzero, time-limited signal, its Fourier transform can not be band limited, and vice versa.
If you weren't made of meat, perhaps the thing you think is a universal constant would be a variable. You can't actually know, because individual humans by definition cannot attain objectivity; it can only be approximated.
If objectivity can only be approximated, how do we know that your definitions are correct?
Limits on your perception and comprehension can be demonstrated to exist, therefore you can't know what all the limitations of the external universe are for certain
But one of the ways of thinking about Heisenberg uncertainty involves how we interact with particles. We would like to use particles that are both low energy (to not greatly affect the momentum of the particle we're trying to observe) and low wavelength (to get a better fix on its position). We just don't have such particles, at least not yet.
The point of this FFT improvement is for signals that are sparse in the frequency domain, not spatial domain. Most images _are_ sparse in frequency due to discretization during data collection.
But what about the inverse FFT? So I can FFT something quicker, but what about when I want to go the other way? ;)
The general idea is that on average the +1 from the Insightful and the -1 from the Flamebait cancel each other out
Then why not just create a new menu option "Inciteful" that doesn't affect a comment's score but spends two mod points to give the poster this message?
In the "old days" these would take much longer than the integration calculations. by using a trig-identity you compute the new ones from power of two of the old ones using simple math. Or these days with large core memories you can pre-tabulate them, if you reuse the same lengths over and over.
The row based fast lifting wavelet transform still beats it.
RB-FLWT beats standard FFT by about 16x and many cases 32x.
Just sayin
Could I:
Quickly search the patent office database
Find all the patents which use a FFT
Patent the invention of using the improved FFT in place of the one in the patent?
Or is it too late since I just published my idea?
That's a pretty fast Fourier transform.
my, your, his/her/its, our, your, their
I'm, you're, he's/she's/it's, we're, you're, they're
No one will save on their bandwidth allotments because of this. It just makes the encoding process faster. The resulting media file will still be the same size/quality and use the same amount of monthly cellphone data as a media file encoded with the old algorithm.
Anything that significantly reduces bandwidth usage may be locked away in the same vault that holds the Arc of the Covenant and Jimmy Hoffa.
Here's the first sentence of the abstract: "We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal." Did you notice the word "approximation" in there? Right. This is an algorithm for calculating an approximation to the Fourier transform, not the actual Fourier transform. There are, to be sure, lots of problems where that's exactly what you want, and this algorithm could be really useful for them. There are also a lot of problems where that's not useful at all, and you need the exact transform. In any case, calling this a "Faster-Than-Fast Fourier Transform" is just wrong. It isn't a Fourier transform. It's an approximation to the Fourier transform.
"I'm too busy to research this and form an educated opinion, but I do have time to tell everyone my uninformed opinion."
when will this faster-than-fast bittorrent client named Fourier be available to the masses?
I can see someone going down to the US patent office and patenting this bad boy, quick as a wink! What you say? Mathematical formulas are not patentable? Rubbish, that's all gone now. They can patent the hell out of computer software, and there are bags and bags of patents on software! They can make the arguement that since computer software is basically the description of mathematics to a computer, and there are bags of patents on it, so now they just drop the computing machinery part, and *bang* 1+1= more money for megacorp than you can shake a stick at.
If you really want fast, use discreet Walsh-Hadamard xform and look-up tables.
The null transform beats them both. So does the plus-one transform. What's your point?
I concur.