How to do DFT for irregular sampling period ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T10:08:44Z http://mathoverflow.net/feeds/question/70263 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70263/how-to-do-dft-for-irregular-sampling-period How to do DFT for irregular sampling period ? Tal 2011-07-13T21:09:28Z 2011-07-21T17:56:34Z <p>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])$.</p> <p>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 ...)</p> <p>Do I need the preceding $\sqrt{\frac{t_{n+1}-t_{n-1}}{2T}}$ ?</p> http://mathoverflow.net/questions/70263/how-to-do-dft-for-irregular-sampling-period/70285#70285 Answer by Hans Engler for How to do DFT for irregular sampling period ? Hans Engler 2011-07-14T02:49:18Z 2011-07-14T15:26:41Z <p>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.</p> http://mathoverflow.net/questions/70263/how-to-do-dft-for-irregular-sampling-period/70290#70290 Answer by Tom Dickens for How to do DFT for irregular sampling period ? Tom Dickens 2011-07-14T03:21:26Z 2011-07-14T03:21:26Z <p>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." </p> <p>I located the following:</p> <p>A. Dutt and V. Rokhlin, Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Comput. 14, 1993, 1368–1393.</p> <p>There is also work by Greg Beylkin, see for example:</p> <p><a href="http://www.ipam.ucla.edu/publications/mgatut/mgatut_4992.pdf" rel="nofollow">http://www.ipam.ucla.edu/publications/mgatut/mgatut_4992.pdf</a> </p> <p>and references therein.</p> <p>Mind you, I have not used these directly, but have used curvelet transform codes that are based on similar algorithms.</p> <p>Hope this helps a bit,</p> <p>Tom</p> http://mathoverflow.net/questions/70263/how-to-do-dft-for-irregular-sampling-period/70369#70369 Answer by Dirk for How to do DFT for irregular sampling period ? Dirk 2011-07-14T20:24:43Z 2011-07-14T20:24:43Z <p>If you are looking for software: Have a look at <a href="http://www-user.tu-chemnitz.de/~potts/nfft/" rel="nofollow">NFFT</a> by Potts, Kreiner and Kunis.</p> http://mathoverflow.net/questions/70263/how-to-do-dft-for-irregular-sampling-period/70918#70918 Answer by Tal for How to do DFT for irregular sampling period ? Tal 2011-07-21T17:56:34Z 2011-07-21T17:56:34Z <p>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 <a href="http://www.amazon.com/Nonuniform-Sampling-Information-Technology-Transmission/dp/0306464454/ref=sr_1_2?ie=UTF8&amp;qid=1311270632&amp;sr=8-2" rel="nofollow">Nonuniform Sampling: Theory and practice / Farokh Marvasti</a> from 2001. Hope it will answer my questions. Will be glad to be back with a concise answer to the benefit of others.</p>