The Fourier Transform, explained in one sentence (2014)
blog.revolutionanalytics.com
blog.revolutionanalytics.com
Any signal—like sounds or electrical signals, or even images—can be thought of as having a certain amount of 'energy' at any choice of frequency. This makes the most sense in music where we might thing of a 3-note chord as having 3 distinct packets of energy at 3 different frequencies.
For any given frequency, we can compute the amount of energy a signal contains at that frequency by comparing the signal with a test signal, a "pure tone" at that frequency. Pure tones are signals that have the unique property of putting all of the energy at exactly one frequency. The Fourier Transform is an equation which packages this idea up, showing us how to represent all of these measurements of energy at all frequencies.
The natural idea of a "pure tone" might be a sine wave. This is what we think of when we think of a musical pure tone and it certainly exists only at a single frequency. But sine waves make for bad comparison signals due to the problem of "phase": two sine waves played together can perfectly support one another and become twice as loud, or they can perfectly interrupt one another and become silence. This happens because sine waves oscillate between positive values and negative values and positive things can cancel out negative things.
When you look at the equation for the Fourier transform you'll see an exponent of a complex number. This is an improved version of a 'pure tone' which avoids the phasing issues of a sine wave. It does this by spinning like a clock hand in two dimensions, remaining always at the same length. This extra dimension lets us preserve enough information so that things never cancel out like with sine waves.
Here, I just tried to define them “Pure tones are signals that have the unique property of putting all of the energy at exactly one frequency” and then use sine as an example.
Truly, complex rotations are a much better definition, but it’s somewhat reasonable to expect people to be familiar with sine waves.
LTI systems closely model many practical systems, including the tuning forks and flutes that give our intuition of what a "pure tone" means. I guess there's a level after that noting that conservation laws lead to LTI systems. I guess there's further levels too, but I'm not a physicist.
That eigenfunction property means we can describe the response of any LTI system to a sinusoid (again, complex exponential in general) at a given frequency by a single complex scalar, whose magnitude represents a gain and whose phase represents a phase shift. No other set of basis functions has this property, thus the special importance of a Fourier transform.
We could write a perfectly meaningful transform using any set of basis functions, not just sinusoids (and e.g. the graphics people often do, and call them wavelets). But if we place one of those non-sinusoidal basis functions at the input of an LTI system, then the output will in general be the sum of infinitely many different basis functions, not describable by any finite number of scalars. This makes those non-sinusoidal basis functions much less useful in modeling LTI systems.
Zoom way in. If you go far enough it’ll just look like a curved line.
That curved line can be estimated down into a sin wave, or more accurately, a few sin waves that combine to make almost the same wave you have.
FFT is a way to take a complex wave and reduce it down to the sin wave components that would all combine to make it up.
To practically apply this, your voice recording is very high resolution and has a lot of bits at a high sample rate. If you instead used sin waves to represent the data, it could be almost as good sounding while being a lot less data to store.
… Watch a video. It’s something many people need to see to get.
I don't profess to be a DSP expert whatsoever, but the more familiar I've become with Fourier transformations, the more apt that analogy seems. Once you grasp that all sound is just a large addition problem of many, many sine waves, the ability to distinguish between them to a fairly high degree of fidelity feels almost like magic.
https://kinder-chen.medium.com/denoising-data-with-fast-four...
First, the Fourier transform does not just measure the 'energy' or amplitude of a single wave; it must also take into account its phase.
Second, complex exponentials are in no way an essential ingredient for defining the Fourier transform. We just work with them for computational simplicity, essentially because exp(ix) exp(iy) = exp(i(x+y)).
I also have trouble assigning meaning to your last paragraph. After all, complex exponentials can cancel just as much as sine waves (proof: sine waves are a combination of complex exponentials).
I'd love other thoughts on how to handle the ideas in the last paragraph. I'm not being technical, but am trying to allude to how the complex exponentials can capture more information more conveniently... and honestly waving my hands a lot. Really, I just want to explain why they're there instead of a more recognizable sine or cosine functions.
I've also tried to show the Fourier transform as the sum of a sine and a cosine transform, but that's too much, I think.
"There are many different ways to write down the number 5. Tally marks, the sigil 5, 4+1, 2.5 times 2, 10/2. Each of them is more or less useful in different circumstances. The same is true of functions! There are many different ways to write the same function. The mechanics of taking a function in one form and writing it in a new form is called a transformation."
Above needs to be said a hundred times. Then you talk about why a frequency space function can be useful. Then you talk about how to transform a time space function to the frequency space representation.
coupled with voidhorse's comment, it appears like "transform" obscures the concept whereas "translation" would be more appropriate and clearer.
Unfortunately I can't remember where I saw this explanation. It might've been in the Scientist's and Engineers Guide to DSP book.
That's only going to make sense for someone who understands your jargon usage of "correlate", and who groks that integrals of sine curves are orthogonal under addition. That's precisely the hard part the linked explanation is trying to explain.
If you've already gotten that far then the DFT is just calculator math.
At the totally basic level, another thing that I think can really trip people up and that a lot of texts are not clear about is that the transform is about moving between representations and that we're not actually transforming anything. Not enough maths texts take the time to explain how the representation connects up with the objects we wish to study and how there are multiple possible ways to represent them, and in some cases, like Fourier, useful ways to "translate" between different representations.
The extra tidbit - the sine waveforms are orthogonal to each other (their cross correlation is zero), so the transform can be inverted. (in math terms: they form a basis set. I'm mostly referring the STFT here, which is the 'common' FFT use. not infinite FFT).
You're going to need a longer sentence...
[Edit] If this sentence genuinely did what it said on the tin, the rest of the article - which give a lot more detail - wouldn't be necessary.
I have taught these kind of undergraduate subjects and, in the context of a course, the Fourier transform never struck me as something very complicated. First, it feels completely natural to write down a Fourier decomposition for periodic functions; the inverse transform to determine the coefficient is just (real or complex) calculus; and all that is left is to convince the audience of completeness which is best done through a few examples as well as the time-honoured method of "proof by intimidation". (Note that the blog post does not do a better job here.)
By contrast, these posts seem to fulfil a demand where people look for an isolated explanation of concept X, like Fourier transforms, matrix determinants, monoids, etc. But they are necessarily too isolated to really convey the subject. For example, one does not normally teach (complex) Fourier transforms without first dedicating significant time to topics like complex exponentials and integrals of trig functions, and likewise one normally teaches monoids only after introducing functors and applicatives.
In other words, without having the necessary background at your fingertips it is hard to really grasp the core concepts. That is why, IMHO, reading these blog posts may feel good but will rarely make things really stick.
Under your thesis one cannot "understand" anything physical (as in physics, chemistry, etc) as the underlying cannot be "proven", at all, by definition.
But usually true understanding and formal proofs go hand in hand.
P.S: Though as a disclaimer, I don't know maths beyond the undergraduate level, and I'm sure there must be very complicated concepts that mathematicians don't understand, but can reason formally about, as well as concepts that mathematicians feel that they intuitively understand but can't quite prove.
Additionaly, there's von Neuman saying "Young man, in mathematics you don't understand things. You just get used to them"
They’re also excellent to motivate a problem so the reader can find the technical details elsewhere.
It depends on what the intention is. Is it to promote comprehensive understanding, proof, and the ability to then apply the concept in all situations? Then no.
Is it just to point out something interesting a make a point? Sure. There's nothing wrong with that. It's OK to explore aspects of a subject without a dense canonical treatise. There's a time and place for all sorts of explanations.
It's great that it was "never complicated" for you. In contrast, the author (David Smith) of this blog post admits that he initially struggled with the Fourier Transform -- and wants to share some insights he gained after he understood it.
He has already graduated with a degree in statistics and computer science and also developed add-on software packages for R so he presumably first got exposed to FT within the _context_ of a college course. So he actually did what you suggested. Nevertheless, he wants to share why some supplementary material he didn't initially have might be helpful to others.
Alternative presentations of topics can sometimes flip the "light bulb" in some brains. I don't think it's a useless blog post.
I don't think they meant "not complicated to learn", but "never complicated to teach, once its time had arrived in the natural progression of the course".
Which is, of course, true for give or take all subjects out there
I don’t think it’s at loggerheads with just-in-time learning or the real opportunity cost of more extensive study. I think it’s just true that hard things are hard whether you like it or not.
Please stop making it sound like the commenter was bragging. That's just having bad faith in HN users.
The comment was about how the context and prior understanding of the underlying topics is a necessary prerequisite for understanding complex topics built on those and how blog learning is a necessarily contrived method of teaching.
It does not mean it won't work for some. If you happen to have the prior understanding of the prerequisites then it'd be a way to learn some additional insight, but you shouldn't assume the Venn diagram for that audience is much larger than a small % of the readers.
> If, like me, you struggled to understand the Fourier Transformation when you first learned about it
No where does the author imply that he is teaching the Fourier Transform to someone who has never heard of it.
I agree with your overall point. Blog posts are not going to teach you difficult mathematics unless they are the length of college textbooks. But a blog post like this is great for reinforcement. If, like me, you are an ECE (Electrical and Computer Engineer) who has written software for the last 15 years, an explanation like the one in the post makes a lot of neurons reconnect.
To that extent, this blog post seems valuable to me. The author is using a language and colors to convey an intuition that I have not precisely seen before.
This is what all these blog posts excel with.
Of course I got it along the way, but I do believe it would have been easier if the background was something like this.
It's bothersome how popularized the notion
I'm one,two,three,...,n blog posts/YouTube videos away from fully grasping this complex mathematical concept which not only requires fundamental knowledge I may not be familiar with, but also solving problems/writing code where at first I'll have no idea how is it supposed to be of any use but over time it will eventually 'click'.
Beautiful animations and witty narrations are nice, but you're in for a (bad) surprise if you think they're adequate. Also nothing beats good old book -> pencil/paper.
On a similar note, I personally believe there are many concepts that have been explained much better by random YouTubers than academic textbooks. Textbooks are more comprehensive almost always, but having an intuitive understanding of something is obviously more important in many cases than simply remembering a long list of bullet points about it. You can always use reference material later. In real life, memorizing facts on their own is rarely useful.
The best answer here is that you should use both, or imo, "all three," of blog posts, video content, and academic textbooks/articles/courses. Taking a variety of approaches helps me get to a mental "click" quicker, personally.
You're also right that explanations can't be isolated. I'd go further and say they never are. People only come to understand new things in terms of things they already understand. There's no "explaining X" in isolation, there's only "explaining X in terms of Y." A good explanation either supplies a suitable Y or makes it clear to the reader what Y they'll be relying on.
So, even if the author tries to isolate, a successful explanation always relies on collateral information. The only question is whether that collateral information is left to chance or intentionally exploited.
What's the "Y" here? Well, the author assumes the reader can make sense of phrases like "energy at a frequency", what it means to "spin your frequency around a circle", "average a bunch of points along a path", etc.
That's...a lot. I'd go so far as to say that a reader who can make sense of that probably already understands more fundamental concepts like vector spaces, bases, and Taylor Series.
And if they understand those things then there are much more straightforward explanations available!
You mean learning by writing a blog post, or learning by reading a blog post? In both cases, the answer is "yes".
> In other words, without having the necessary background at your fingertips it is hard to really grasp the core concepts. That is why, IMHO, reading these blog posts may feel good but will rarely make things really stick.
The problem these posts solve, at least for me, is that despite having the necessary background, some concepts didn't "click" in my mind when I first learned them. I found that if I then read a couple different posts on a specific concept, each with slightly different perspective or way of presenting it, one of them will eventually hit the "sweet spot" and make it "click" in context of all the background I already have (and often cascade into making me understand a few more things in the topical background).
But if you are organized, you'll start with the most likely place and progress to increasingly less likely places. When you find it, there's no surprise, and no one gets much of a chuckle over your efforts.
If you don't understand the problem space, then saying "That's the last place I would have looked!" is an expression of exasperation about your lack of knowledge.
I always assumed it was kind of a 'life's a bitch' aphorism
I’m currently in a phase where I don’t understand them.
Anything more specific than that should be handled case-by-case until you build an intuition for how any given monad will behave.
Computational context in this sense is like, is this computation of the type that can either fail or succeed? (Maybe monad). Or is this computation of the type that can produce multiple values of the same type? (List monad). Or maybe this computation can produce value of one type or another (Either monad). Or a computation that can interacti with inputs and outputs (IO monad).
So these are computations in differend kinds of computational "worlds" in a sense, with different rules on how such a computation in this context composes.
Are the constraints limited to return values or can there be other kinds of constraints?
It might be more helpful to think about this in terms of actual code samples. Consider a data type which can represent a computation which can fail. This data type has two possible states: ‘Failed’, and ‘Success(return_value)’ (where the ‘return_value’ field can be anything). Now, let’s say you have one result which might have failed, and you want to pass it to another fallible computation, which we can represent as a function from an input to a fallible output. How do you do it? Well, you might define a function something like this (in vaguely Rust-like pseudocode):
fn andThen(value, nextComputation) {
match value {
Success(return_value) => return nextComputation(returnValue);
Failed => return Failed;
}
}
Now let’s consider a different case: what if your computation is instead nondeterministic, and can return multiple results? In this case, you might instead have a nondeterministic value — let’s represent it as a list — which you got from one computation, and you need to supply it as input to another nondeterministic computation. Then you’ll need to write something like:
fn andThen_nondet(value, nextComputation) {
mut result = [];
foreach (v in value) {
result.concat(nextComputation(v));
}
return result;
}
Monads, therefore, are nothing special — they’re just data types with an ‘andThen’ method to let you sequence them. The method always has the same form: inspect the input to temporarily separate any returned value(s) from their context, then call the next computation to wrap those value(s) back up in the required context. This gets neatly summarised in the Haskell type signature:
(>>=) :: Monad m => m a -> (a -> m b) -> m bIt's essentially a mini interpreter for tiny functionally pure segments of a program.
One tricky part of the interpretation is understanding the most familiar monadic data types in this paradigm. For example, the list monad representing discrete nondeterminism.
Writing about this so tersely is probably only going to confuse anyone who isn't already 90% of the way to understanding....
well, it’s so simple: they’re just burritos!
[1]: https://byorgey.wordpress.com/2009/01/12/abstraction-intuiti...
After watching3Blue1Brown's video, I get it. So I can share with you what confused me:
It's this part of the sentence: "average a bunch of points along that path". I know what averaging it, but I don't know what averaging "along a path" means. Also I was (wrongly) expecting the output of this function to be a real number - I just expect "energy" to be a number. Instead, here what we're doing is averaging complex numbers so the output is a complex number. What a complex energy means is left as an exercise to the reader.
Here's my suggestion for a sentence that would have worked better for me:
"To find the energy at a particular frequency, spin your signal around a circle at that frequency, and find the center of mass of the plot."
Presumably then we have to take the distance from the origin to get an amount of energy.
They shouldn't be using the term energy, really. That should be reserved for the magnitude of the complex number (so re(z)^2+im(z)^2). You can write a complex number either as a real and imaginary part, or as a amplitude r (the distance you're referencing) and phase (the rotation from r+0im).
> "To find the energy at a particular frequency, spin your signal around a circle at that frequency, and find the center of mass of the plot."
As someone who's spent a lot of time with the subject, I like this better than the original.
As for a single line on intuition, can you beat: “method of decomposing a function into a sun of sines and cosines?”
The OP is better. It's the frequency that matters for intuiook, the shape of the periodic function is a technical detail.
But then, how is it different from Laplace transform?
(I have to admit, I actually learned about both during my uni time. But now I totally forgot them all.)
If you read more into it's history, the DFT actually helped a lot during the nuclear arms race as it can detect any nuclear test that happened anywhere except underground.
All of this is just linear algebra, with different linear transforms. A fourier transform is a linear transform that transforms point space basis to harmonic oscillation basis.
It's been a long time since I've thought about the Laplace transform, but IIRC, it has some properties that are preferable the Fourier transform as a math tool.
The Fourier transform better maps to an intuitive concept of frequency, which is why it is the basis for the transforms we actual use in practice in engineering, such as the discrete Fourier transform, which is what the famous FFT algorithm computes.
In high school physics some problems got way easier by redefining coordinates as x' and y', solving for those, them going back to x and y. That's what the Fourier transform does, but for functions.
Looking at its formula, we can see it looks like we are projecting a function into a series of complex exponentials, just like we need to project a vector in x' and y' for a change of basis in the euclidian space.
Then, the Fourier coefficients can be thought as "how much my function looks like a complex exponential of this given frequency". Compare the formulas for the Pearson Correlation and Convolution, they are almost the same.
Since the Fourier transform is just a particular case of changing basis, there are many, many other integral transforms that might be useful in different contexts. We can even create our own. But unis teach about the Fourier transform because it is really good for solving differential equations, which turns out to be a popular way of modeling problems in engineering.
It's exactly a change of basis
Sine waves aren't the only basis with which you can make this transformation. Your basis can be an arbitrary set of periodic functions as long as it meets certain requirements. Decomposition into wavelet functions is commonly used in seismic signal analysis, for example.
After being relieved of the burden of that misconception, I was finally able to understand the role of complex numbers in the Fourier Transform.
Later in that video, we see a visualization of the rotation. I was able to grasp how the exp function could yield rotation where I’d never been able to understand why e*e*e*e… did.
That “easy to remember” formula had been presented to me countless times. It only made sense once I stopped thinking about it in terms of repeated multiplication.
With that definition it's easy to derive the Taylor series expansion (every derivative at 0 is 1), and you can think of Euler's formula not as telling you how to evaluate exp(ix) (it's already perfectly well defined), but as an introduction of cos and sin as shorthand for its real and imaginary parts.
There is value in doing this expansion to teach the laymen, and the author does make the expansion somewhat in his post to be fair.
If:
. you have a vector space equipped with a dot product - say R³
. you have a specific orthonormal basis of said vector space - say (i, j, k) in R³
. you have a vector V - say V ∈ R³
. you want the coordinates of V in that basis
. then all you have to do is take the dot product of V with each member of the basis (i.e. you *project* V onto each basis member).
. in other words: V = Sum_over_basis_members[ individual_basis_member * Dot_product[V, individual_basis_member] ]
. the discrete Fourier transform (both signal and basis are discrete and finite, dot product is the usual suspect)
. the Fourier series (basis is discrete and infinite, signal is a continuous periodic function, dot product is the continuous version of the standard dot product, i.e. an integral)
. the Fourier transform (basis is infinite and continuous, signal is any "well-behaved" function, and the reconstruction of the "vector" involves a double integral, one for the dot product and one for the summation over basis terms)
. The "Vector" is any well-behaved periodic function (don't recall exactly what well-behaved entails, but not the most important part of the story anyways)
. The vector space is the set of well-behaved periodic functions
. The basis is the family of functions Exp[2*π*i] where the parameter i = {0, 1, 2, 3, ..., infty}
. The dot product is the cross-correlation between the function and a basis member: i.e. Integral[x=0, x=2*π, function*basis_member]
. You rebuild the function as:
function = Sum_over_basis_members[ basis_member Dot_product[function, basis_member] ]
1. I can't tell the difference between the pink and the purple in the formula. The text is fine, but the formula isn't. 2. I have no idea what "signal" means in the "spin your signal" so the single sentence explanation is completely useless to me.
This bums me out a bit because I think there's something really great here.
`x(t) = sum_k w_k sin(2pik*t)`
Then you just ask the question: given x, solve for w.
The next question is "why sinusoids", and the answer is that because for any linear, time invariant system acting on x:
y(t) = F[x](t)
that system diagonalizes over (complex) sinusoids:
y(f) = F(f)x(f)
Then you’ll immediately understand how the Fourier transform can be just a change of basis (a matrix multiplication in the discrete case).
If not here it is it's a great watch.
OK, that's a paragraph instead of a sentence, but it does motivate the whole raison d'etre of "why would I care anyway?"
If you want to try this for yourself grab a megabyte of photos of “conventionally attractive” selfies and a megabyte of selfies chosen at random and gzip them.
I’m personally not all that symmetrical so I don’t compress all that well. But I suspect you’ll find that “pretty” people compress better.
Same experiment with pop music vs serious jazz, same result.
I have a pet theory that everything from caffeine to alcohol is cropping in the Fourier domain.
It’s a fun experiment, try it out!
Asymmetry, blemish, teeth a different color than the corpus all consume entropy in the Shannon sense.
In a very real sense, movie stars are the most boring people to take still photos of.
I should have said JPEG or 264 or something: a DCT is what I meant.
Thank you for the correction.
There are many interesting applications, for example, voice recognition https://towardsdatascience.com/understanding-audio-data-four...
It is really amazing
An epistemological hurdle that really helped me was realizing these things like frequency and time domain aren't "real" as much as they are extremely useful mathematical models for manipulating things.
From how it's used and an interest history.
The fft is what you get when applying dynamic programming (memoization and recursive subproblem division) to the DFT.
You can see in the formula, that it's plugged in as the frequency of the signal the original signal is 'spun-around' with.
The last Fourier Transform explanation you will ever need.