MIT has been making a bit of noise lately about a new algorithm that is touted as a faster Fourier transform that works on particular kinds of signals, for instance: "Faster fourier transform named one of world’s most important emerging technologies". The MIT Technology Review magazine says:
With the new algorithm, called the sparse Fourier transform (SFT), streams of data can be processed 10 to 100 times faster than was possible with the FFT. The speedup can occur because the information we care about most has a great deal of structure: music is not random noise. These meaningful signals typically have only a fraction of the possible values that a signal could take; the technical term for this is that the information is "sparse." Because the SFT algorithm isn't intended to work with all possible streams of data, it can take certain shortcuts not otherwise available. In theory, an algorithm that can handle only sparse signals is much more limited than the FFT. But "sparsity is everywhere," points out coinventor Katabi, a professor of electrical engineering and computer science. "It's in nature; it's in video signals; it's in audio signals."
Could someone here provide a more technical explanation of what the algorithm actually is, and where it might be applicable?
EDIT: Some links:
No comments:
Post a Comment