0
$\begingroup$

I intended to use a discrete Fourier transform (DFT) on a time series sampled at uneven intervals. What I did was to calculate a DFT matrix where the elements are the values at the uneven locations like this

$$ {\displaystyle {\begin{aligned}X_{k}&= \frac{1}{\sqrt{N}}\sum _{n=0}^{N-1}x_{n}\cdot e^{-{\frac {2\pi i}{time_{N-1} - time_0}}k \cdot time_n}\\&\end{aligned}}} $$

where $time_n$ is the time location in the sequence and $time_{N-1} - time_0$ is the entire time span of all samples.

I realize that orthogonality of the basis vectors in the DFT matrix might get somewhat lost. Is anything more lost? Can I do something more to make the transformation more comparable to an ordinary DFT?

Here is an implementation of it you can try with your own data http://bodavid.github.io/Be10/Be10/public_html/index.html Orthogonality between basis vectors are visualized in a colorized matrix.

$\endgroup$
  • $\begingroup$ I hope you are aware of the procedures for DFT analysis of unevenly sampled data. There are various ways. Some people prefer NFFT. $\endgroup$ – Fat32 Jan 2 at 23:13
  • $\begingroup$ No, when I searched I only found recommendations to interpolate. $\endgroup$ – David Jonsson Jan 2 at 23:18
  • $\begingroup$ Do you want a practical code or theoretical end? (i.e., why did you try to formulate it by yourself ?) $\endgroup$ – Fat32 Jan 2 at 23:26
  • $\begingroup$ Both. I found it intuitive to adjust the DFT matrix to the points of measurements. $\endgroup$ – David Jonsson Jan 2 at 23:37
  • $\begingroup$ Ok. So if you need a library, go NFFT for a beginning. Or you can write your own from a few formulas (you can find nonuniform sampling and DFT here too). For a theoretical pursuit, notice that a mere re-locationing of the DFT basis is not sufficient for nonuniform to uniform conversion, as the previously hidden (located at nulling time positions) contributions from all other DFT basis must now also be included as they are no more nulled due to the uneven located data samples. $\endgroup$ – Fat32 Jan 2 at 23:46
0
$\begingroup$

I've run up this alley a couple of times. Let's look at what you've actually accomplished.

1) You picked an interval/DFT frame

2) You built basis vectors with sinusoids the length of the frame, including only the time points where you have samples.

As you observed, this is no longer an orthonormal basis. This means you are going to have to solve a matrix inverse to get your actual coordinates. With a regular DFT, the matrix is the identity matrix so solving the inverse is implied. The coordinates you solve for are very much like bin values at this point.

3) Your basis vectors are actually sampled points from continuous sinusoidal functions. Therefore you can construct a continuous function which includes all your original sample points.

What have you actually accomplished? Well, a very good interpolation of your data.

If it so happens that your signal is composed of tones that have a whole number of cycles, your coordinates/bin values will be spot on. However, if the tone is not a whole number of cycles, the leakage of your uneven sampling will not match the leakage of evenly sampled points, just as leakage doesn't match for different sized DFTs.

So, at this point, if you want to do any serious spectral analysis of your signal using DFT techniques, I agree with the recommendations you have gotten, resample your reconstructed signal at evenly spaced points and work with that.

You will get a different interpolation function for every different interval length. You need to be aware of the "wraparound" nature of the DFT. This means the interpolation function will repeat every interval length. Therefore you will want to make your interval wider than just the width of your samples. When you resample you will likely want to narrow the interval to just around your points. The extrapolations are useless.

Of course, there are much simpler interpolation techniques.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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