11 ms·

An Interactive Guide to the Fourier Transform (2012)

301 points by parsecs 5y ago

sillysaurusx 5y ago
I've been thinking a lot about how to apply FFTs to neural networks, so this is timely; thank you. If you're looking for deeper explanations, I recommend "Practical Signal Processing": https://www.amazon.com/Practical-Signal-Processing-Mark-Owen/dp/1107411823 https://www.amazon.com/Practical-Signal-Processing-Mark-Owen... Many of the chapters are here: https://battle.shawwn.com/sdb/books/PSP/ https://battle.shawwn.com/sdb/books/PSP/ but buy the book if you can afford to. In particular, Chapter 4's "untwisting" intuition is the best I've found: https://imgur.com/a/r7KvO60 https://imgur.com/a/r7KvO60 Another way of phrasing it: You know that effect when a wheel is spinning so fast, it looks like it's going backwards? If it looks like it's standing still, there's a Fourier coefficient at that rotational frequency. ... Or at least, I think there is. It's hard to be precise with analogies.
- tracyhenry 5y ago
  Google's FNet seems to apply FT to NNs? https://arxiv.org/abs/2105.03824 https://arxiv.org/abs/2105.03824
  - sillysaurusx 5y ago
    That paper was one of the most misleading papers I've ever seen in NNs. https://twitter.com/theshawwn/status/1393315603973386240 https://twitter.com/theshawwn/status/1393315603973386240 Like many others, I was hyped when it came out. Then it turns out that BERT with half the param count still kicks their butts in accuracy. They also only model the .real component and ignore the .imaginary component entirely, which you can't do and expect good results. But, FFTs are so cool and under-explored that I'm sure they'll be making the rounds in NNs soon. There are lots of advantages to frequency space representations.
    - kortex 5y ago
      I don't understand why the first operations of a CNN are FFT-based decomposition into spatial wavelets. This is basically all the first layers are doing anyways. In fact the filters usually learn both an edge and a centroid at a given orientation. You can get both at the same time with complex wavelets.
- obastani 5y ago
  There has been some interesting recent work [1] applying Fourier transforms (more precisely, an adaptation of the Fourier transform to the sphere) to CNNs, to automatically encode equivariance to rotational symmetries. [1] https://arxiv.org/abs/1711.06721 https://arxiv.org/abs/1711.06721
- mhh__ 5y ago
  Proakis's book is quite good if you want to really nail down the fundamentals of the mathematics, but it's completely detached from applications and intuition despite what the cover (I suspect this is because the author has a different book on communication theory) says, so I'm not a huge fan of it.
- 37ef_ced3 5y ago
  For neural nets, https://NN-512.com https://NN-512.com generates stand-alone C code vectorized Fourier convolutions that are 2x2 spatially strided (with a big 16x16 tile) This is great for large filter, 2x2 strided neural net convolutions (e.g., 7x7 stride 2x2) There's none of the waste you find elsewhere, in implementations that downsubsample the output of a dense (unstrided) Fourier convolution. I haven't seen this technique used anywhere else!
TeeMassive 5y ago
The most intuitive explanation I've seen, although a bit abstract, is that Fourier transforms, and the other Fourier-like transforms including the s and z transforms, are just about changing the system of coordinates of the data vector using the transform's generative vectors. Indeed we can easily see that the definition of all those transforms take the form of the sum of a scalar product that computes the projection of the data vector unto the kth dimension in the transformation (e.g. frequency) space.
- alanbernstein 5y ago
  This is the interpretation that leads you to imagine what a fractional Fourier transform might be: a rotation other than 90 degrees in the vector space you described. Interesting, if esoteric.
  - kortex 5y ago
    For those who may not have heard of it: https://en.m.wikipedia.org/wiki/Linear_canonical_transformation https://en.m.wikipedia.org/wiki/Linear_canonical_transformat... Neatly generalizes and ties together all of your favorite integral transforms and has weird connections to virtually every branch of mathematics.
  - BlueTemplar 5y ago
    I was wondering recently whether some kind of 45° rotation transform could be used to represent equally well both "sides" of Heisenberg's unsharpness principle ?
jmchuster 5y ago
i'd assume 3b1b would have an intuitive video about it as well
- kentor 5y ago
  The 3b1b video was mind blowing. Link: https://www.youtube.com/watch?v=spUNpyF58BY https://www.youtube.com/watch?v=spUNpyF58BY
  - travisgriggs 5y ago
    Agreed! Came here to post it. First time I really "got" what an FFT was about.
dang 5y ago
Some past threads: 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) These are similar: An Interactive Introduction to Fourier Transforms - https://news.ycombinator.com/item?id=25095724 https://news.ycombinator.com/item?id=25095724 - Nov 2020 (52 comments) An Interactive Introduction to Fourier Transforms - https://news.ycombinator.com/item?id=20934347 https://news.ycombinator.com/item?id=20934347 - Sept 2019 (44 comments) An Interactive Introduction to Fourier Transforms - https://news.ycombinator.com/item?id=18879957 https://news.ycombinator.com/item?id=18879957 - Jan 2019 (22 comments) An animated introduction to the Fourier Transform [video] - https://news.ycombinator.com/item?id=16242103 https://news.ycombinator.com/item?id=16242103 - Jan 2018 (31 comments) Ask HN: Where can I learn about fourier transformations? - https://news.ycombinator.com/item?id=15819069 https://news.ycombinator.com/item?id=15819069 - Nov 2017 (8 comments) Fourier transform – A math tool used in optics, MP3s, JPEGs and more (2013) - https://news.ycombinator.com/item?id=14084526 https://news.ycombinator.com/item?id=14084526 - April 2017 (83 comments) The Fourier Transform and its Applications - https://news.ycombinator.com/item?id=12476692 https://news.ycombinator.com/item?id=12476692 - Sept 2016 (55 comments) The Medieval Fourier Transform - https://news.ycombinator.com/item?id=10531790 https://news.ycombinator.com/item?id=10531790 - Nov 2015 (15 comments) The Fourier Transform, explained in one sentence - https://news.ycombinator.com/item?id=8505410 https://news.ycombinator.com/item?id=8505410 - Oct 2014 (82 comments) The Fourier Transform and its Applications - https://news.ycombinator.com/item?id=7789767 https://news.ycombinator.com/item?id=7789767 - May 2014 (22 comments) Fourier transform for dummies - https://news.ycombinator.com/item?id=7468193 https://news.ycombinator.com/item?id=7468193 - March 2014 (37 comments) Understanding the Fourier transform (2011) - https://news.ycombinator.com/item?id=6686456 https://news.ycombinator.com/item?id=6686456 - Nov 2013 (6 comments) Understanding The Fourier Transform - https://news.ycombinator.com/item?id=4861960 https://news.ycombinator.com/item?id=4861960 - Dec 2012 (44 comments) Intuitive explication of Fourier Transformation - https://news.ycombinator.com/item?id=2555562 https://news.ycombinator.com/item?id=2555562 - May 2011 (33 comments) Mastering The Fourier Transform in One Day - https://news.ycombinator.com/item?id=1360405 https://news.ycombinator.com/item?id=1360405 - May 2010 (11 comments) Mastering The Fourier Transform in One Day - https://news.ycombinator.com/item?id=698929 https://news.ycombinator.com/item?id=698929 - July 2009 (18 comments) An Intuitive Explanation of Fourier Theory - https://news.ycombinator.com/item?id=56844 https://news.ycombinator.com/item?id=56844 - Sept 2007 (11 comments)
itissid 5y ago
What about the 3 blue 1 brown video on it? I think that is pretty concise and intuitive too but does not seem to appear on this thread https://www.youtube.com/watch?v=spUNpyF58BY&ab_channel=3Blue1Brown https://www.youtube.com/watch?v=spUNpyF58BY&ab_channel=3Blue...
- BlueTemplar 5y ago
  Haven't they "just" taken the above explanation, and made a video about it ?
Patient0 5y ago
The only way I have been able to understand it: - Functions can be thought of as vectors in an inner product space (https://www.youtube.com/watch?v=TgKwz5Ikpc8 https://www.youtube.com/watch?v=TgKwz5Ikpc8) - the "inner product" operation (integral of the product of the two functions): imagine what would happen as you approximate functions as discrete vector with a very high number of dimensions/co-ordinates and computed the dot-product between those two vectors, but scale the result to be invariant of how many dimensions you used to approximate it => you get the integral formula - Now, it's just normal linear algebra: - The "length" of one of these vectors can now be thought of as the square root of the inner product of the function with itself - The "distance" between two functions can now be thought of by subtracting one function from the other, to get a new "vector/function", and compute its length - The cosine of the "angle" between two functions is the dot product between two functions scaled to have length 1 - The functions describing a sine or cosine wave are vectors which have a inner-product against themselves of 1, and a dot-product against any other frequencies of 0 - Thus the different frequency functions/vectors form an orthonormal basis - This means that you can find the co-ordinates of any function by taking the inner product of the function against each fourier basis function - The "co-ordinates" of your function w.r.t. the orthonormal basis can be computed by taking the inner product against each basis function/vector - This will be the point that minimizes the distance to your actual function - These "co-ordinates" are the fourier co-efficients for the fourier series representation of your function - For non-periodic functions, you can take the limit as your period goes to infinity, that gives you the fourier transform representation. Or, in short: 1. Functions can be thought of as vectors in an inner product space (https://www.youtube.com/watch?v=TgKwz5Ikpc8 https://www.youtube.com/watch?v=TgKwz5Ikpc8) 2. The Fourier series functions form an orthonormal set of basis vectors 3. Now just use normal linear algebra to work out the co-ordinates of your function w.r.t 2
- only_as_i_fall 5y ago
  So you got through 2 or 3 years of calculus at least a year of abstract algebra and probably 2 years of linear before you could understand what a Fourier transform was? Color me skeptical
  - 5y ago
etamponi 5y ago
From the beginning of the article: > The Fourier Transform is one of deepest insights ever made. Unfortunately, the meaning is buried within dense equations The post does a great job at explaining what the Fourier transform means, but I am always skeptical of sentences like this. It's a pattern found in many other posts too: "unfortunately" this concept is expressed in math form, let's try to solve this problem. I find that it's exactly the other way around. Math and math notation is dismissed too early and too easily even in engineering studies, resulting in shoddy and imprecise definitions and understandings. > The Fourier Transform is one of deepest insights ever made. Fortunately, the meaning is engraved in dense equations
- ath92 5y ago
  For most people, having only the equations means they cannot build an intuition for what a fourier transform actually is, because they don't have a solid enough grasp of math notation to easily make sense of what the dense equations actually represent. For those people it's very helpful to first get a sense of what it all means (even if it means that initial mental model is somewhat imprecise), because it makes understanding the equations easier.
  - xNeil 5y ago
    Surprisingly for me, it's the other way around! Equations build intuition in my case, although I'm not sure why.
    - thomasahle 5y ago
      My experience is that visuals help people _feel_ like they understand the concept, but the equations are necessary to get an _operational_ knowledge. It's all well and good to be able to talk about the "deepest human knowledge" at a dinner party, but it doesn't help you solve actual problems using the fourier transform.
      - kortex 5y ago
        My brain works the opposite. Equations give me something I can work with but feels like voodoo, and I only get operational knowledge once I can visualize it in some way.
geokon 5y ago
At the end of these types of popsci explanations you still can't grok the math any better and you end up with a hand-wave-y misleading understanding of what's going on. It starts off by saying that the Fourier Transform "measures every possible cycle". This is an wrong approach to thinking of the Fourier Transform. If you think in these terms you will quickly get lost. The Fourier basis is a set of sinusoids that are mutually orthogonal (ie. none can be represented as a combination of the others). They just happen to generally cover the frequency ranges you're interested in (though this depends on your problem). If you choose some random sinusoidal signal that isn't a harmonic of your sampling period, then the Fourier Transform gives you back a mess that's hard to interpret (how a off-harmonic sinusoid gets "smeared" across the basis is actually something I frankly still don't quite understand https://ccrma.stanford.edu/~jos/mdft/Frequencies_Cracks.html https://ccrma.stanford.edu/~jos/mdft/Frequencies_Cracks.html ) This is in contrast to the phase information that you get that is continuous. Each frequency has two associated basis vectors and they can give you any phase offset. The frequencies are only set harmonics, but the phase can be any value. This is the result of how the basis is setup. If anything, the phase information you get from the Fourier transform is more interesting than the frequency information you can glean. The "Circular Paths" visualization is also highly misleading. The complex plane is a crutch that gives you pretty pictures. It pretends to be like a 2D plane but it's actually fundamentally distinct from a Cartesian/"normal" X-Y plane b/c complex numbers can be multiplied while normal [x,y] pairs can not (b/c the operation is simply undefined - you can't multiply two points on a map). The product of two complex numbers is giving you another complex number.. but good luck visualizing where that point ends up! You'll notice all complex plane examples stay on the unit circle b/c you get a "rotation" but it's an edge case. The whole 2D analogy is setting you up to be very confused
- nspattak 5y ago
  Why is it wrong? I was not lost.
- BlueTemplar 5y ago
  All operations have to be defined, and learned first. That's like saying that you can't multiply two matrices... (Though it does annoy me when a symmetric symbol is used for non-commutative operations !) https://en.wikipedia.org/wiki/Complex_number#/media/File:Complex_multi.svg https://en.wikipedia.org/wiki/Complex_number#/media/File:Com... See also geometric/Clifford Algebra : http://www.av8n.com/physics/clifford-intro.htm http://www.av8n.com/physics/clifford-intro.htm (Though note that it does require TWO different "multiplication" operations to make sense !)
otabdeveloper4 5y ago
> Here's a plain-English metaphor: > What does the Fourier Transform do? Given a smoothie, it finds the recipe. > How? Run the smoothie through filters to extract each ingredient. > Why? Recipes are easier to analyze, compare, and modify than the smoothie itself. > How do we get the smoothie back? Blend the ingredients. This has to be the absolute worst attempt at an explanation ever. Even the "monads are a burrito" thing is better.
- kortex 5y ago
  Why? I totally understood it. Then again, I have a background in chemistry, HPLC-MS, NMR, AA, FTIR, so I'm used to the idea of "breaking a mixture into orthogonal components."
  - otabdeveloper4 5y ago
    Because "recipe for a smoothie" analogy is too broad and doesn't help you understand how the Fourier Transform is different from a Ruby script or a bill of materials for a chair. Not to mention that the idea of "given a smoothie, it finds the recipe" is impossible and makes no sense in the first place.
    - stocknoob 5y ago
      Tasting a drink and guessing its ingredients makes no sense?
      - otabdeveloper4 5y ago
        Except that absolutely not how the Fourier Transform works and gives a very false impression.
amitport 5y ago
I kind of wish he used tau instead of Hz here.
slowhand09 5y ago
Cool article.. For some application - see http://www.dspguide.com/pdfbook.htm http://www.dspguide.com/pdfbook.htm
aj7 5y ago
That’s the discrete Fourier transform. The difference is quite significant.
hansvm 5y ago
I see this particular mistake crop up a lot, and it's a bit pedantic, but I don't get the impression that it's being intentionally ignored for educational reasons: The author repeatedly describes "the" recipe, "the" set of frequencies, .... The standard Fourier transform is only unique conditioned on the fact that we've agreed on a particular set of basis functions ahead of time. It isn't even the only choice of orthogonal exponentials we could have picked. In terms of real applications that point often doesn't matter much -- especially in fields like lossy compression where you might not actually care much about any underlying meaning in the representation, and especially in fields like radio where your data is in some sense fundamentally represented as combinations of sinusoids -- but in general it isn't a sound leap to go from "this Fourier coefficient is big" to "there exists a big sinusoid that semantically matters to my data."
- whatshisface 5y ago
  Linear time-invariant physical processes are so common in the real world that it's not unreasonable to expect sinusoids to semantically matter... At least when the data pertains to physical systems.
  - hansvm 5y ago
    Certainly. It's super reasonable to think that they might matter and to investigate that approach; it's unreasonable to take as an axiom that they matter and use that as proof of other facts.
- joppy 5y ago
  If you add some additional structure of remembering that the domain of these transformations is an abelian group, then there is actually a completely canonical version of the Fourier transform, whose domain is the dual group - the only non-canonical part is picking labels for elements of the dual group, but there is no other choice of basis functions. (Wikipedia gets a little into this, you can find it under "Pontryagin duality" on the Fourier transform page, but it's not really enough of an explanation to learn from). Take the discrete Fourier transform for example, whose domain group is Z/nZ: the integers-mod-n for some fixed n. The basis functions for the transforms need to be group homomorphisms f: Z/nZ -> C, meaning that they need to satisfy f(a + b) = f(a) f(b) for all a, b. Without too much trouble you can work out that the only such functions are of the form f(k) = exp(2 pi i m k / n) for m = 0, ..., n - 1. So once the group structure is remembered, the choice of basis is forced. The only ambiguity is relabelling the basis elements back into Z/nZ, which is a (very useful) hack. The same reasoning (with more complicated working) applies to taking the Fourier series of a periodic function, or taking the Fourier transform of a continuous function on the real line. There is a canonical choice of basis, but some ambiguity in what labels to assign to those basis elements.
YZF 5y ago
Probably worth saying "Discrete Fourier Transform"...

301 points by parsecs 5y ago

I've been thinking a lot about how to apply FFTs to neural networks, so this is timely; thank you. If you're looking for deeper explanations, I recommend "Practical Signal Processing": https://www.amazon.com/Practical-Signal-Processing-Mark-Owen/dp/1107411823 https://www.amazon.com/Practical-Signal-Processing-Mark-Owen... Many of the chapters are here: https://battle.shawwn.com/sdb/books/PSP/ https://battle.shawwn.com/sdb/books/PSP/ but buy the book if you can afford to. In particular, Chapter 4's "untwisting" intuition is the best I've found: https://imgur.com/a/r7KvO60 https://imgur.com/a/r7KvO60 Another way of phrasing it: You know that effect when a wheel is spinning so fast, it looks like it's going backwards? If it looks like it's standing still, there's a Fourier coefficient at that rotational frequency. ... Or at least, I think there is. It's hard to be precise with analogies.

tracyhenry 5y ago
Google's FNet seems to apply FT to NNs? https://arxiv.org/abs/2105.03824 https://arxiv.org/abs/2105.03824
- sillysaurusx 5y ago
  That paper was one of the most misleading papers I've ever seen in NNs. https://twitter.com/theshawwn/status/1393315603973386240 https://twitter.com/theshawwn/status/1393315603973386240 Like many others, I was hyped when it came out. Then it turns out that BERT with half the param count still kicks their butts in accuracy. They also only model the .real component and ignore the .imaginary component entirely, which you can't do and expect good results. But, FFTs are so cool and under-explored that I'm sure they'll be making the rounds in NNs soon. There are lots of advantages to frequency space representations.
  - kortex 5y ago
    I don't understand why the first operations of a CNN are FFT-based decomposition into spatial wavelets. This is basically all the first layers are doing anyways. In fact the filters usually learn both an edge and a centroid at a given orientation. You can get both at the same time with complex wavelets.
obastani 5y ago
There has been some interesting recent work [1] applying Fourier transforms (more precisely, an adaptation of the Fourier transform to the sphere) to CNNs, to automatically encode equivariance to rotational symmetries. [1] https://arxiv.org/abs/1711.06721 https://arxiv.org/abs/1711.06721
mhh__ 5y ago
Proakis's book is quite good if you want to really nail down the fundamentals of the mathematics, but it's completely detached from applications and intuition despite what the cover (I suspect this is because the author has a different book on communication theory) says, so I'm not a huge fan of it.
37ef_ced3 5y ago
For neural nets, https://NN-512.com https://NN-512.com generates stand-alone C code vectorized Fourier convolutions that are 2x2 spatially strided (with a big 16x16 tile) This is great for large filter, 2x2 strided neural net convolutions (e.g., 7x7 stride 2x2) There's none of the waste you find elsewhere, in implementations that downsubsample the output of a dense (unstrided) Fourier convolution. I haven't seen this technique used anywhere else!

TeeMassive 5y ago

The most intuitive explanation I've seen, although a bit abstract, is that Fourier transforms, and the other Fourier-like transforms including the s and z transforms, are just about changing the system of coordinates of the data vector using the transform's generative vectors. Indeed we can easily see that the definition of all those transforms take the form of the sum of a scalar product that computes the projection of the data vector unto the kth dimension in the transformation (e.g. frequency) space.

alanbernstein 5y ago
This is the interpretation that leads you to imagine what a fractional Fourier transform might be: a rotation other than 90 degrees in the vector space you described. Interesting, if esoteric.
- kortex 5y ago
  For those who may not have heard of it: https://en.m.wikipedia.org/wiki/Linear_canonical_transformation https://en.m.wikipedia.org/wiki/Linear_canonical_transformat... Neatly generalizes and ties together all of your favorite integral transforms and has weird connections to virtually every branch of mathematics.
- BlueTemplar 5y ago
  I was wondering recently whether some kind of 45° rotation transform could be used to represent equally well both "sides" of Heisenberg's unsharpness principle ?

jmchuster 5y ago

i'd assume 3b1b would have an intuitive video about it as well

kentor 5y ago
The 3b1b video was mind blowing. Link: https://www.youtube.com/watch?v=spUNpyF58BY https://www.youtube.com/watch?v=spUNpyF58BY
- travisgriggs 5y ago
  Agreed! Came here to post it. First time I really "got" what an FFT was about.

dang 5y ago

Some past threads: 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) These are similar: An Interactive Introduction to Fourier Transforms - https://news.ycombinator.com/item?id=25095724 https://news.ycombinator.com/item?id=25095724 - Nov 2020 (52 comments) An Interactive Introduction to Fourier Transforms - https://news.ycombinator.com/item?id=20934347 https://news.ycombinator.com/item?id=20934347 - Sept 2019 (44 comments) An Interactive Introduction to Fourier Transforms - https://news.ycombinator.com/item?id=18879957 https://news.ycombinator.com/item?id=18879957 - Jan 2019 (22 comments) An animated introduction to the Fourier Transform [video] - https://news.ycombinator.com/item?id=16242103 https://news.ycombinator.com/item?id=16242103 - Jan 2018 (31 comments) Ask HN: Where can I learn about fourier transformations? - https://news.ycombinator.com/item?id=15819069 https://news.ycombinator.com/item?id=15819069 - Nov 2017 (8 comments) Fourier transform – A math tool used in optics, MP3s, JPEGs and more (2013) - https://news.ycombinator.com/item?id=14084526 https://news.ycombinator.com/item?id=14084526 - April 2017 (83 comments) The Fourier Transform and its Applications - https://news.ycombinator.com/item?id=12476692 https://news.ycombinator.com/item?id=12476692 - Sept 2016 (55 comments) The Medieval Fourier Transform - https://news.ycombinator.com/item?id=10531790 https://news.ycombinator.com/item?id=10531790 - Nov 2015 (15 comments) The Fourier Transform, explained in one sentence - https://news.ycombinator.com/item?id=8505410 https://news.ycombinator.com/item?id=8505410 - Oct 2014 (82 comments) The Fourier Transform and its Applications - https://news.ycombinator.com/item?id=7789767 https://news.ycombinator.com/item?id=7789767 - May 2014 (22 comments) Fourier transform for dummies - https://news.ycombinator.com/item?id=7468193 https://news.ycombinator.com/item?id=7468193 - March 2014 (37 comments) Understanding the Fourier transform (2011) - https://news.ycombinator.com/item?id=6686456 https://news.ycombinator.com/item?id=6686456 - Nov 2013 (6 comments) Understanding The Fourier Transform - https://news.ycombinator.com/item?id=4861960 https://news.ycombinator.com/item?id=4861960 - Dec 2012 (44 comments) Intuitive explication of Fourier Transformation - https://news.ycombinator.com/item?id=2555562 https://news.ycombinator.com/item?id=2555562 - May 2011 (33 comments) Mastering The Fourier Transform in One Day - https://news.ycombinator.com/item?id=1360405 https://news.ycombinator.com/item?id=1360405 - May 2010 (11 comments) Mastering The Fourier Transform in One Day - https://news.ycombinator.com/item?id=698929 https://news.ycombinator.com/item?id=698929 - July 2009 (18 comments) An Intuitive Explanation of Fourier Theory - https://news.ycombinator.com/item?id=56844 https://news.ycombinator.com/item?id=56844 - Sept 2007 (11 comments)

itissid 5y ago

What about the 3 blue 1 brown video on it? I think that is pretty concise and intuitive too but does not seem to appear on this thread https://www.youtube.com/watch?v=spUNpyF58BY&ab_channel=3Blue1Brown https://www.youtube.com/watch?v=spUNpyF58BY&ab_channel=3Blue...

BlueTemplar 5y ago
Haven't they "just" taken the above explanation, and made a video about it ?

Patient0 5y ago

The only way I have been able to understand it: - Functions can be thought of as vectors in an inner product space (https://www.youtube.com/watch?v=TgKwz5Ikpc8 https://www.youtube.com/watch?v=TgKwz5Ikpc8) - the "inner product" operation (integral of the product of the two functions): imagine what would happen as you approximate functions as discrete vector with a very high number of dimensions/co-ordinates and computed the dot-product between those two vectors, but scale the result to be invariant of how many dimensions you used to approximate it => you get the integral formula - Now, it's just normal linear algebra: - The "length" of one of these vectors can now be thought of as the square root of the inner product of the function with itself - The "distance" between two functions can now be thought of by subtracting one function from the other, to get a new "vector/function", and compute its length - The cosine of the "angle" between two functions is the dot product between two functions scaled to have length 1 - The functions describing a sine or cosine wave are vectors which have a inner-product against themselves of 1, and a dot-product against any other frequencies of 0 - Thus the different frequency functions/vectors form an orthonormal basis - This means that you can find the co-ordinates of any function by taking the inner product of the function against each fourier basis function - The "co-ordinates" of your function w.r.t. the orthonormal basis can be computed by taking the inner product against each basis function/vector - This will be the point that minimizes the distance to your actual function - These "co-ordinates" are the fourier co-efficients for the fourier series representation of your function - For non-periodic functions, you can take the limit as your period goes to infinity, that gives you the fourier transform representation. Or, in short: 1. Functions can be thought of as vectors in an inner product space (https://www.youtube.com/watch?v=TgKwz5Ikpc8 https://www.youtube.com/watch?v=TgKwz5Ikpc8) 2. The Fourier series functions form an orthonormal set of basis vectors 3. Now just use normal linear algebra to work out the co-ordinates of your function w.r.t 2

only_as_i_fall 5y ago
So you got through 2 or 3 years of calculus at least a year of abstract algebra and probably 2 years of linear before you could understand what a Fourier transform was? Color me skeptical
- 5y ago

etamponi 5y ago

From the beginning of the article: > The Fourier Transform is one of deepest insights ever made. Unfortunately, the meaning is buried within dense equations The post does a great job at explaining what the Fourier transform means, but I am always skeptical of sentences like this. It's a pattern found in many other posts too: "unfortunately" this concept is expressed in math form, let's try to solve this problem. I find that it's exactly the other way around. Math and math notation is dismissed too early and too easily even in engineering studies, resulting in shoddy and imprecise definitions and understandings. > The Fourier Transform is one of deepest insights ever made. Fortunately, the meaning is engraved in dense equations

ath92 5y ago
For most people, having only the equations means they cannot build an intuition for what a fourier transform actually is, because they don't have a solid enough grasp of math notation to easily make sense of what the dense equations actually represent. For those people it's very helpful to first get a sense of what it all means (even if it means that initial mental model is somewhat imprecise), because it makes understanding the equations easier.
- xNeil 5y ago
  Surprisingly for me, it's the other way around! Equations build intuition in my case, although I'm not sure why.
  - thomasahle 5y ago
    My experience is that visuals help people _feel_ like they understand the concept, but the equations are necessary to get an _operational_ knowledge. It's all well and good to be able to talk about the "deepest human knowledge" at a dinner party, but it doesn't help you solve actual problems using the fourier transform.
    - kortex 5y ago
      My brain works the opposite. Equations give me something I can work with but feels like voodoo, and I only get operational knowledge once I can visualize it in some way.

geokon 5y ago

At the end of these types of popsci explanations you still can't grok the math any better and you end up with a hand-wave-y misleading understanding of what's going on. It starts off by saying that the Fourier Transform "measures every possible cycle". This is an wrong approach to thinking of the Fourier Transform. If you think in these terms you will quickly get lost. The Fourier basis is a set of sinusoids that are mutually orthogonal (ie. none can be represented as a combination of the others). They just happen to generally cover the frequency ranges you're interested in (though this depends on your problem). If you choose some random sinusoidal signal that isn't a harmonic of your sampling period, then the Fourier Transform gives you back a mess that's hard to interpret (how a off-harmonic sinusoid gets "smeared" across the basis is actually something I frankly still don't quite understand https://ccrma.stanford.edu/~jos/mdft/Frequencies_Cracks.html https://ccrma.stanford.edu/~jos/mdft/Frequencies_Cracks.html ) This is in contrast to the phase information that you get that is continuous. Each frequency has two associated basis vectors and they can give you any phase offset. The frequencies are only set harmonics, but the phase can be any value. This is the result of how the basis is setup. If anything, the phase information you get from the Fourier transform is more interesting than the frequency information you can glean. The "Circular Paths" visualization is also highly misleading. The complex plane is a crutch that gives you pretty pictures. It pretends to be like a 2D plane but it's actually fundamentally distinct from a Cartesian/"normal" X-Y plane b/c complex numbers can be multiplied while normal [x,y] pairs can not (b/c the operation is simply undefined - you can't multiply two points on a map). The product of two complex numbers is giving you another complex number.. but good luck visualizing where that point ends up! You'll notice all complex plane examples stay on the unit circle b/c you get a "rotation" but it's an edge case. The whole 2D analogy is setting you up to be very confused

nspattak 5y ago
Why is it wrong? I was not lost.
BlueTemplar 5y ago
All operations have to be defined, and learned first. That's like saying that you can't multiply two matrices... (Though it does annoy me when a symmetric symbol is used for non-commutative operations !) https://en.wikipedia.org/wiki/Complex_number#/media/File:Complex_multi.svg https://en.wikipedia.org/wiki/Complex_number#/media/File:Com... See also geometric/Clifford Algebra : http://www.av8n.com/physics/clifford-intro.htm http://www.av8n.com/physics/clifford-intro.htm (Though note that it does require TWO different "multiplication" operations to make sense !)

otabdeveloper4 5y ago

> Here's a plain-English metaphor: > What does the Fourier Transform do? Given a smoothie, it finds the recipe. > How? Run the smoothie through filters to extract each ingredient. > Why? Recipes are easier to analyze, compare, and modify than the smoothie itself. > How do we get the smoothie back? Blend the ingredients. This has to be the absolute worst attempt at an explanation ever. Even the "monads are a burrito" thing is better.

kortex 5y ago
Why? I totally understood it. Then again, I have a background in chemistry, HPLC-MS, NMR, AA, FTIR, so I'm used to the idea of "breaking a mixture into orthogonal components."
- otabdeveloper4 5y ago
  Because "recipe for a smoothie" analogy is too broad and doesn't help you understand how the Fourier Transform is different from a Ruby script or a bill of materials for a chair. Not to mention that the idea of "given a smoothie, it finds the recipe" is impossible and makes no sense in the first place.
  - stocknoob 5y ago
    Tasting a drink and guessing its ingredients makes no sense?
    - otabdeveloper4 5y ago
      Except that absolutely not how the Fourier Transform works and gives a very false impression.

amitport 5y ago

I kind of wish he used tau instead of Hz here.

slowhand09 5y ago

Cool article.. For some application - see http://www.dspguide.com/pdfbook.htm http://www.dspguide.com/pdfbook.htm

aj7 5y ago

That’s the discrete Fourier transform. The difference is quite significant.

hansvm 5y ago

I see this particular mistake crop up a lot, and it's a bit pedantic, but I don't get the impression that it's being intentionally ignored for educational reasons: The author repeatedly describes "the" recipe, "the" set of frequencies, .... The standard Fourier transform is only unique conditioned on the fact that we've agreed on a particular set of basis functions ahead of time. It isn't even the only choice of orthogonal exponentials we could have picked. In terms of real applications that point often doesn't matter much -- especially in fields like lossy compression where you might not actually care much about any underlying meaning in the representation, and especially in fields like radio where your data is in some sense fundamentally represented as combinations of sinusoids -- but in general it isn't a sound leap to go from "this Fourier coefficient is big" to "there exists a big sinusoid that semantically matters to my data."

whatshisface 5y ago
Linear time-invariant physical processes are so common in the real world that it's not unreasonable to expect sinusoids to semantically matter... At least when the data pertains to physical systems.
- hansvm 5y ago
  Certainly. It's super reasonable to think that they might matter and to investigate that approach; it's unreasonable to take as an axiom that they matter and use that as proof of other facts.
joppy 5y ago
If you add some additional structure of remembering that the domain of these transformations is an abelian group, then there is actually a completely canonical version of the Fourier transform, whose domain is the dual group - the only non-canonical part is picking labels for elements of the dual group, but there is no other choice of basis functions. (Wikipedia gets a little into this, you can find it under "Pontryagin duality" on the Fourier transform page, but it's not really enough of an explanation to learn from). Take the discrete Fourier transform for example, whose domain group is Z/nZ: the integers-mod-n for some fixed n. The basis functions for the transforms need to be group homomorphisms f: Z/nZ -> C, meaning that they need to satisfy f(a + b) = f(a) f(b) for all a, b. Without too much trouble you can work out that the only such functions are of the form f(k) = exp(2 pi i m k / n) for m = 0, ..., n - 1. So once the group structure is remembered, the choice of basis is forced. The only ambiguity is relabelling the basis elements back into Z/nZ, which is a (very useful) hack. The same reasoning (with more complicated working) applies to taking the Fourier series of a periodic function, or taking the Fourier transform of a continuous function on the real line. There is a canonical choice of basis, but some ambiguity in what labels to assign to those basis elements.

YZF 5y ago

Probably worth saying "Discrete Fourier Transform"...