I've been thinking a lot about how to apply FFTs to neural networks, so this is timely; thank you.<p>If you're looking for deeper explanations, I recommend "Practical Signal Processing": <a href="https://www.amazon.com/Practical-Signal-Processing-Mark-Owen/dp/1107411823" rel="nofollow">https://www.amazon.com/Practical-Signal-Processing-Mark-Owen...</a><p>Many of the chapters are here: <a href="https://battle.shawwn.com/sdb/books/PSP/" rel="nofollow">https://battle.shawwn.com/sdb/books/PSP/</a> but buy the book if you can afford to.<p>In particular, Chapter 4's "untwisting" intuition is the best I've found: <a href="https://imgur.com/a/r7KvO60" rel="nofollow">https://imgur.com/a/r7KvO60</a><p>Another way of phrasing it: You know that effect when a wheel is spinning so fast, it looks like it's going backwards? If it looks like it's standing still, there's a Fourier coefficient at that rotational frequency.<p>... Or at least, I think there is. It's hard to be precise with analogies.
From the beginning of the article:<p>> The Fourier Transform is one of deepest insights ever made. Unfortunately, the meaning is buried within dense equations<p>The post does a great job at explaining what the Fourier transform means, but I am always skeptical of sentences like this. It's a pattern found in many other posts too: "unfortunately" this concept is expressed in math form, let's try to solve this problem.<p>I find that it's exactly the other way around. Math and math notation is dismissed too early and too easily even in engineering studies, resulting in shoddy and imprecise definitions and understandings.<p>> The Fourier Transform is one of deepest insights ever made. <i>Fortunately</i>, the meaning is <i>engraved</i> in dense equations
At the end of these types of popsci explanations you still can't grok the math any better and you end up with a hand-wave-y misleading understanding of what's going on.<p>It starts off by saying that the Fourier Transform "measures every possible cycle". This is an <i>wrong</i> approach to thinking of the Fourier Transform. If you think in these terms you will quickly get lost. The Fourier basis is a set of sinusoids that are mutually orthogonal (ie. none can be represented as a combination of the others). They just happen to generally cover the frequency ranges you're interested in (though this depends on your problem). If you choose some random sinusoidal signal that isn't a harmonic of your sampling period, then the Fourier Transform gives you back a mess that's hard to interpret (how a off-harmonic sinusoid gets "smeared" across the basis is actually something I frankly still don't quite understand <a href="https://ccrma.stanford.edu/~jos/mdft/Frequencies_Cracks.html" rel="nofollow">https://ccrma.stanford.edu/~jos/mdft/Frequencies_Cracks.html</a> )<p>This is in contrast to the phase information that you get that <i>is</i> continuous. Each frequency has two associated basis vectors and they can give you any phase offset. The frequencies are only set harmonics, but the phase can be any value. This is the result of how the basis is setup. If anything, the phase information you get from the Fourier transform is more interesting than the frequency information you can glean.<p>The "Circular Paths" visualization is also highly misleading. The complex plane is a crutch that gives you pretty pictures. It pretends to be like a 2D plane but it's actually fundamentally distinct from a Cartesian/"normal" X-Y plane b/c complex numbers can be multiplied while normal [x,y] pairs can not (b/c the operation is simply undefined - you can't multiply two points on a map). The product of two complex numbers is giving you another complex number.. but good luck visualizing where that point ends up! You'll notice all complex plane examples stay on the unit circle b/c you get a "rotation" but it's an edge case. The whole 2D analogy is setting you up to be very confused
What about the 3 blue 1 brown video on it? I think that is pretty concise and intuitive too but does not seem to appear on this thread <a href="https://www.youtube.com/watch?v=spUNpyF58BY&ab_channel=3Blue1Brown" rel="nofollow">https://www.youtube.com/watch?v=spUNpyF58BY&ab_channel=3Blue...</a>
The only way I have been able to understand it:<p>- Functions can be thought of as vectors in an inner product space (<a href="https://www.youtube.com/watch?v=TgKwz5Ikpc8" rel="nofollow">https://www.youtube.com/watch?v=TgKwz5Ikpc8</a>)<p>- the "inner product" operation (integral of the product of the two functions): imagine what would happen as you approximate functions as discrete vector with a very high number of dimensions/co-ordinates and computed the dot-product between those two vectors, but scale the result to be invariant of how many dimensions you used to approximate it => you get the integral formula<p>- Now, it's just normal linear algebra:<p>- The "length" of one of these vectors can now be thought of as the square root of the inner product of the function with itself<p>- The "distance" between two functions can now be thought of by subtracting one function from the other, to get a new "vector/function", and compute its length<p>- The cosine of the "angle" between two functions is the dot product between two functions scaled to have length 1<p>- The functions describing a sine or cosine wave are vectors which have a inner-product against themselves of 1, and a dot-product against any other frequencies of 0<p>- Thus the different frequency functions/vectors form an orthonormal basis<p>- This means that you can find the co-ordinates of any function by taking the inner product of the function against each fourier basis function<p>- The "co-ordinates" of your function w.r.t. the orthonormal basis can be computed by taking the inner product against each basis function/vector<p>- This will be the point that minimizes the distance to your actual function<p>- These "co-ordinates" are the fourier co-efficients for the fourier series representation of your function<p>- For non-periodic functions, you can take the limit as your period goes to infinity, that gives you the fourier transform representation.<p>Or, in short:<p>1. Functions can be thought of as vectors in an inner product space (<a href="https://www.youtube.com/watch?v=TgKwz5Ikpc8" rel="nofollow">https://www.youtube.com/watch?v=TgKwz5Ikpc8</a>)<p>2. The Fourier series functions form an orthonormal set of basis vectors<p>3. Now just use normal linear algebra to work out the co-ordinates of your function w.r.t 2
The most intuitive explanation I've seen, although a bit abstract, is that Fourier transforms, and the other Fourier-like transforms including the s and z transforms, are just about changing the system of coordinates of the data vector using the transform's generative vectors.<p>Indeed we can easily see that the definition of all those transforms take the form of the sum of a scalar product that computes the projection of the data vector unto the kth dimension in the transformation (e.g. frequency) space.
I see this particular mistake crop up a lot, and it's a bit pedantic, but I don't get the impression that it's being intentionally ignored for educational reasons: The author repeatedly describes "the" recipe, "the" set of frequencies, .... The standard Fourier transform is only unique conditioned on the fact that we've agreed on a particular set of basis functions ahead of time. It isn't even the only choice of orthogonal exponentials we could have picked.<p>In terms of real applications that point often doesn't matter much -- especially in fields like lossy compression where you might not actually care much about any underlying meaning in the representation, and especially in fields like radio where your data is in some sense fundamentally represented as combinations of sinusoids -- but in general it isn't a sound leap to go from "this Fourier coefficient is big" to "there exists a big sinusoid that semantically matters to my data."
Cool article.. For some application - see <a href="http://www.dspguide.com/pdfbook.htm" rel="nofollow">http://www.dspguide.com/pdfbook.htm</a>
> Here's a plain-English metaphor:<p>> What does the Fourier Transform do? Given a smoothie, it finds the recipe.<p>> How? Run the smoothie through filters to extract each ingredient.<p>> Why? Recipes are easier to analyze, compare, and modify than the smoothie itself.<p>> How do we get the smoothie back? Blend the ingredients.<p>This has to be the absolute worst attempt at an explanation ever. Even the "monads are a burrito" thing is better.