r/Python • • Oct 14 '19

When Python Meets Fourier Transform

2.3k Upvotes

122 comments sorted by

View all comments

74

u/__unavailable__ Oct 14 '19

That's a surprisingly intuitive way of depicting fourier series.

0

u/[deleted] Oct 14 '19

[deleted]

4

u/[deleted] Oct 14 '19

Could you prove that intuitively for a layman?

12

u/waxen_earbuds Oct 15 '19 edited Oct 15 '19

Consider the following approximate, ad hoc statement of Fourier’s theorem: any periodic signal may be represented as an infinite sum of simple harmonics. Well, okay, that’s great and all, but how does this apply here? The key is that op’s dog here is a closed path through the complex plane. In other words, given some amount of time that it would take to trace that path, given some parametrization, you have a notion of fundamental frequency. The component of the “dog signal” (DS) that is captured by that fundamental is encoded in magnitude (the radius) and phase (the starting angle) of the first line segment. As we discussed, the speed is encoded by the frequency that you define. This is a symmetry of a path representation of a complex signal, so you could think of there as being infinitely many possible “fundamental frequencies”. That center line segment traces a circle, which you could think of as a very crude approximation of the DS. Recalling the visual intuition for 2D vector/complex addition, if we added a complex number to this first fundamental signal, it would effectively extend the path in whatever direction our second segment was pointing by whatever its magnitude is. The second such segment would proceed at twice the speed of the fundamental, third thrice, ad infinitum, with each step providing a bit more clarity. We do this in harmonics of the fundamental frequency, since only integer multiples of the fundamental can be periodic with respect to the base signal. But thanks to Mr. Fourier, we know that is all we need. Just infinitely many.

In mathematical terms, you can think of the first circle as being some horizontal component Acos(wt+φ) and a vertical component Asin(wt+φ) for some amplitude A, phase offset φ, and fundamental frequency w=2pi/T, where T is the amount of time it takes to traverse the path. Should you choose to represent this as a complex number, using Euler’s identity, we have Aexp(i(wt + φ)). Since we have established that the amplitude and phase are unique for each constituent integer multiple of the fundamental frequency, we can represent this in general for the k’th such frequency as A_k exp(i(kwt + φ_k)). To sum this all the way to the number of circles at our disposal, we can represent our complex signal z parametrized by time as

$ z(t) \approx \sum_{k=1}N A_k e{i(k\omega t + \phi_k)} $

This is the statement of the discrete, complex Fourier series for a zero-offset path. There is much more to be said here, but I will refer you to Wikipedia or 3b1b for further elaboration.

Hope that helps!

3

u/DatBoi_BP Oct 15 '19

They more generally mean Fourier Transform. Anyway, the x–axis is real, y–axis is imaginary. Fourier Transform takes the "signal" (in this case, the set of points discretely outlining this animal) and essentially decomposes it into a bunch of amplitudes and phase angles (complex numbers' magnitudes and arguments, respectively) for a set of frequencies that depends on the sampling rate. These directly correspond to the circles we see—radius = amplitude; initial direction of line = phase angle; rate of change of line direction = frequency. Center the next circle on the end of the line of the current circle, and once you get to the last circle line, plot that point as it changes over time. That recreates the image

9

u/Helicon_Amateur Oct 14 '19

Can you elaborate?

89

u/[deleted] Oct 14 '19

"Hey, what's a fourier transform?"

Option 1: Present a bunch of equations

Option 2: The Fourier transform (FT) decomposes a function of time (a signal) into its constituent frequencies. This is similar to the way a musical chord can be expressed in terms of the volumes and frequencies of its constituent notes. The term Fourier transform refers to both the frequency domain representation and the mathematical operation that associates the frequency domain representation to a function of time. The Fourier transform of a function of time is itself a complex-valued function of frequency, whose magnitude (modulus) represents the amount of that frequency present in the original function, and whose argument is the phase offset of the basic sinusoid in that frequency. The Fourier transform is not limited to functions of time, but the domain of the original function is commonly referred to as the time domain. There is also an inverse Fourier transform that mathematically synthesizes the original function from its frequency domain representation.

Option 3: Here's a spirograph drawing a dog

0

u/[deleted] Oct 14 '19

[deleted]

24

u/ForgottenWatchtower Oct 14 '19

Nothing is stopping you. Plenty of info freely available on the web. 3b1b is a great YT channel to refresh/learn many mathematical fundamentals, including Fourier transforms.

8

u/waxen_earbuds Oct 14 '19

If you want to understand it at the level of the person you are replying to, you are better off studying applied math.

16

u/[deleted] Oct 14 '19

while true, i just copied wikipedia's intro paragraph

2

u/[deleted] Oct 14 '19

You should look into DSP. It's not just an engineering problem - Carl Friedrich Gauss apparently made bank on the stock market using signal processing techniques.

1

u/[deleted] Oct 15 '19

It's called technical analysis. There's a python binding for the TA-lib. But it's a good way to go broke because everyone else is also doing TA on stocks and they'll beat you to it.

3

u/PM_ME_VINTAGE_30S Oct 14 '19

I'll take option 2 for $500. No but seriously, I'm saving this. I'm in diff EQ and I think I'll be learning this formally in about a month. 👍Ofc I'm an electrical engineering major and I intend to specialize in DSP so Fourier transforms will be life.

6

u/potatochemist Oct 14 '19

Essentially, if you add up the right combination of sine waves with different heights and speeds, you can recreate any function/graph/picture.

3

u/Helicon_Amateur Oct 14 '19

Okay. Now I get it and feel really stupid for not thinking of it that way. I understand what an FFT does but didn't relate it to this picture.

So each frame of this drawing should then consist of a peice of a signal, say there is this really long signal in the time domain - then stepping over a finite chunk of that signal would produce this graph, is that correct?

4

u/potatochemist Oct 14 '19

The "signal" is the shape of the dog. However instead of volume over time (like a microphone), it's x-y pairs over time where each pair is a point somewhere on the dog.

They then take the FFT of this to get the size and speed (magnitude and frequency) of the sin waves shown by the circles.

Here's a gif of the same thing with a time signal (like volume).

Here's a really good video if you want to get a bit deeper.

3

u/FauxReal Oct 14 '19

Funny lookin' muzzle on that dog of yours.

5

u/AnythingApplied Oct 14 '19

One thing to be careful of is that this fourier transform isn't just based on the shape, but more specifically the shape and speed of drawing. If the pencil is drawing at a constant distance per unit time vs constant angle from the origin vs any other speed arrangement, you'll get a different fourier series.