Sparse Fast Fourier Transform, The fasterthanfast Fourier transform 
Sparse Fast Fourier Transform, The fasterthanfast Fourier transform 
Feb 10 2012, 19:55
Post
#1


Group: Members Posts: 6 Joined: 27November 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 fasterthanfast Fourier transform sFFT web page: sFFT: Sparse Fast Fourier Transform Best regards. Omar 


Feb 11 2012, 13:00
Post
#2


Group: Members Posts: 562 Joined: 4June 02 Member No.: 2220 
Just wondering: sFFT (based on DFT? ) compromises frequencydomain 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?"



Feb 13 2012, 00:37
Post
#3


Group: Members Posts: 143 Joined: 3April 09 Member No.: 68627 
Just wondering: sFFT (based on DFT?) compromises frequencydomain 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. 


LoFi Version  Time is now: 31st January 2015  10:36 