IPB

Welcome Guest ( Log In | Register )

 
Reply to this topicStart new topic
Sparse Fast Fourier Transform, The faster-than-fast Fourier transform
16 Hz
post Feb 10 2012, 19:55
Post #1





Group: Members
Posts: 6
Joined: 27-November 09
From: Argentina
Member No.: 75344



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
Go to the top of the page
+Quote Post
romor
post Feb 10 2012, 21:15
Post #2





Group: Members
Posts: 668
Joined: 16-January 09
Member No.: 65630



LossyFFT


--------------------
scripts: http://goo.gl/M1qVLQ
Go to the top of the page
+Quote Post
Destroid
post Feb 10 2012, 21:33
Post #3





Group: Members
Posts: 545
Joined: 4-June 02
Member No.: 2220



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?"
Go to the top of the page
+Quote Post
16 Hz
post Feb 10 2012, 21:43
Post #4





Group: Members
Posts: 6
Joined: 27-November 09
From: Argentina
Member No.: 75344



QUOTE (romor @ Feb 10 2012, 17:15) *
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?
Go to the top of the page
+Quote Post
romor
post Feb 10 2012, 22:12
Post #5





Group: Members
Posts: 668
Joined: 16-January 09
Member No.: 65630



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


--------------------
scripts: http://goo.gl/M1qVLQ
Go to the top of the page
+Quote Post
alexeysp
post Feb 10 2012, 22:16
Post #6





Group: Members
Posts: 130
Joined: 3-April 09
Member No.: 68627



QUOTE (16 Hz @ Feb 10 2012, 23:43) *
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).
Go to the top of the page
+Quote Post
Destroid
post Feb 11 2012, 13:00
Post #7





Group: Members
Posts: 545
Joined: 4-June 02
Member No.: 2220



Just wondering: sFFT (based on DFT? unsure.gif ) compromises frequency-domain in floating accuracy areas to approximate for the sake of performance? [ I may need to do more homework tongue.gif ]

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


--------------------
"Something bothering you, Mister Spock?"
Go to the top of the page
+Quote Post
dhromed
post Feb 11 2012, 14:31
Post #8





Group: Members
Posts: 1286
Joined: 16-February 08
From: NL
Member No.: 51347



FYI, here is NewScientist's pop-sci interpretation.
Go to the top of the page
+Quote Post
alexeysp
post Feb 13 2012, 00:37
Post #9





Group: Members
Posts: 130
Joined: 3-April 09
Member No.: 68627



QUOTE (Destroid @ Feb 11 2012, 15:00) *
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.

Go to the top of the page
+Quote Post
romor
post Sep 22 2012, 15:09
Post #10





Group: Members
Posts: 668
Joined: 16-January 09
Member No.: 65630



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


Paper link: fft2.pdf


--------------------
scripts: http://goo.gl/M1qVLQ
Go to the top of the page
+Quote Post
quackalist
post Sep 22 2012, 16:59
Post #11





Group: Members
Posts: 42
Joined: 18-July 03
Member No.: 7846



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?

Go to the top of the page
+Quote Post
saratoga
post Sep 22 2012, 17:30
Post #12





Group: Members
Posts: 4854
Joined: 2-September 02
Member No.: 3264



QUOTE (quackalist @ Sep 22 2012, 11:59) *
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.
Go to the top of the page
+Quote Post
m45t3r
post Sep 23 2012, 00:25
Post #13





Group: Members
Posts: 22
Joined: 14-January 12
Member No.: 96431



QUOTE (saratoga @ Sep 22 2012, 13:30) *
QUOTE (quackalist @ Sep 22 2012, 11:59) *
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.
Go to the top of the page
+Quote Post
saratoga
post Sep 23 2012, 00:30
Post #14





Group: Members
Posts: 4854
Joined: 2-September 02
Member No.: 3264



QUOTE (m45t3r @ Sep 22 2012, 19:25) *
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.

QUOTE (m45t3r @ Sep 22 2012, 19:25) *
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).
Go to the top of the page
+Quote Post
m45t3r
post Sep 23 2012, 00:48
Post #15





Group: Members
Posts: 22
Joined: 14-January 12
Member No.: 96431



QUOTE (saratoga @ Sep 22 2012, 20:30) *
QUOTE (m45t3r @ Sep 22 2012, 19:25) *
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.

QUOTE (m45t3r @ Sep 22 2012, 19:25) *
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?
Go to the top of the page
+Quote Post
saratoga
post Sep 23 2012, 01:01
Post #16





Group: Members
Posts: 4854
Joined: 2-September 02
Member No.: 3264



QUOTE (m45t3r @ Sep 22 2012, 19:48) *
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.
Go to the top of the page
+Quote Post
romor
post Sep 23 2012, 05:56
Post #17





Group: Members
Posts: 668
Joined: 16-January 09
Member No.: 65630



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


--------------------
scripts: http://goo.gl/M1qVLQ
Go to the top of the page
+Quote Post
hlloyge
post Sep 23 2012, 10:26
Post #18





Group: Members
Posts: 695
Joined: 10-January 06
From: Zagreb
Member No.: 27018



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.
Go to the top of the page
+Quote Post

Reply to this topicStart new topic
1 User(s) are reading this topic (1 Guests and 0 Anonymous Users)
0 Members:

 



RSS Lo-Fi Version Time is now: 26th July 2014 - 00:51