12 ms·
Fourier transform – A math tool used in optics, MP3s, JPEGs and more (2013)
- brian-armstrong 10y agoThis 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.
- labster 10y agoD'oh!
- dang 10y agoOk, we changed the title to a representative phrase from the article. We also added the article's year.
- matt4077 10y agoHey dang! I'd like to lodge a protest :) 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.
- deleted 10y ago[deleted]
- dang 10y agoHN's policy on titles has been in place for many years (https://news.ycombinator.com/newsguidelines.html 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.
- matt4077 10y agoThanks for your answer! 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.
- 10y ago
- adamnemecek 10y ago"Math trick", really?
- TheApexTheater 10y agoYou 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.
- cyberferret 10y agoYes, 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'.
- adamnemecek 10y agoBut 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.
- matt4077 10y agotrick |trɪk| noun • a clever or particular way of doing something: the trick is to put one ski forward and kneel. Synonyms: [tricks]: art, skills, techniques; secrets, shortcuts. ... 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".
- jim-jim-jim 10y agoAn 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.
- khedoros1 10y agoA 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).
- deleted 10y ago[deleted]
- onirom 10y agoAdding 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) https://www.youtube.com/watch?v=jBg3DnElfHk https://www.youtube.com/watch?v=jBg3DnElfHk
- SilverSlash 10y agoIt'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)?
- panic 10y agoThere's this article https://jackschaedler.github.io/circles-sines-signals/ https://jackschaedler.github.io/circles-sines-signals/ which is accompanied by some really neat interactive visuals.
- Davertron 10y agoI 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.
- CapacitorSet 10y agoI 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.
- msds 10y agoWhat 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. For starters, I'd recommend the course notes to Stanford's EE261 (https://see.stanford.edu/materials/lsoftaee261/book-fall-07.pdf https://see.stanford.edu/materials/lsoftaee261/book-fall-07....) - well written, very funny, a nice level of rigour, etc...
- Rainymood 10y agoAccording 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.
- brian-armstrong 10y agoMy biggest complaint with it was honestly just the title. It's cool to hear about another person seeing the utility in FT. Now go stare at a graphic equalizer on your music player :D
- lutusp 10y agoThe 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.
- jonahx 10y agoRelated friendly intro material: Nice intro from betterexplained: https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/ https://betterexplained.com/articles/an-interactive-guide-to... Previous HN Post "The Fourier Transform, explained in one sentence": https://news.ycombinator.com/item?id=8505410 https://news.ycombinator.com/item?id=8505410 Yet another HN Post: https://news.ycombinator.com/item?id=9762022 https://news.ycombinator.com/item?id=9762022
- thesmok 10y agoThis article on Electric Druid is the one that finally explained FT to me http://electricdruid.net/fourier-analysis-for-non-mathematicians/ http://electricdruid.net/fourier-analysis-for-non-mathematic...
- libeclipse 10y agoGod damn, that's beautiful...
- diger44 10y agoIf you want to see how the Fourier series work with sound and oscillators, I made a cool interactive visualization here: http://bgrawi.com/Fourier-Visualizations/ http://bgrawi.com/Fourier-Visualizations/
- johndough 10y agoMinor 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?
- gregschlom 10y agoVery nice visualization, thanks for sharing!
- Raknarg 10y agoHuh. 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)?
- d--b 10y agoFourier 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.
- kuharich 10y agoPrior discussion: https://news.ycombinator.com/item?id=6683866 https://news.ycombinator.com/item?id=6683866
- known 10y agoYou missed Hedge funds
- sangpo_pepys 10y agoan 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! https://pdfs.semanticscholar.org/1790/fe007bc1ab161a1ea814748b42e3acbdc958.pdf https://pdfs.semanticscholar.org/1790/fe007bc1ab161a1ea81474...
- Myrmornis 10y ago> 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?
- galeos 10y agoI 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.
- mrkgnao 10y agohttps://acko.net/files/gltalks/toolsforthought/#0 https://acko.net/files/gltalks/toolsforthought/#0
- tambourine_man 10y agoCan anyone explain like I'm five: wavelets vs discreet cosine transforms? I can roughtly understand the latter, but the former remains a mistery.
- deleted 10y ago[deleted]
- cillian64 10y agoAll 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.
- xchip 10y agoAs 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)....
- gp7 10y agoIf 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.
- xchip 10y agoHere 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) https://htmlpreview.github.io/?https://github.com/aguaviva/GuitarTuner/blob/master/GuitarTuner.html https://htmlpreview.github.io/?https://github.com/aguaviva/G... It also works with guitars, in fact each string played openly should match each of the vertical lines. This is how I tune my guitar. There is more to it, but still it is a great start :)
- regularfry 10y agoFor extra credit, use the exact same filter as part of the sound generator.
- throwawayNewc 10y agohint: white noise
- thearn4 10y agoFFT and the convolution theorem are some of my favorite tricks in math. A toy I made a few years back: https://github.com/thearn/game-of-life https://github.com/thearn/game-of-life
- kmm 10y agoFourier 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
- ptero 10y agoThis 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.
- reitanqild 10y agoAbove may sound harsh, which was not my intent; I belive you and the word harsh wouldn't even have crossed my mind if you hadn't mentioned it.
- catnaroek 10y ago> Why are [sine waves] better than, say, step functions (...) 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).
- alok-g 10y agoWon't the same apply to square waves also, i.e., they can also form an orthonormal basis?
- sdenton4 10y agoTotally 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...
- sizzzzlerz 10y agoI'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.
- leecarraher 10y agodang doesn't mention my two favorite uses large integer multiplication -> addition convolution -> multiplication
- tzs 10y agoThere'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]). [1] https://www.amazon.com/Who-Fourier-Mathematical-Adventure-2nd/dp/0964350432 https://www.amazon.com/Who-Fourier-Mathematical-Adventure-2n... [2] https://en.wikipedia.org/wiki/Hippo_Family_Club#Transnational_College_of_LEX https://en.wikipedia.org/wiki/Hippo_Family_Club#Transnationa... [3] https://www.amazon.com/What-Quantum-Mechanics-Physics-Adventure/dp/0964350440 https://www.amazon.com/What-Quantum-Mechanics-Physics-Advent... [4] https://www.amazon.com/What-Biology-Adventure-Transnational-College/dp/0964350424 https://www.amazon.com/What-Biology-Adventure-Transnational-...
- calebm 10y ago"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).
- calebm 10y agoHere are some of my notes on the Fourier Transform (and using it for sound analysis): http://calebmadrigal.com/fourier-transform-notes/ http://calebmadrigal.com/fourier-transform-notes/
- mcguire 10y agoThere's also The Scientist and Engineers' Guide to Digital Signal Processing: http://www.dspguide.com/ http://www.dspguide.com/
- acobster 10y agoDecompose complex signals into their constituent sinusoids with this one weird trick