## Topic: Sparse Fast Fourier Transform (Read 8407 times)previous topic - next topic

0 Members and 1 Guest are viewing this topic.
• 16 Hz
Sparse Fast Fourier Transform
##### 10 February, 2012, 01:55:44 PM
Hello.
I don't know if this topic was already mentioned here (I wasn't able to find it).

Somebody here could find it interesting:

MIT news article: The faster-than-fast Fourier transform

sFFT web page: sFFT: Sparse Fast Fourier Transform

Best regards.

Omar

• romor
Sparse Fast Fourier Transform
##### Reply #1 – 10 February, 2012, 03:15:57 PM
LossyFFT

• Destroid
Sparse Fast Fourier Transform
##### Reply #2 – 10 February, 2012, 03:33:33 PM
What do you mean? Even so, I can think one application where a real-time DSP could be used to preview (and later set to a precision mode during final rendering).

I wonder how FFTW world compare in performance.
"Something bothering you, Mister Spock?"

• 16 Hz
Sparse Fast Fourier Transform
##### Reply #3 – 10 February, 2012, 03:43:49 PM
LossyFFT

Transforming a signal to frequency domain, isn't always lossy?
Or is it possible to do a time->freq->time conversion in a lossless way?

• romor
Sparse Fast Fourier Transform
##### Reply #4 – 10 February, 2012, 04:12:24 PM
http://en.wikipedia.org/wiki/Fast_Fourier_..._approximations

Yes, x=ifft(fft(x)) within numerical accuracy, i.e. doing it out-of-box in numpy err is 1e-16

The work you are presenting to us, throws away insignificant frequencies

• alexeysp
Sparse Fast Fourier Transform
##### Reply #5 – 10 February, 2012, 04:16:56 PM
Transforming a signal to frequency domain, isn't always lossy?

DFT is an orthogonal linear transform, and as such is always inversible. In other words, it is lossless (up to the computation roundoff error in practice).

• Destroid
Sparse Fast Fourier Transform
##### Reply #6 – 11 February, 2012, 07:00:19 AM
Just wondering: sFFT (based on DFT?  ) compromises frequency-domain in floating accuracy areas to approximate for the sake of performance? [ I may need to do more homework  ]

Second inquiry: this rounding is inaccurate not reliable to rebuild original parameters? (possibly inaudible, maybe not)

My inquires are on fundamental levels for the purpose of learning for any other interested readers.

Long live HA
"Something bothering you, Mister Spock?"

• dhromed
Sparse Fast Fourier Transform
##### Reply #7 – 11 February, 2012, 08:31:21 AM

• alexeysp
Sparse Fast Fourier Transform
##### Reply #8 – 12 February, 2012, 06:37:57 PM
Just wondering: sFFT (based on DFT?) compromises frequency-domain in floating accuracy areas to approximate for the sake of performance?

"FFT" is just a name for one particularly clever method of computing DFT. "Sparse FFT" is a name for the method of computing DFT (or rather its approximation) that is applicable to the signals a priori known to have relatively few significant spectral components.

You can think of sparse FFT as the "noise gate" filter working in frequency domain.

The algorithm does not choose the noise threshold automagically - number of significant components to compute is a free parameter and its value must be decided upon beforehand.

Quote
Second inquiry: this rounding is inaccurate not reliable to rebuild original parameters? (possibly inaudible, maybe not)

In general, the magnitude of the accumulated roundoff error depends on the inherent precision of the used number format, on the order of computations, and on the transform window length. To get an idea of actual figures, one could take a look at the fftw accuracy benchmark results.

For basic theoretical analysis on the quantization noise in finite precision FFT, this chapter is worth reading. There are, of course, many other published works on this subject.

• romor
Sparse Fast Fourier Transform
##### Reply #9 – 22 September, 2012, 10:09:44 AM
Another sparse attack - QTT–FFT (quantized tensor train):

Quote
... Combining the QTT–FFT algorithm with a method that computes QTT representation
from several elements (samples) of a given vector, we compare it with Sparse Fourier
transform algorithms. By numerical examples we show that our approach can be competitive
with the existing methods for the Fourier-sparse signals with randomly distributed
components, especially for higher dimensions. Our approach is especially advantageous
for the signals with limited bandwidth, which are not exactly Fourier-sparse...

Sparse Fast Fourier Transform
##### Reply #10 – 22 September, 2012, 11:59:35 AM
Know next to nothing about maths, but was wondering about the claim for improving battery life. Course, I understand computation uses power and any reduction in the computation needed for a given task reduces the power needed to perform the task.

I'm just wondering if any power savings are expected to be significant in typical consumer uses...phones, tablets etc or in more general scientific and engineering computation?

• saratoga
Sparse Fast Fourier Transform
##### Reply #11 – 22 September, 2012, 12:30:25 PM
I'm just wondering if any power savings are expected to be significant in typical consumer uses...phones, tablets etc or in more general scientific and engineering computation?

Probably not.  The FFT isn't really the bottleneck in anything consumers do that I can think of.  Yes, video and audio codecs often use them, but they're usually only a small part of the entire codec time, and for these applications approximations to the FFT are already available.  I didn't look at the math but my guess is that something like this becomes more useful for very large FFT sizes or for more then 1 or 2 dimensional transforms.

Science, engineering and maybe telcom applications might be a completely different story though.

• m45t3r
Sparse Fast Fourier Transform
##### Reply #12 – 22 September, 2012, 07:25:04 PM
I'm just wondering if any power savings are expected to be significant in typical consumer uses...phones, tablets etc or in more general scientific and engineering computation?

Probably not.  The FFT isn't really the bottleneck in anything consumers do that I can think of.  Yes, video and audio codecs often use them, but they're usually only a small part of the entire codec time, and for these applications approximations to the FFT are already available.  I didn't look at the math but my guess is that something like this becomes more useful for very large FFT sizes or for more then 1 or 2 dimensional transforms.

Science, engineering and maybe telcom applications might be a completely different story though.

Well, on Rockbox at least the FFT part of decoding can take up to 50% of CPU time (http://www.rockbox.org/wiki/FasterMDCT). It's true that audio decoding is not really that much CPU intensive, but video encoding/decoding probably is another mater.

• saratoga
Sparse Fast Fourier Transform
##### Reply #13 – 22 September, 2012, 07:30:40 PM
Well, on Rockbox at least the FFT part of decoding can take up to 50% of CPU time (http://www.rockbox.org/wiki/FasterMDCT).

Well it did until stripwax, mt and I rewrote it using a modern, efficient split radix FFT.  Now its quite a bit faster.

It's true that audio decoding is not really that much CPU intensive, but video encoding/decoding probably is another mater.

Sure, but the DCT is usually only a pretty small portion of that.  And of course you can already use approximations if you want (though usually people don't since its not very slow to begin with).

• m45t3r
Sparse Fast Fourier Transform
##### Reply #14 – 22 September, 2012, 07:48:23 PM
Well, on Rockbox at least the FFT part of decoding can take up to 50% of CPU time (http://www.rockbox.org/wiki/FasterMDCT).

Well it did until stripwax, mt and I rewrote it using a modern, efficient split radix FFT.  Now its quite a bit faster.

It's true that audio decoding is not really that much CPU intensive, but video encoding/decoding probably is another mater.

Sure, but the DCT is usually only a pretty small portion of that.  And of course you can already use approximations if you want (though usually people don't since its not very slow to begin with).

Interesting, so how much CPU time does FFT uses on Rockbox nowadays?

• saratoga
Sparse Fast Fourier Transform
##### Reply #15 – 22 September, 2012, 08:01:56 PM
Interesting, so how much CPU time does FFT uses on Rockbox nowadays?

To be honest its been so long I don't remember.  Probably 10MHz or so though on arm7tdmi, less on a more modern ARM chip.

• romor
Sparse Fast Fourier Transform
##### Reply #16 – 23 September, 2012, 12:56:54 AM
Authors suggest applications in image and vidio processing, but perhaps applications are broader and "limited" to problems using features of this TT (no dimensionality curse) format, including machine learning (PCA), pattern recognition, and the like (or wavelets, remote sensing, ...)

About dense formulae presented in the paper - from far above, it seems that at least one characteristic of this TT format is tied to decomposition - tensor SVD and TT-SVD algorithm. It is suggested/shown that decomposing allows fast and trivial arithmetics (..., convolution) in one dimension - linear, and fast approximations
Yet QTT decomposition - binarization (algebraic wavelet transform) as additional feature

Matlab users can find TT toolbox here: https://github.com/oseledets/TT-Toolbox

I'm by no means related to this, nor have Matlab

• hlloyge
Sparse Fast Fourier Transform
##### Reply #17 – 23 September, 2012, 05:26:50 AM
I remember, few years ago, experimenting with encoding (or decoding) audio to some codec, vorbis, mp3, I can't remember, with the use of external fft dll someone compiled and posted here on HA. It was faster.
But I can't find the thread.