# How to do DFT for irregular sampling period ?

I have two vectors: $\vec{a}$ and $\vec{t}$: $a_k$ is the sampling value taken at $t_k$. I need to do DFT, but the sampling period is irregular. I've learned about Frames but unsure how to use the Duffin–Schaeffer's suggestion for a Frame-function: $\sqrt{\frac{t_{n+1}-t_{n-1}}{2T}}sinc(\frac{\pi}{T}[t-t_n])$.

Does the following operation: $C_n=\sum_k{f(k) sinc(\frac{\pi}{T_k}[t_k-t_n])}$, really do the work to get the coefficients ($C_n$) ? (... pretty sure I misinterpreted the equation somehow ...)

Do I need the preceding $\sqrt{\frac{t_{n+1}-t_{n-1}}{2T}}$ ?

-
@Tal: is your question seeking advice on numerical techniques? Or are you studying the problem theoretically? – WetSavannaAnimal aka Rod Vance Jul 14 '11 at 2:56
@wetsavannaanimal-aka-rod-vance: I'm no mathematician, I'm practical engineer (EEE) and programmer. I have a real world problem. Theory would interest me only if it gets me somewhere... If I have a gap of knowledge, then I would get books and read - But in this case, I just want to examine data (say 10k elements vector) in MATLAB, which was sampled non-uniformly, and learn what kind of filter I need. In addition, since the real-time data comes in variable sampling rate, the next step would be to understand how to build a (digital) filter that handles this situation. – Tar Jul 14 '11 at 18:38
You may be interested in my answer to a similar math.stackexchange question, which describes an easy but probably less accurate method. – Sebastian Reichelt Jul 14 '11 at 21:08

There have been a number of publications about "Unequally Spaced FFTs" in the numerical analysis literature. These typically involve an automated sort of interpolation (usually Gaussian) to an equally spaced grid followed by an FFT. The methods come with error bounds specified. You could search under the names Rokhlin, Dutt, and Beylkin, with title words "Unequally spaced FFT."

I located the following:

A. Dutt and V. Rokhlin, Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Comput. 14, 1993, 1368–1393.

There is also work by Greg Beylkin, see for example:

and references therein.

Mind you, I have not used these directly, but have used curvelet transform codes that are based on similar algorithms.

Hope this helps a bit,

Tom

-

If you are looking for software: Have a look at NFFT by Potts, Kreiner and Kunis.

-
If it's from Osnabrück, I am endorsing it :) – Hans Engler Jul 15 '11 at 1:54
I think it is from Chemnitz but Stefan Kunis went to Osnabrück. – Dirk Jul 15 '11 at 13:37

In a nutshell, do a spline interpolation, resample, and then compute a DFT. You will encounter difficulties if the $t_{k+1}- t_k$ vary over several orders of magnitude because the smallest such gap dictates the interval width for resampling. You will also have immense trouble if the data are noisy - in that case you could try to denoise them first, e.g. using wavelets. Finally you will have to handle endpoint problems.

-
@Hans: maybe you could say something about the applications which you have found this works well for. Also, I'm not altogether sure that the OP is asking for a numerical technique - but if so, then often qualitative "experimental" data on performance can be useful. – WetSavannaAnimal aka Rod Vance Jul 14 '11 at 2:55
@Rod - I did this for data coming from measurements in electronic circuits. Typically about 20K sample points, with $\frac{max_k(t_{k+1}-t_k)}{min_k(t_{k+1}-t_k)} \approx 10^3$ or so. The main advantage there was that $(t_{k+1}-t_k)$ varied very smoothly with $k$. The bottleneck turned out to be the spline interpolation, due to the differences in scales. I ended up using cubic box splines and then just adding (superposing) the dft's of these box splines explicitly (no fft after all). But that would not work if $(_{k+1}-t_k$ varies irregularly. – Hans Engler Jul 14 '11 at 12:43

As a practical EEE \ programmer, I only delve into theory when needed, and a considerable dose of it is definitely needed here... so I ordered the book Nonuniform Sampling: Theory and practice / Farokh Marvasti from 2001. Hope it will answer my questions. Will be glad to be back with a concise answer to the benefit of others.

-