8 ms·
An interactive guide to the Fourier transform (2012)
- alberto_ol 3y agoprevious submission with 79 comments https://news.ycombinator.com/item?id=27229836 https://news.ycombinator.com/item?id=27229836
- dang 3y agoThanks! Macroexpanded: An Interactive Guide to the Fourier Transform (2012) - https://news.ycombinator.com/item?id=27229836 https://news.ycombinator.com/item?id=27229836 - May 2021 (79 comments) An Interactive Guide to the Fourier Transform - https://news.ycombinator.com/item?id=10635075 https://news.ycombinator.com/item?id=10635075 - Nov 2015 (18 comments) An Interactive Guide To The Fourier Transform - https://news.ycombinator.com/item?id=4948082 https://news.ycombinator.com/item?id=4948082 - Dec 2012 (25 comments)
- moritonal 3y agoReading this I realise Bartosz Ciechanowski's work has ruined my definition of "interactive" for blogs.
- deleted 3y ago[deleted]
- nimishk 3y agoExactly what I was thinking!
- Isamu 3y agoAdding epicycles to the circular orbits - an example before Fourier! https://en.m.wikipedia.org/wiki/Deferent_and_epicycle https://en.m.wikipedia.org/wiki/Deferent_and_epicycle
- earlymodernlvr 3y agoRequest for someone to make an intuitive explanation of why the Fourier Transform is (almost) it's own inverse. I know the math proof from taking analysis, but the formula is too pretty and symmetrical for the explanation to be so technical. Same for why it preserves L2 norm.
- duped 3y agoSame answer for both. It's an orthogonal transform, aka a change of basis. You're conceptually rotating the function/series to an equivalent one that's orthogonal to the original. The magnitude/energy hasn't changed (Parseval's theorem is a more succinct definition). And to perform the inverse transform you need to conceptually rotate it back to the original, which should mirror the original transform very nicely. If it didn't preserve energy then there wouldn't necessarily be an inverse transform, since that implies information was lost.
- earlymodernlvr 3y agoI really appreciate this reply, since this is something I've always been curious about. If you have time, I would really appreciate it if you could elaborate on this point (maybe with some equations), but you've already given me a ton to think about, thank you! Also, is the new basis orthogonal to the original, or just another orthonormal basis? I don't see why it would be orthogonal to the original.
- ndriscoll 3y agoIt's an orthonormal basis. See my comment here[0] for more on why the forward and inverse transforms look similar (I've written e_w to mean e^iwt, but we want to think of it as a vector). The forward direction is doing a dot product with an exponential with a specific frequency to get the transform at that frequency (i.e. the function's projection/component at that frequency), which is a sum over the entire time basis. The inverse transform sums over all components/projections of the function at each frequency to rebuild the function. This is how you do an expansion in terms of orthogonal projections in any dimension. This also explains why the forward transform has a minus and the inverse doesn't: a complex dot product sums over complexConjugate(v_i)*w_i, while the inverse/reconstruction just sums over the basis exponentials scaled by the Fourier coefficient for that frequency. You can also prove that the sum over all imaginary exponentials is Dirac delta[1], so you could think of the inverse transform as being a dot product with delta to get the function at a specific time, and that dot product is a sum over the frequency basis. [0] https://news.ycombinator.com/item?id=38658312 https://news.ycombinator.com/item?id=38658312 [1] https://math.stackexchange.com/questions/1343859/why-does-integrating-a-complex-exponential-give-the-delta-function https://math.stackexchange.com/questions/1343859/why-does-in...
- chasil 3y agoIt would also be nice to have an understanding of its relation to the Laplace transform, something more than saying that the real component goes to zero.
- segfaultbuserr 3y ago+1. Pop-sci explanations of the frequency domain and Fourier transform are too many already, but does anyone know if there's a similar physical interpretation or visualization of the Laplace transform and the S domain?
- deleted 3y ago[deleted]
- sheepshear 3y agoMaybe this? https://youtu.be/iP4fckfDNK8 https://youtu.be/iP4fckfDNK8 It shows how the FT is a 2D slice of the 3D LT in the s-domain.
- sorenjan 3y agoThe short explanation of the DFT that I like the most is that it projects the signal vector on to the vector room with the exponential functions as basis vectors. Then you can see how much of the signal that each basis vector, corresponding to a frequency, can explain. It's intuitive to see if you start with a 2D vector space (the regular euclidian plane) and a 2D vector, and then you can expand the definition of vector spaces to include orthogonal functions as bases.
- sampo 3y ago> vector room Is Swedish, "rum" means both space, and a room. In English, "vector space" is used.
- amelius 3y agoMinor point, it's not a projection because you don't lose dimensions.
- nh23423fefe 3y agonit: the identity matrix is a projection P^2 = P is the definition. not losing dimensions
- amelius 3y agoTrue, but missing the point as you would not normally refer to the identity matrix as a projection.
- nh23423fefe 3y agoWhat was your point? An incorrect characterization of projections?
- mrfox321 3y agoNit to your nit, which is incorrect w.r.t. parent reply: A Fourier transform is not a projection, it's a change of basis represented by a unitary transformation.
- kkapelon 3y agoIt is super to easy to find resources on HOW the FT works. But I find it very difficult to find resources on WHY we need it and WHERE it is useful to have. Does anybody have some good sources that explain the practical applications and how it is useful on real world usage?
- CaptainFever 3y agoFrom TFA: Stop. Here's where most tutorials excitedly throw engineering applications at your face. Don't get scared; think of the examples as "Wow, we're finally seeing the source code (DNA) behind previously confusing ideas". If earthquake vibrations can be separated into "ingredients" (vibrations of different speeds & amplitudes), buildings can be designed to avoid interacting with the strongest ones. If sound waves can be separated into ingredients (bass and treble frequencies), we can boost the parts we care about, and hide the ones we don't. The crackle of random noise can be removed. Maybe similar "sound recipes" can be compared (music recognition services compare recipes, not the raw audio clips). If computer data can be represented with oscillating patterns, perhaps the least-important ones can be ignored. This "lossy compression" can drastically shrink file sizes (and why JPEG and MP3 files are much smaller than raw .bmp or .wav files). If a radio wave is our signal, we can use filters to listen to a particular channel. In the smoothie world, imagine each person paid attention to a different ingredient: Adam looks for apples, Bob looks for bananas, and Charlie gets cauliflower (sorry bud). The Fourier Transform is useful in engineering, sure, but it's a metaphor about finding the root causes behind an observed effect.
- kkapelon 3y agoYes I saw that. But it still hides the "meaty" part. Where are the articles that explain those processes? For example I would love to find an article that starts with "let's make a wav file smaller". And then somewhere in the middle it just says "and here we will use FT to achieve X".
- rescbr 3y agoIt's not an article, but I found The Scientist and Engineer's Guide to Digital Signal Processing book to be very comprehensive. There are a couple of chapters on applications, but not much code. http://www.dspguide.com/pdfbook.htm http://www.dspguide.com/pdfbook.htm
- ndngmfksk 3y agoThis article incorrectly labels the DFT as as a Fourier transform. To people who use these tools, the distinction is important and misnomers like this will make learning harder for people starting out. The article should be updated to correct this error.
- sizzzzlerz 3y agoJust a nit. The pair of equations the author showed at the beginning of the article are not the equations of the Fourier Transform and its inverse. The Transform is a continuous function operating on an infinite input. The equation for the Transform involves the use of the integral taken over +/- infinity. What is shown, using the summation operator, is a discrete form on the Transform where the input is a limited time series. A good alternative explanation can be found on Grant Sanderson's 3 Blue 1 Brown channel https://youtu.be/spUNpyF58BY?si=uqq2OOSATYcWmaG8 https://youtu.be/spUNpyF58BY?si=uqq2OOSATYcWmaG8
- keithalewis 3y agoFourier transform can be defined for any locally compact abelian group. Integers modulo n is one such.
- penguin_booze 3y agoGiven that monads are monoids in the category of endofunctors, I'm perfectly fine with it.
- keithalewis 3y agoThere is no Royal Road to mathematics. There is also no shortage of people convincing themselves they understand some particular aspect of it by watching a YouTube video. It is rare when a mathematician, or anyone, can write a book on a topic that no other expert in the field can top. Walter Rudin did that with Fourier analysis.
- ndriscoll 3y agoYou actually don't need abelian. e.g. the group of 1d affine transformations T(a,b)(x) = ax+b gives a variation of a wavelet transform. But you no longer have 1-D irreducible representations, so your Fourier coefficients become operators instead of numbers or something like that.
- keithalewis 3y ago
- white_beach 3y agohere's another recent book https://github.com/vadim-za/math-intuition-book https://github.com/vadim-za/math-intuition-book
- kuharich 3y agoPast comments: https://news.ycombinator.com/item?id=4948082 https://news.ycombinator.com/item?id=4948082, https://news.ycombinator.com/item?id=10635075 https://news.ycombinator.com/item?id=10635075
- evereverever 3y agoThere was an old macintosh application that had an interactive FFT. I remember seeing it at the Haus Der Musik in Vienna and have always looked for it.
- kaleidawave 3y agoJust seen this, was playing with complex Fourier series yesterday. Here < 100 LOC of python that calculates the coefficients and draws the circle animation https://gist.github.com/kaleidawave/bdaf8649e7917152b6cdd624636344f9 https://gist.github.com/kaleidawave/bdaf8649e7917152b6cdd624... Mind blowing that there might be a solar system out there with a collection of orbiting objects whose final object could have square orbit
- jameshart 3y agoI don’t like the casting of the frequency domain view as the ‘recipe’ and the time domain view as the ‘product’. The point of Fourier is that you can switch between these perspectives losslessly - they contain equivalent information. The ‘smoothie’ metaphor of ‘unmixing’ the smoothie to get the ingredients, and then blending it to get the smoothie back conjures the impression that Fourier transformation is some sort of entropy reversing process, which is misleading. A time domain function has a frequency domain interpretation - that doesn’t mean the frequency domain function is what ‘made’ the time domain function. It’s a chicken and an egg - both make each other. Just like a function has a derivative, and you can recover the original function (modulo it’s y-offset) by taking its antiderivative - that doesn’t make the derivative the ‘recipe’ for the function.
- diracs_stache 3y agoAgreed, in image processing the time-domain representation doesn't always carry significance when spatial extent is pertinent
- throwaway3091 3y ago[dead]
- nextaccountic 3y agothe best analogy is a basis change in a vector space: you can have the same data (the same vector) viewed in different ways if you look at it using different a base. for example, in physics, the numerical value of the coordinates of an object change in different frames of reference and this is not just an analogy: in the vector space of functions the fourier transform is indeed a basis change (to be more precise, a rotation). and from this arises the fractional fourier transform, which is a halfway change: if the fourier transform is a 180 degrees rotation, a fractional transform is something in between https://en.m.wikipedia.org/wiki/Fractional_Fourier_transform https://en.m.wikipedia.org/wiki/Fractional_Fourier_transform and this also explains why the fourier transform is the inverse of itself: two 180 degrees rotations gets you to the same place you were before
- 3y ago
- gnarlouse 3y agohttps://youtu.be/spUNpyF58BY?si=dM8J8Df5U7DTV9ls https://youtu.be/spUNpyF58BY?si=dM8J8Df5U7DTV9ls This is the definitive, the last Fourier transform guide you’ll ever need. It’s so intuitive and simple to understand. I watched this video *once* six years ago, and I can still rebuild the Fourier formula from memory. If only this had been around during my digital signal processing coursework in undergrad.
- jameshart 3y ago3b1b’s video is excellent, agreed. But I also want to give a shout out to this video: https://youtu.be/ToMyB5Hk06w?si=yJLDbb82JireH4Q9 https://youtu.be/ToMyB5Hk06w?si=yJLDbb82JireH4Q9 It does a really solid job of building the intuition for the way the underlying mathematical machinery works, using ‘inner products’ as its mode of thinking rather than complex analysis - I think it’s a great complement to Grant Sanderson’s explanation and for some people I think it’s probably more useful.
- euroderf 3y ago> If only this had been around during my digital signal processing coursework in undergrad. I hear that. At my school the course in Fourier Series & Boundary Value Problems was better known to students as "Mystery Math". This because there was typically a single moment of enlightenment.. where suddenly... the entire content of the course became pud. If this moment of mathematical satori came before the final exam, you were in luck.
- 2muchcoffeeman 3y agoI find all these Fourier explanations bad. The basic idea is very simple: Fourier takes a function, and converts it into the reciprocal domain. So if your X axis is time, t. Then Fourier gives you 1/t. What’s 1/t if t was some unit time? Frequency. If you want a nice intuitive example of this, (hand waving begins) a lens will give you a Fourier transform on its back focal plane if all the light coming in are parallel. Don’t quote me on that I need to double check the precise conditions. But you can send laser light through an image printed on transparency and manually apply filters to clean up small artefacts.
- meindnoch 3y ago4F Optical Correlator: https://youtu.be/wcRB3TWIAXE https://youtu.be/wcRB3TWIAXE A simple optical computer.
- 2muchcoffeeman 3y agoYep. It’s a great experiment because you can have spatial frequency as well which gives you a physical demonstration of a Fourier transform. Then you can do things like create physical filters and reform the original image to see if your filter worked.
- dr_dshiv 3y agoOne of the guys he thanks is Steve Lehar, who is a hero of mine. Steve had incredible intuitions about Harmony and Resonance and was crushed down by normies in psychology. But, indeed, the world is made of waves and resonance/harmony does govern pretty much everything! He says it better than me: https://scholar.google.com/citations?user=UmJanU0AAAAJ&hl=en https://scholar.google.com/citations?user=UmJanU0AAAAJ&hl=en