Huh. Just a thought, is there a point in the "whip" of the chain there where the overall curve of the lines approaches the same shape you get from i^i^i^i^i^i...(etc)?
Minor nitpick: When hovering over the slide buttons, the mouse changes to a hand symbol which indicates that dragging should be possible, but it is not. Maybe if it acts like a checkbox, it should look like a checkbox?
They are draggable, but it will not register as a transition unless the mouse button is released while still hovering over the slide button. It is effectively just a checkbox.
This article has several nice plots, but IMO the wikipedia does a better job describing Fourier transforms than this article. A few things that article alludes to, but not clearly states is FT ability to convert between time and frequency representation of a wave.
Another question worth at least cursory mention: what is so great about sine waves (or complex exponents)? Why are they better than, say, step functions for decomposition of many physical phenomena? Even a couple of quick examples would be helpful (drop a stone into a lake; what shape are the waves? extra credit -- why?).
Above may sound harsh, which was not my intent; I just think expanding a little can give a much better view of the algorithm and its applications.
Sine and cosine waves whose frequencies are multiples of a fundamental frequency, form an orthonormal basis w.r.t. the inner product given by integrating f(x)ĝ(x)dx over one period of the sine (or cosine) wave whose frequency is the fundamental frequency. In practical signal processing, this means that we can separately consider the contribution of each frequency to the total energy of a signal. Technically, the above only explains Fourier series, but the Fourier transform is just the limit case when the fundamental frequency is made arbitrarily small (re-scaled by a factor of the size of Dirac's delta at 0, of course).
They can[0]; however, this requires some further construction.
One major benefit of the sin/cos basis is that each basis function maps uniquely to a dirac delta in frequency space. This allows for power/energy symmetries between time and frequency domain representations of a signal and allows for more tenable frequency filtering, e.g. removing 60/50Hz noise or isolating a particular frequency band.
A haar wavelet or modified square wave basis may provide you with a simple orthonormal signal basis, but each wavelet has a frequency representation with infinite support in frequency space. This is (a) untenable and (b) eliminates the possibility of frequency-specific filtering. Wavelet analysis is more useful in specific cases.
When you use the term "frequency space", you are already thinking in terms of the frequency of sin/cos functions. If you actually think in terms of frequency in a different orthonormal basis, you'll find that the dirac delta characteristic you mention is not specific to sin/cos, thereby invalidating your argument.
Totally of the cuff: I believe you can recast the Sims in the discrete Fourier transform as integrals of step functions. So it should work. However the width of the steps in the discrete dirtier transform is fixed for each n. So you'll need to be a bit clever to make sure your steps line up right of you want to build up a single infinite basis. And I would be a bit afraid that the need for things to line up would end up losing some needed span... So at least the are done things which need to be checked.
The sin and cos basis is very convenient. Even more convenient is the e^(i.n.t) basis...
>Sine and cosine waves whose frequencies are multiples of a fundamental frequency, form an orthonormal basis w.r.t. the inner product given by integrating f(x)ĝ(x)dx over one period of the sine
This, by the way, was perhaps the most mindblowing thing I learned in my advanced linear algebra course. I had already learned about applied Fourier Transforms and the FFT, but seeing the same tools we had used to prove things about Cartesian bases could be applied to something so unexpected, with such powerful results, was incredible.
The "magic" of the Fourier transform and DFT is entirely contained in this proof, IMO. I think a lot of people find the Fourier transform extra-amazing because it is their first encounter with basis change and infinite dimensional vector spaces.
"Complex exponentials are the eigenfunctions of linear systems."
This means that, if you put a complex exponential in, you get the same complex exponential out, scaled by some constant, whose magnitude we call the "frequency response". No other functional form has this property.
They are eigenfunctions, so they are orthogonal. We can represent any function in L2 using a weighted sum of them.
My explanation for why we use complex exponentials in waves analysis, in two common cases:
In the first case, when you're solving a differential equation like
f(t) = - C^2 * d^2/dt^2 f(t)
you have several different ways of representing the entire family of solutions, all valid. Here are some:
A*cos(Cx+phi)
A*cos(Cx) + B*sin(Cx)
A*e^(±iCx)
So at least two of these solutions only involve real numbers. However, it turns out from experience that this is actually harder to work with; it's more annoying to keep track of phase or FOIL cross-terms than it is to work with complex numbers. Your equations end up with fewer terms when you use complex exponentials. Then, because we're working with linear systems, you can simply add up your complex solutions in such a way that the complex numbers cancel out and you're left with a real-valued solution that works for physical waves.
In the second case, we use complex numbers to keep track of something. Like when you're doing a Fourier transform, you break down a signal into its different frequency components. However, a signal made up of a 500hz sine wave is going to be shaped differently from a signal made of a 500hz cosine wave, so we have to keep track of those separately. Conveniently, e^(ix) = cos(x) + i sin(x), so we use a complex number to represent the presence of a 500hz cosine wave (real part) and a 500hz sine wave (complex part) while keeping our equations simple. That's sort of a practical overview; a deeper understanding can come from learning linear and abstract algebra.
It's amazing how almost every one of these articles about the Fourier Transform actually only talk about Fourier Series. Perhaps because most of the people who write these articles themselves lack an intuition for Fourier transforms (hint: there isn't much)?
I was just going to post that. I don't think any other explanation or tutorial does a more complete-yet-understandable job of explaining how the DFT actually works. I feel like there are a million articles out there that do basically what this article does, which is to explain kinda-sorta what the Fourier Transform is (i.e. "make a wave using other waves!") but never go into any detail about how you select which constituent waves contribute to the overall wave etc., and so I was always left unsatisfied.
That's true, but it's kind of the same idea, so it's okay. The best way to understand this, for people who are familiar with linear algebra, is to think of the Fourier transformations as change-of-basis operations that convert signals from a time basis to a frequency basis. Depending for the bases for the time domain and the frequency domain, you get the Fourier series, Fourier transform, or Discrete Fourier transform[1].
I find the Fourier series is the hardest to understand intuitively (compared to FT and DFT), since the time basis (periodic functions of time) and the frequency basis (infinite sequence of Fourier coefficients) look very different.
I never really intuited how the time domain and frequency domain related until I looked at the animation mentioned in the article[1] - I really wish I had seen that gif earlier since it shows the frequency and time domains as orthogonal (literally).
Edit: I've realized that our comment was on series, not transforms.
What do you mean, not much intuition for Fourier transforms? Sure, sometimes you get weird results and need to work with fairly generalized versions of functions, and a bit of background in functional analysis is helpful, but a strong intuition about the Fourier transform is both extremely useful, and not that hard to develop.
Thank you for the link!
I used Stanford handouts for every subject I could find, they are usually excellent, like a better and more rigorous Wikipedia article.
I'm still trying to understand the convolution of two functions. Every God damn text ist only about how useful the Fourier series are - that's it.
(Math student)
Since you mentioned that you are a math student, I highly recommend Stein and Shakarchi's "Fourier Analysis: An Introduction".
It is a rigorous treatment that covers a lot of the essentials of Fourier theory, while also covers some very interesting "math applications" (e.g Dirichlet's theorem on primes in arithmetic progressions at the end), as well as "mixed applications" (e.g Radon transforms that are used in imaging but are also of interest from a math perspective).
Note that this book requires an introductory analysis class as a prereq; basically you need to be familiar with the standard Riemann integral theory and rigorous treatment of limits, continuity, and derivatives.
It's much easier to get an intuitive understanding of convolution directly in the time domain, without worrying about Fourier Transforms.
Convolution with a top-hat kernel is just a moving average. Each point of the output is the average of the input signal over a given radius about that point.
Convolution with other kernels is a weighted moving average. Each point of the output is the average of the input signal over a region with weights depending on the displacement from that point.
The Fourier Transform allows implementing convolution as multiplication in frequency space (because the Fourier transform turns translations into multiplications), which is sometimes formally useful, and sometimes more efficient to evaluate.
I similarly struggled to get intuition on the convolution operation, until the following simple idea clicked. Think of convolution as similar to elementary school long multiplication, but without carries. (Also, if you are working with vectors of of some length N, the multiplication "wraps" modular-arithmetic style around the end of the vector back to the beginning.)
I think it's because they're meant to explain Fourier transforms to people who aren't familiar with transforms, and therefore are much more comfortable with Fourier coefficients rather than an actual transform in the frequency domain.
According to the comments I'm the only one who liked the article. I've had a lot of math but never any signal processing (i.e. FT) and never really got to wrap my head around the concept of a FT. I realize that the person here is making a lot of simplifications but you've gotta start from somewhere. Great job on making an article that is both engaging but still "mathy".
Can't please everyone I guess ... especially not on HN.
The article is all right. I would have liked to see somewhere a mention of the fact that the transform being described moves between the time and frequency domains, and that the relationship is reciprocal.
Fourier series (and transforms) are probably my most favorite mathematical tool in physics
It has the power to transform nasty or complicated operators into something more manageable: derivatives turn into multiplication by the wavevector, linear differential equations turn into finding the roots of a polynomial, integration over all of space turn into an (infinite) sum over all wavevectors, convolutions turn into pointwise multiplications, ...
Later you learn that Fourier series are just one example of an application of the linear algebra concept of decomposing a vector onto an orthogonal basis, with the vectors in this case being functions, but the original will always have a special place in my heart
There's an interesting book about Fourier and his series and transform written for a general audience: "Who Is Fourier? A Mathematical Adventure" [1], by an organization called the Transnational College of LEX (which seems to have some sort of connection with Hippo Family Club[2]).
The only math assumed going in is basic high school algebra.
They also have a book on quantum mechanics ("What is Quantum Mechanics? A Physics Adventure" [3]) and biology ("What is DNA? A Biology Adventure"[4]).
"Who is Fourier?" is the absolute best math book I've ever seen. I loved it, and recommend it to anyone interested in math (and even more to those not YET interested in math).
Here is an easy explanation, before computers the Fourier transform of sound was computed using a bank of filters. Each filter was tuned to detect a certain frequency.
To go back from frequency to the original sound you have to replace the filters by sound generators (generating the same frequency the filter was tuned to)
In my interactive sample below I have a filter tuned for each note of the piano (you'll need a microphone)
Fourier transform (any kind of transform, really) is at the same time so simple and so mind-boggling. The math to produce it just fits together super neatly: applying algebra principles (basis change, dot products, etc.) to functions, and seeing that it works really is a stunning achievement of mathematics.
I sometimes wonder if analysis could have been discovered the other way around, that functions could have first been described as a sum of harmonics, and that we would have stumbled upon "time-defined" functions as the inverse fourier of harmonics.
If you don't know about the FT, you should really dig into it. It's way simpler that number theory, cryptography or complexity theory, yet it is incredibly useful and frankly beautiful.
An old Yamaha FM synthesizer is a fun way to play around with this concept, making familiar waveforms from sines either by playing a series of operators in unison at different frequencies, or more efficiently: modulating one operator with another at a certain frequency ratio.
I don't remember off the top of my head, but I think a it's a 1:2 ratio of carrier to modulator sine that mimics a square wave pretty well.
A while ago when I was researching how the Yamaha OPL-series FM synths work, one program that I found was an instrument-builder. It gave you direct control over the hardware registers and showed some information about the waveforms that would be generated, if I'm remembering correctly.
Dosbox has an OK OPL3 emulator built into it, so that's an easy, software-based stack to work from (ummm....if I could re-find the program that I was using).
Adding sines is the basis of additive synthesis, you are correct about the ratio, i have made a visual additive synth which is just adding alot of sinewaves (Y axis represent frequencies)
an interesting fact not mentioned in the article is that Gauss invented the fast fourier transform before the digital computer was even invented, that is, the divide-and-conquer algorithm. genius!
I've been using the DFT and FFT for so long in my work as an electrical engineer, I sometimes forget the beauty of underlying concepts and equations, especially since one need not ever code one up as implementations exist in just about every computer language there is. That such a simple equation has such a profound impact on modern life is wonderful.
I can recommend 'Who is Fourier?' By the Transnational College of Lex. It assumes very little prior knowledge and introduces the reader to, among others, the concepts of trigonometry, calculus, imaginary numbers, logarithms and Fourier analysis.
I wish I'd known about this book when I was studying maths at school.
> As the string vibrates, the air molecules around it bounce to and fro, creating a wave of jiggling air molecules that we call sound. If you could watch the air carry out this periodic dance, you’d discover a smooth, undulating, endlessly repeating curve that’s called a sinusoid, or a sine wave.
That's a remarkably poor description, I think? It could make a young reader imagine the sine graphs are there in the air, but very hard to see. I guess to construct the wave you'd do something like measure density changes at a single point in space?
All of these transforms are trying to take a given signal and find ways to construct it using "atoms" taken from a "dictionary". By looking at which atoms of the dictionary you used, you get an idea of what the signal is made up of.
The discrete cosine transform is awfully similar to the discrete fourier transform. They are conceptually the same and just have minor technical differences. The DCT and DFT's dictionaries are made up of sine and cosine wave atoms at different frequencies. These waves are all infinitely long, so they work best at representing signals which are repetitive over their whole length. They don't do a very good job at noticing where interesting parts of a signal are.
A wavelet is like a small chunk of sine/cosine wave. Instead of being infinitely long, it only exists over a small length of time/space. The wavelet dictionary contains wavelets in different places as well as at different frequencies. So when you decompose using wavelets they do a better job of encoding where the interesting bits are. Wavelets assume your signal might be periodic in particular areas, where the DFT tries to find periodicities over the whole signal.
Every one of these transforms has the same basic "trick". It turns out you can represent a function "f" as weighted sum of a bunch of other functions "e_n". That is, by adding (the right) bunch of other functions together, each scaled by a number "a_n"
so f = sum_n a_n*e_n
It's not at all obvious you can find any set of "e_n" so that this works, but it turns out you can. Not only that, but there are many ways to do it!
It turns out the set of functions has some very particular properties - without details, scaled sin & cos work (in complex variable, you get the FT), but so do step functions (Haar basis) and weirder functions (Wavelets), as well as many others if you relax some constraints (Frame theory, things don't have to be a basis any more. This is useful but has consequences like energy may not be conserved). Calculating "a_n" scalars takes a little of the details too, but is straightforward in practice.
The discretization of many of these things is quite useful in practice, but they all have continous variable equivalents. The DCT is basically a "trick" too, use twice as many samples as the DFT, but use only the real part (no complex numbers).
If you forget the complex exponential part of the fourier transform (of which cosine is the real part) and just present it as
F(x) = ∫f(x)g(x)dx
for some arbitrary g, then the short time fourier transform is
F(x, t) = ∫f(x)w(x - t)g(x)dx.
So the mental model is your windowing the function you're taking the transform of. Remember that's just multiplication, so if w(x) is 0 outside of some interval, then so is f(x)w(x), and you use t to slide the window around.
But multiplication is associative, so you could easily think of it as windowing g(x) instead! Windowing the complex exponential gives you a wavelet. Rather than leaving it there, wavelet transforms add a scaling factor as well, giving
F(x, t, s) = ∫f(x)g((x - t)/s)dx
where g is now some 'mother wavelet'. Which could be the complex exponential, windowed or otherwise. If you remember that the complex exponential maps R onto the complex unit circle, with period 2pi, then increasing s increases the period (with respect to x), allowing for larger frequencies, and decreasing s gives you more detail in the frequencies you can see.
So, you'd want a wavelet that lowpasses the signal to avoid aliasing (which you can do by windowing!); and by the nyquist theorem in the discrete case you then need less samples to represent it fully. Taking that idea forward leads you to the whole filterbank thing you see all the time
I think the key thing is that wavelets aren't transforms of one variable, in the discrete case indices, but of three; index, time (location) and scale.
As a broad simplification, the cosine transforms use sinusoids, and wavelets tend to use square waves (or other funny shaped waves that is not a sinusoid)....
This is a clickbait title. It doesn't offer any evidence that Homer Simpson's face originated with the Fourier Transform, merely that you can recreate it with "circles." Seems the title ought to be changed.
The original title was "The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face". I believe that it better represents the actual content than your version ("The Fourier transform, a widely applicable mathematical discovery").
There is nothing "clickbait-y" about the author/editor's chosen title, unless this derisive label has become to mean any title that is not entirely devoid of humour, metaphors, or imagination. Trying, and succeeding, to generate interest isn't evil. Otherwise, please rename "hacker news" to "social content discovery platform for mostly white American males aged 18 to 40 employed in IT"(.ycombinator.com).
The original title is better suited to communicate the style and substance of the article. Reading it, it is immediately obvious that is an attempt at a pop-science treatment of Fourier trans. That is exactly what you get, the minor nitpick about the Simpsons being dragged into it somewhat arbitrarily nonwithstanding.
I'd add that the title of an article is as much part of the creation as the article itself. Of course, everyone has every legal right to use whatever words they want when linking to it. But, considering that titles are artistic expressions, I believe it would be appropriate to consider–at least in marginal cases–to respect the original work and its creator. To that effect, it may be worthwhile exploring ways to indicate when a title is not the original, or to maybe always keep original titles, but, where necessary, add add a subtitle with the 10-word summary people seem to be craving.
HN's policy on titles has been in place for many years (https://news.ycombinator.com/newsguidelines.html) and is specifically organized around what you call 'respect for the original work and its creator'. If there's any place on the internet more organized around such respect, I'd like to know. In my mind we're a tiny outpost that actually cares about this and that's a big reason why readers come here.
At the same time (as you'll also see if you read the site guidelines), we ask users to change titles that are misleading or linkbait. This is obviously necessary for any site that aspires to intellectual substance, though of course people often disagree about particular cases and that's fine.
Article authors typically don't write headlines so I don't see this as a creativity issue. Web publications are notorious for making baity headlines—that's the headline's job from their point of view. "The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face" is an obvious case of this, which is why so many HN readers protested. But a moderator found a better title than the one I changed it to.
When we change a title to something less misleading or baity, we try to use a representative phrase from the article itself, so in many cases the HN title ends up being more in line with the author's intention, not less.
I must push back against your dig at the HN community. It's both weirdly out of place—what do race, age, gender and nation have to do with article titles?—and insulting to the great many members who don't fit your description, who are every bit as welcome here as those who do.
My "alternative name" for HN was in no way meant as a criticism of the community. I was just trying to demonstrate that the name "Hacker news" itself is designed to be more attractive than an anodyne description would be: "Hacker" being a term that conjures a certain image. I tried to contrast it with the most boring just-the-facts description I could think of, and no criticism of either the community nor you and the other moderator(s?) was implied in that characterisation.
You know, I'm sort of split on what to think of the click-bait-y article title.
The guy's a PhD at Princeton, he clearly knows the Fourier Transform is more than just a trick - he even mentions that he wants to bring science/math to a wider audience at the end. From what I can tell, this article's more aimed at the nerdy middle/high schooler who likes math than engineers and computer scientists (the main target audience of this site). So while the article's title sort of tricks you into learning about this "trick", as long as people who normally can't be bothered to look at math (because for some reason it's popular to be "bad at math", ie not want to do math) are learning about the applications of mathematics in the real world, I don't see anything particularly wrong with trying to reach a wider audience.
... and I wish people would stop this witch hunt for "clickbait". It seems any headline that includes trace amounts of creativity, imagination, or suspense is seen as illegitimate, usually with an allusion to some mythical past where every book was apparently called "It was the Gardener: A Murder-Mystery".
But I kind of feel like it might give the wrong impression that these things are "tricks" (whatever that even means). I do agree with you though, the guy probably knows what he's talking about.
Yes, I was a bit surprised at the way the title hinted that this was a new 'trick' thing, when I have been familiar with Fast Fourier Transforms since forever when it comes to audio processing and reverb convolution etc., but then I realised that this is domain specific knowledge that is entirely due to me working in this capacity for so long. To someone in another industry or engineering capacity, FFTs may be an unknown entity, and indeed be an 'interesting discovery'.
I think "trick" here was referring to what is sometimes called "Fourier's trick" for getting the Fourier coefficients, than calling Fourier analysis itself a trick.
