Sparse Fast Fourier Transform, The faster-than-fast Fourier transform Options

[16 Hz]

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]

LossyFFT

[Destroid]

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.

[16 Hz]

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]

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]

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]

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

[dhromed]

FYI, here is NewScientist's pop-sci interpretation.

[alexeysp]

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.

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]

Another sparse attack - QTT–FFT (quantized tensor train):

... 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...

Paper link: fft2.pdf

[quackalist]

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]

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]

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]

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]

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]

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]

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]

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.