Discrete fourier transformation from a list of x-y points

Question

What I'm trying to do is, from a list of x-y points that has a periodic pattern, calculate the period. With my limited mathematics knowledge I know that Fourier Transformation can do this sort of thing.

I'm writing Python code.

I found a related answer here, but it uses an evenly-distributed x axis, i.e. dt is fixed, which isn't the case for me. Since I don't really understand the math behind it, I'm not sure if it would work properly in my code.

My question is, does it work? Or, is there some method in numpy that already does my work? Or, how can I do it?

EDIT: All values are Pythonic float (i.e. double-precision)

Answer 1

For samples that are not evenly spaced, you can use scipy.signal.lombscargle to compute the Lomb-Scargle periodogram. Here's an example, with a signal whose dominant frequency is 2.5 rad/s.

from __future__ import division

import numpy as np
from scipy.signal import lombscargle
import matplotlib.pyplot as plt


np.random.seed(12345)

n = 100
x = np.sort(10*np.random.rand(n))
# Dominant periodic signal
y = np.sin(2.5*x)  
# Add some smaller periodic components
y += 0.15*np.cos(0.75*x) + 0.2*np.sin(4*x+.1)
# Add some noise
y += 0.2*np.random.randn(x.size)

plt.figure(1)
plt.plot(x, y, 'b')
plt.xlabel('x')
plt.ylabel('y')
plt.grid()

dxmin = np.diff(x).min()
duration = x.ptp()
freqs = np.linspace(1/duration, n/duration, 5*n)
periodogram = lombscargle(x, y, freqs)

kmax = periodogram.argmax()
print("%8.3f" % (freqs[kmax],))

plt.figure(2)
plt.plot(freqs, np.sqrt(4*periodogram/(5*n)))
plt.xlabel('Frequency (rad/s)')
plt.grid()
plt.axvline(freqs[kmax], color='r', alpha=0.25)
plt.show()

The script prints 2.497 and generates the following plots:

Answer 2

This page from Scipy shows you basic knowledge of how Discrete Fourier Transform works: http://docs.scipy.org/doc/numpy-1.10.0/reference/routines.fft.html

They also provide API for using DFT. For your case, you should look at how to use fft2.