Trying to decompose a signal into sine waves whose wavelengths aren't restricted to 1/N times sample range?

I am trying to essentially do a Fourier transform - I want to fit some data with sine/cosine functions. At first I was trying to do this using FFT, but my problem is that the FFT algorithm doesn't seem to provide accurate information about the actual frequencies/wavelengths that are making up the data, i.e., all the wavelengths reported by the FFT are 1/N of the sample window (where N is an integer.)

But, say that the actual wavelength present is some non-integer quotient such as 1/3.5 times the sample window, etc.? Is there a better algorithm than FFT to fit a function with any-wavelength sine waves, instead of only restricting to specific wavelengths?

(I understand that to get a better fit, it probably won't be a fast algorithm like FFT - that is fine if it is a slow method, as long as it can accurately fit to find any arbitrary present frequencies.)

This is my first time posting on this board - let me know if you need any more information about my question. Bonus points if anyone can suggest a way to do this in Python!

There is absolutely no need for explicit interpolation. The DFT can do that for you. Take you signal frame and apply a windowing function to minimise edge artefacts. Afterwards pad the frame with zeros to determine the number to output bins of the DFT. Then apply your FFT and you have an interpolated spectrum with the frequency step size you desire.

• Great! I'd tried zero padding, but I hadn't subtracted the mean, so the FFT was giving me junk (FFT of a step function I guess.) After looking into windowing, I saw that I should be subtracting the mean off my signal. FFT results: i.imgur.com/kpszbz8.png One more question: I've tried zero padding 5 ways: raw data, mean subtracted, mean/slope subtracted, and windowed with Hann and Hamming windows. The windowed FFTs show a peak at 12700, while the mean/slope subtracted show that peak at 13000. Manual analysis suggests 13000 to be closer. Why is windowing causing a peak shift? – MarkSchwab Aug 2 '16 at 17:57
• @MarkSchwab Can you show your code? – Jazzmaniac Aug 2 '16 at 18:36
• Is there a good way to post my code without going over the 600 character limit? – MarkSchwab Aug 2 '16 at 18:47

If you signal is stable long enough, one method is to gather more data over a longer time period, and then use a longer FFT. If the sine/cosine functions of interest are far enough apart in frequency, and the noise and interference levels are low enough, you can use your current FFT results and interpolate between the FFT result bins (the ones that are Fs/N apart) for greater peak frequency estimation resolution. Parabolic interpolation is one method, but not as accurate as Sinc kernel reconstruction for interpolation. You can use successive approximation with windowed Sinc reconstruction, if needed.

• Unfortunately, I can't collect more data, I'm working with what data I have available. Could you go into more detail on how to do the Sinc kernel reconstruction for interpolating between the FFT bins? And the successive approximation with windowed Sinc reconstruction? Or, if there is a tutorial that you could link to, that would also be much appreciated. Am I correct in understanding that even with a fixed data set, I could use those methods to help determine what "actual" frequencies are present even if they are in between FFT frequency bins? Example data: i.imgur.com/XEAQhH5.png – MarkSchwab Aug 2 '16 at 0:25
• Whether you can reliably use interpolation or not depends on your S/N ratio. See: ccrma.stanford.edu/~jos/resample/… – hotpaw2 Aug 2 '16 at 2:21

It may surprise you that you can perfectly reconstruct your sampled data using only integer fractional bins; you can perfectly represent your 20 samples in 1 second of your 3.5 hz wave using only a linear combination of sin/cos 0,1,2,..9.

If your question is "how do i represent sampling of a non integer frequency", the answer is the fft guarantees that you can perfectly reconstruct your samples, irrespective of frequency.

If your question is "can i know what my frequency was" -- unfortunately the basis for the FFT transform assumes that you have multiple frequencies present and calculates the weightings for those frequency combinations (1hz, 2hz, etc) to perfectly account for the received signal.

• I attempted to get woulfram alpha to plot what the dft of the above was, but the closest i got was a table with complex numbers with wolframalpha.com/input/… but the graph is scaled all wrong – Andrew Hill Aug 2 '16 at 2:13
• Anthropomorphizing basis functions does not make sense. They make no assumptions. Now the user of a DFT can make your assumption or various other assumptions given differing a-priori knowledge or information about the data. – hotpaw2 Aug 2 '16 at 2:18