How to do DFT for irregular sampling period ? - MathOverflow

How to do DFT for irregular sampling period ?

2011-07-13T21:09:28Z

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}}$ ?

Answer by Hans Engler for How to do DFT for irregular sampling period ?

2011-07-14T02:49:18Z

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.

Answer by Tom Dickens for How to do DFT for irregular sampling period ?

2011-07-14T03:21:26Z

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:

http://www.ipam.ucla.edu/publications/mgatut/mgatut_4992.pdf

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

Answer by Dirk for How to do DFT for irregular sampling period ?

2011-07-14T20:24:43Z

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

Answer by Tal for How to do DFT for irregular sampling period ?

2011-07-21T17:56:34Z

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.