Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Generally when one takes the FFT of a signal it "works" over the whole bandwidth dividing up the spectrum into chunks given by the resolution. If the bandwidth of the signal is 10khz and your resolution is 1000 then each "frequency" represents a chunk of 10hz(each bin is 10hz in size).

The problem with this method is that it gives the same "size" to each bin even though lower frequencies loose resolution. e.g., a 10hz bin around 25hz frequency contains much more information than 10hz at 8kz. This issue is not hard to fix with the analytical FT since it is just a matter of scale. Is it possible adapt the FFT to have a frequency dependent bin-size?

Essentially when we divide up the frequency range into n chunks we want lower frequencies to have more accuracy since they are lower frequencies.

e.g., I might want a resolution of 0.1hz in the lower frequencies and 10hz in the higher frequencies. The problem with the current FFT is that we must use the highest resolution overall. That is, Because I want a 0.1hz resolution in the lower frequencies I MUST have an 0.1hz resolution in the higher resolutions. This means I'll require a much higher n-point transform than I really need.

share|improve this question
1  
Have you looked at wavelets? (By the way, I think your description of chunks or bins of the frequency range being represented by individual frequencies in the Fourier analysis is misleading.) –  joriki Jul 22 '12 at 15:29
    
@joriki There is nothing misleading about using the term bins. It is very similar to that of a histogram. I believe you are confused on terminology/understanding my question rather than the term being misleading. –  AbstractDissonance Jul 22 '12 at 19:46
    
I didn't say that the term "bins" is misleading. I believe your entire description of chunks or bins of frequency range being represented by individual frequencies is misleading. The frequencies in the discrete Fourier analysis stand only for themselves; they don't "represent" any nearby frequencies. –  joriki Jul 22 '12 at 19:57
    
@joriki: I'm sorry but your understanding of the DFT is a bit skewed. The DFT transforms a sequence of numbers to another sequence of numbers BUT when you interpret those numbers to physical meaning then do represent a "wash" or a "bin" of frequencies. There are many reasons for this and in the real world devices that convert signals to the digital domain are not even accurate enough and so each data point represents a "bin" around some point. In any case your only correct if we have infinite accuracy which we don't and the reason why I would like a low-frequency weighted transform. –  AbstractDissonance Jul 22 '12 at 20:14
2  
I don't think you're use of "correct" is appropriate here. I deliberately didn't say that you were incorrect, since this talk of bins and chunks being represented isn't formal enough to be correct or incorrect. I said that it's misleading, and I said so in the context of a site on mathematics. You may well be right that it has its merits in the context of inaccurate measurements, but I do believe that for someone trying to understand the discrete Fourier transform mathematically it can be misleading. –  joriki Jul 22 '12 at 20:23
show 5 more comments

2 Answers

up vote 1 down vote accepted

It's called the nonequispaced fft or non-uniform discrete Fourier transform:

Code can be found here

share|improve this answer
    
I am not referring to a non-uniform independent variable(usually time) but the frequency parameter(w). When you take the FFT of a function you end up with an array of numbers representing the magnitudes of frequencies EQUALLY spaced(they are partitioned uniformly just like time is). I do not want them equally spaced. NUDFT is used for non-uniform input sampling while I still have uniform input sampling. It is sort of the reverse of what I want. I want uniform input to non-uniform output rather than non-uniform input to uniform output. –  AbstractDissonance Jul 22 '12 at 19:50
    
@AbstractDissonance: The Fourier transform is symmetric with respect to "input" and "output"; which domain you call frequency and which you call time is just a matter of convention. –  joriki Jul 22 '12 at 20:02
1  
@AbstractDissonance: Please moderate your combative style. There's no need to imply that people haven't thought about what they wrote for a few minutes (especially people who tried to help you by providing an answer to your question), or to use four exclamation marks, or to describe someone's understanding as "skewed". –  joriki Jul 22 '12 at 20:28
1  
@AbstractDissonance Calm down man. Did you see the code provided in the answer? They are exactly what you are looking for. The input (time-domain) is uniformly sampled, and the output (frequency domain) is non-uniform. So NUDFT can used for both cases, no matter the non-uniform is in time or frequency domain. Here is another paper talking about exact what you want. –  chaohuang Jul 22 '12 at 20:34
1  
@AbstractDissonance: Here, too, this will be my last reply. Your tendency to quickly assume and claim that others don't "realize" the truth that you see, or that you have to "teach" them, is unconstructive. I don't want to interact in this manner, and I don't think you're increasing your chances of getting helpful answers by interacting this way. –  joriki Jul 22 '12 at 20:39
show 10 more comments

If you want smaller bins you simply pad the input sequence with zeros. Trust me it is worth the "effort". If you read carefully the stuff provided by chaohuang, the answer you are looking for is provided by oversampling(PAD THE SIGNAL WITH ZEROS) and then interpolation. The last paper's contribution was to minimize the errors! So whoever gave the downvote clearly has no clue what FFT is about!

share|improve this answer
    
............... –  La Conquista Aug 31 '12 at 17:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.