# What is the optimal adaptive grid for calculating a DFT using a fixed number of sampling points?

I'm currently facing the following problem: I want to approximate the Fourier transform $F(\omega)$ of a (let's say, $L^2(\mathbb R)$) function $f(x)$ by calculating the discrete Fourier transform, using only a fixed number of sampling points. These points are allowed to lie arbitrarily far away from the origin. In addition, we don't care about computational costs, so the grid can be chosen completely free.

What is the optimal (with respect to minimizing the error) choice for the grid?

I guess that this choice is dependent on the bandwidth $B$ of $f$. Does this mean that Nyquist-Shannon forces the grid to being broader than $2*B$?

Also, I found literature about sparse Fourier transform sampling in case of known sparsity in $F(\omega)$ (compressed sensing). But since my signal does not appear to have sparse support in the frequency domain, I don't see how these methods would be applicable in my case.

This can be split up in two questions for the sampling frequency and the window.

1) The required sampling frequency is given by the Nyquist theorem to be $f_s>2*f_{max}$ with $f_{max}$ being the largest frequency in your signal. When sampling actual signals with an ADC there is usually a low pass filter to ensure an upper frequency limit.

2) The function $f(x)$ is usually defined to $-\infty<x<\infty$. However, you can only pass a finite portion to the DFT. The DFT is not a time-discrete Fourier Transform but a Fourier Series. Hence, it is defined on periodic signals.

If your signal is actually periodic then it is favorable to perform the DFT over whole periods. From the DFT's point of view, the signal you hand to it is repeated infinitely and when you pass it an incomplete period, there will be border effects resulting in frequencies showing up that are not in the original signal.

If your signal is time limited, all of it should be contained in the vector you pass to the DFT.

If the signal is neither time limited nor periodic you would theoretically need a DFT with infinite length, simular to the actual Fourier Transform which is defined for $-\infty<x<\infty$. Since this is not possible, Spectral Density Estimation techniques can be employed. The data can then be visualized with Spectogram plots showing the frequency content over time. It depends on what you are trying to achieve, really.

• You are right, I have to get more specific concerning the type of functions I want to transform. In fact, my function has compact support, which can be arbitrarily wide. Also there is some (but no fast) decay with increasing distance to the origin. I will rethink about it and regard this question as answered. – tomglabst Jul 25 '13 at 14:18