IPB

Welcome Guest ( Log In | Register )

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
 
Start new topic
Replies
Destroid
post Feb 11 2012, 13:00
Post #2





Group: Members
Posts: 551
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
alexeysp
post Feb 13 2012, 00:37
Post #3





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

Posts in this topic


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: 30th September 2014 - 12:28