1
$\begingroup$

Does anyone have a reference that specifically discusses choosing the frequency scale for a simple 1D data for non-uniformly sampled time-domain data when performing the discrete Fourier transform.

In the ordinary uniform sample case, $N$ be the total number of samples in the signal, and $T_s$ be the sampling period (the inverse of the sampling frequency $F_s$ ). The uniform DFT will convert a sequence of $N$ numbers $x[n]$, where $n=0,1, \ldots, N-1$, into another sequence of $N$ complex numbers $X[k]$, where $k=0,1, \ldots, N-1$. The frequencies corresponding to each $k$ are given by: $$ f_k=\frac{k F_s}{N} $$

In MATLAB, the non-uniform DFT is defined as Link

Nonuniform Discrete Fourier Transform of Vector For a vector $X$ of length $n$, sample points $t$, and frequencies $f$, the nonuniform discrete Fourier transform of $X$ is defined as $$ Y(k)=\sum_{j=1}^n X(j) e^{-2 \pi i t(j) f(k)} $$ where $k=1,2, \ldots, m$. When $t=0,1, \ldots, n-1$ and $f=(0,1, \ldots, n-1) / n$ (defaults for nufft), the formula is equivalent to the uniform discrete Fourier transform used by the $\mathrm{fft}$ function.

Furthermore it suggests

The nonuniform discrete Fourier transform treats the nonuniform sample points t and frequencies f as if they have a sampling period of 1 s and a sampling frequency of 1 Hz for the equivalent uniformly sampled data. For this reason, include the scaling factor T to the time vector when using nufft to obtain the transform with correctly scaled units. Plot the absolute value of the transform as a function of the default frequencies that are scaled by Fs.

In such case is there a protocol as to how one should make a frequency grid?

I cannot find selection of the frequency scale in nonuniform DFT discussed in detail anywhere.

For example, if we have exponential time-domain sampling protocol, or a random sampling, are there any constraints on how the frequency axis is chosen after the transform?

The link above includes the code:

    Y = nufft(X,t);
    n = length(t);
    f = (0:n-1)/n;
    plot(f,abs(Y))

which uses uniform sampling in the frequency domain. The function nufft gives the option of passing in the frequency axis using the Y = nufft(X,t,f). Can I choose f arbitrarily?

$\endgroup$
2
  • $\begingroup$ Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Signal Processing Meta, or in Signal Processing Chat. Comments continuing discussion may be removed. $\endgroup$
    – Peter K.
    Feb 7 at 13:48
  • $\begingroup$ Wouldn't it make sense to use the minimum sample spacing in the time domain to define the extent of the frequency axis, and also use maximum time duration to define its sample spacing? That is, $\Delta f = 1/\max_i{\mathrm{range}(\mathbf{t}_i)}$, and $\mathrm{range}(f) = 1/\min_i{\Delta t_i}$. $\endgroup$ Feb 23 at 16:33

1 Answer 1

1
$\begingroup$

Can I choose f arbitrarily?

Yes and no.

Theoretically, you can perform a "DFT-like" operation with any set of N time samples {t_n} at any set of K frequencies $f_k$ simply as

$$X(f_k) = \sum_{n=0}^{N-1} x(t_n)e^{-j2\pi f_k t_n} \tag{1}$$

This can be written in terms of a Matrix operation as

$$\overrightarrow{X_d} = M \cdot \overrightarrow {x_d} \tag{2}$$

where $\overrightarrow{X_d} = [X(f_0),x(f_1), ..., X(f_{K-1})]'$, $\overrightarrow{x_d} = [x(t_0),x(t_1), ..., X(t_{N-1})]'$ and

$$M = \begin{bmatrix} e^{-j2\pi t_0 f_0} & e^{-j2\pi t_1 f_0} & ... & e^{-j2\pi t_{N-1} f_0} \\ e^{-j2\pi t_0 f_1} & e^{-j2\pi t_1 f_1} & ... & e^{-j2\pi t_{N-1} f_1} \\ & & ...\\ e^{-j2\pi t_0 f_{K-1}} & e^{-j2\pi t_1 f_{K-1}} & ... & e^{-j2\pi t_{N-1} f_{K-1}} \end{bmatrix} \tag{3}$$

For $K=N$ the matrix becomes square and may be invertible, i.e. you may able to recover all points in time from all frequency samples. The "may" requires that all points in time and frequencies are "sufficiently different". Technically this should always be the case if the vectors are unique but inverting a matrix is numerically challenging and any type of "clustering" of time or frequency instances will make this numerically very difficult and extremely sensitive to any type of noise.

While the choice is theoretically arbitrary, there are lot of practical considerations a big one being: what are you planning to do with the data and what properties/requirements does your application have.

This being said, Matlab's default (uniform sampling) should be a good starting point for many use cases.

$\endgroup$
2
  • $\begingroup$ Thanks for the post. My main interest is in chemical instrumentation. Suppose a instrument generates a free induction decay (exponentially decaying sinusoids). It may consist of 100k points collected over microseconds. The FID is DFT'ed to get a spectrum of molecular frequencies. So I may not need to go back. $\endgroup$
    – AChem
    Feb 8 at 14:16
  • $\begingroup$ The key point is if we have different "types" of sampling, say random sampling, exponentially sampling, does the MATLAB suggestion to make the frequency axis still hold? I have been trying to find references but nobody clearly discuss the frequency axis generation. $\endgroup$
    – AChem
    Feb 8 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.