[HN Gopher] An Interactive Guide to the Fourier Transform (2012)
___________________________________________________________________
An Interactive Guide to the Fourier Transform (2012)
Author : parsecs
Score : 269 points
Date : 2021-05-21 02:21 UTC (20 hours ago)
(HTM) web link (betterexplained.com)
(TXT) w3m dump (betterexplained.com)
| hansvm wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| whatshisface wrote:
| Since you could be in any basis before taking the Fourier
| transform, it's more like there's a canonical _change-of-
| basis_ than there is a canonical _basis_. Time domain might
| not be the system 's most natural basis.
| etamponi wrote:
| 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
| lelanthran wrote:
| >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.
|
| Some things are less intuitive because of the dense equations.
| You'd have to be slightly insane to say that "x^2 = y^2 + z^2"
| is a more intuitive way to explain what a circle is than a
| picture of a circle.
|
| > Fortunately, the meaning is engraved in dense equations
|
| "I am very intelligent"
| fmihaila wrote:
| > Some things are less intuitive because of the dense
| equations. You'd have to be slightly insane to say that "x^2
| = y^2 + z^2" is a more intuitive way to explain what a circle
| is than a picture of a circle.
|
| It's the difference between qualitative and quantitative
| descriptions. Which one captures the full depth of the
| concept? Neither on its own; you need to contemplate both at
| the same time to capture that depth ("range" may be a better
| word). There is information hiding in the interplay between
| the two that is missed when considering them in isolation.
|
| I don't believe formalism is all we need, but it is necessary
| if the problem at hand requires more than just intuition.
| Conversely, formalism without qualitative understanding is
| opaque and sterile. Together, they combine operational
| ability and simple intuition into a higher form of intuition
| (operational intuition), the most desirable kind.
| anon_tor_12345 wrote:
| >You'd have to be slightly insane
|
| yes and this particular flavor of insanity has a name:
| pedantry.
|
| >the meaning is engraved in dense equations
|
| what's hilarious is that middling tier mathematically
| literate people worship mathematical formalism while truly
| mathematically literate people (i.e. mathematicians) eschew
| it because they understand that _mathematics can 't be
| formalized_ but also because it's natural language whose
| value is communication not codification. even here - ask
| someone to explain to you rigorously the definition of the
| fourier transform wrt dirac deltas. again the middling tier
| mathematically literate will assume that writing down an
| integral against a dirac delta is rigorous simply because you
| can write it down _completely forgetting that the dirac delta
| is a tempered distribution not a function_ and thus that
| integral means something completely different. ultimately it
| is the case that the definition is consistent with a set of
| agreed upon definitions but the symbology itself is just a
| pun.
| gugagore wrote:
| the value of [mathematical] language is not only
| communication, but also reasoning. It is remarkable, and
| sometimes unfortunate, how much mathematical reasoning you
| can do without knowing what you're doing, by pattern
| matching. Notation doesn't just allow you to communicate.
| It also allows you to manipulate e.g. truths that you know
| into truths that you do not yet know. In doing this
| abstract manipulation, you postpone (when necessary, and
| hopefully not indefinitely) thinking about semantics, while
| acting only syntactically.
|
| A lot of people say something like "math is a universal
| language", and it sounds like we both agree that's
| nonsense. But I think we disagree on the extent to which
| math is a natural language. Your comment does not, in my
| opinion, recognize the symbolic manipulation (which doesn't
| have to be mostly-linear sequences of symbols, but can be
| e.g. diagrams too) that make math math.
| ska wrote:
| > the dirac delta is a tempered distribution not a function
|
| Nah, it's a measure :)
|
| Joking aside your point is a good one. Notation is a
| necessary but flawed tool to communicate the details with
| minimal confusion.
| anon_tor_12345 wrote:
| >Nah, it's a measure :)
|
| lol tell me you're a physicist without telling me you're
| a physicist :)
|
| >with minimal confusion.
|
| i think this the key thing that people that do a little
| math but not an immense amount don't understand: notation
| serves the same purpose as short hand in any other
| speech/communication. locally it's crystal clear, where
| local can be as small as that paper, that subsection, or
| just that paragraph (cf "the distinction is clear from
| context" lolol). i've written papers myself where i
| switch notations midstream for efficiency's sake (try
| defining tensors without bases but then try manipulating
| them without index notation...) but taking notation for
| granted is just as likely to get you into trouble as
| taking an API's promises for granted (in fact they're
| exactly the same things - leaky abstractions).
| 6gvONxR4sf7o wrote:
| You're taking this to a really uncharitable extreme, but
| yay you can laugh at the "hilarious" "middling tier
| mathematically literate people," I guess.
| dls2016 wrote:
| > You'd have to be slightly insane to say that "x^2 = y^2 +
| z^2" is a more intuitive way to explain what a circle is than
| a picture of a circle.
|
| I would expect any freshmen STEM student to recognize
| sqrt(x^2+y^2) as the distance of an (x,y) point to the
| origin. And the equation x^2+y^2=r^2 says this quantity must
| be fixed.
|
| Now I wouldn't expect a student to be able to write the
| previous two sentences so clearly.
|
| This gets to the heart of the paradox of learning. How to see
| past the clutter if you don't know what you're looking for?
|
| The human brain is lazy and prone to skipping logical steps,
| as reflected in the variation in natural language (and
| student's writing skills). Therefore learning a natural
| language does not demand simplicity up front.. unlike the up-
| front rigor required to learn mathematics notation or a
| programming language.
| anon_tor_12345 wrote:
| >How to see past the clutter if you don't know what you're
| looking for?
|
| the picture of the circle isn't clutter - in a very precise
| sense it is the definition (platonic ideal). the algebraic
| definition "x^2 = y^2 + z^2" clearly isn't the definition
| because it's missing things (which field is this polynomial
| over?). there are many other definitions (another is R/Z).
|
| >mathematics notation or a programming language
|
| notation isn't a formal language - there is no formal
| grammar written down somewhere and in fact there can be
| none (cf godel). whether you realize it or not it's a
| natural language that evolves, has slang, and is spoken to
| various degrees of competency by many successful
| mathematicians.
| dls2016 wrote:
| > the picture of the circle isn't clutter - in a very
| precise sense it is the definition (platonic ideal)
|
| Which precise sense? I get that language is slippery, but
| I can't follow you if you get philosophical, bring up
| fields (maybe the polynomial is defined over a ring!)
| while simultaneously stating that your favorite
| definition is The One True Way (TM).
|
| How does one use the platonic ideal to distinguish a
| circle from an ellipse?
|
| > whether you realize it or not it's a natural language
| that evolves
|
| Yes, I realize.
|
| My point was that the day-to-day usage of natural
| language tolerates a lot of ambiguity. Whereas the
| classroom usage of mathematical/programming notation does
| not. It's hard to be informal and "break the rules" as a
| beginner while retaining precision. Because the web of
| potential associations hidden in a statement (the
| "clutter") hasn't yet been pruned down by experience.
|
| Writing is hard.
| anon_tor_12345 wrote:
| >Which precise sense?
|
| in the sense that "mathematical entities are abstract,
| have no spatiotemporal or causal properties, and are
| eternal and unchanging"
|
| https://en.wikipedia.org/wiki/Philosophy_of_mathematics#P
| lat...
|
| >How does one use the platonic ideal to distinguish a
| circle from an ellipse?
|
| entailed in the picture "definition" is constant
| curvature.
|
| >while simultaneously stating that your favorite
| definition is The One True Way (TM).
|
| that's not what i wrote.
|
| >Whereas the classroom usage of mathematical/programming
| notation does not.
|
| i won't speak to programming notation but every upper
| level or grad math class i've had has been at times
| extremely informal in its use of notation. take an
| integral on any chalkboard in any class and you're almost
| certain to have these questions without listening to the
| lecture itself (i.e. it's omitted from the notation):
|
| 1 what is the domain? R or C or something really exotic
|
| 2 is it over a closed contour/boundary or open?
|
| 3 what's the metric? i.e. are we actually integrating
| forms?
|
| 4 is it even an integral at all not just shorthand for
| solving a differential equation (e.g. stochastic
| integral)
| dls2016 wrote:
| > in the sense that "mathematical entities are abstract,
| have no spatiotemporal or causal properties, and are
| eternal and unchanging"
|
| oh THAT sense, why didn't you just say so?
|
| but seriously what does that sense have to do with a
| picture of a circle? how would one _use_ the picture of a
| circle to distinguish from an ellipse?
|
| edit: nobody ever checked if i knew diddly squat about
| "real actual academic platonism v formalism" before
| peforming mathematical exposition in front of numerous
| classrooms in at least two countries, and surely i'm not
| going to hold back while arguing on the internet!
| anon_tor_12345 wrote:
| >oh THAT sense, why didn't you just say so?
|
| i mean if you're not familiar with the real actual
| academic platonism v formalism debate maybe you shouldn't
| pontificate on what's better or worse re mathematical
| exposition?
| rovolo wrote:
| As a compromise between you two:
|
| > Fortunately, the process is engraved in dense equations.
| Unfortunately, the dense equations make it difficult to learn
| why we're following this process.
| seoaeu wrote:
| But "dense" in this context literally means "difficult to
| understand". If you are trying to build intuition, then that is
| pretty much by definition a bad thing.
| ath92 wrote:
| 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 wrote:
| Surprisingly for me, it's the other way around! Equations
| build intuition in my case, although I'm not sure why.
| thomasahle wrote:
| 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 wrote:
| 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.
| Patient0 wrote:
| 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)
|
| - 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)
|
| 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
| Sharlin wrote:
| Huh, this is great. Thanks.
| only_as_i_fall wrote:
| 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
| Patient0 wrote:
| Basically yes - but even now I'd have to admit I have no
| intuition for why the different "frequency" functions are
| orthogonal to each other.
| YZF wrote:
| Probably worth saying "Discrete Fourier Transform"...
| slowhand09 wrote:
| Cool article.. For some application - see
| http://www.dspguide.com/pdfbook.htm
| jmchuster wrote:
| i'd assume 3b1b would have an intuitive video about it as well
| kentor wrote:
| The 3b1b video was mind blowing. Link:
| https://www.youtube.com/watch?v=spUNpyF58BY
| travisgriggs wrote:
| Agreed! Came here to post it. First time I really "got" what
| an FFT was about.
| otabdeveloper4 wrote:
| > 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 wrote:
| 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 wrote:
| 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 wrote:
| Tasting a drink and guessing its ingredients makes no
| sense?
| otabdeveloper4 wrote:
| Except that absolutely not how the Fourier Transform
| works and gives a very false impression.
| TeeMassive wrote:
| 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 wrote:
| 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 wrote:
| For those who may not have heard of it:
|
| 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.
| dang wrote:
| Some past threads:
|
| _An Interactive Guide to the Fourier Transform_ -
| 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 - Dec 2012 (25
| comments)
|
| These are similar:
|
| _An Interactive Introduction to Fourier Transforms_ -
| https://news.ycombinator.com/item?id=25095724 - Nov 2020 (52
| comments)
|
| _An Interactive Introduction to Fourier Transforms_ -
| https://news.ycombinator.com/item?id=20934347 - Sept 2019 (44
| comments)
|
| _An Interactive Introduction to Fourier Transforms_ -
| 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 - Jan 2018 (31
| comments)
|
| _Ask HN: Where can I learn about fourier transformations?_ -
| 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 -
| April 2017 (83 comments)
|
| _The Fourier Transform and its Applications_ -
| https://news.ycombinator.com/item?id=12476692 - Sept 2016 (55
| comments)
|
| _The Medieval Fourier Transform_ -
| 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 - Oct 2014 (82
| comments)
|
| _The Fourier Transform and its Applications_ -
| https://news.ycombinator.com/item?id=7789767 - May 2014 (22
| comments)
|
| _Fourier transform for dummies_ -
| https://news.ycombinator.com/item?id=7468193 - March 2014 (37
| comments)
|
| _Understanding the Fourier transform (2011)_ -
| https://news.ycombinator.com/item?id=6686456 - Nov 2013 (6
| comments)
|
| _Understanding The Fourier Transform_ -
| https://news.ycombinator.com/item?id=4861960 - Dec 2012 (44
| comments)
|
| _Intuitive explication of Fourier Transformation_ -
| 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 - May 2010 (11
| comments)
|
| _Mastering The Fourier Transform in One Day_ -
| https://news.ycombinator.com/item?id=698929 - July 2009 (18
| comments)
|
| _An Intuitive Explanation of Fourier Theory_ -
| https://news.ycombinator.com/item?id=56844 - Sept 2007 (11
| comments)
| Cybotron5000 wrote:
| You beauty! Thanks so much! HN rules! :)
| ZephyrBlu wrote:
| Do you have a bunch of these lists tucked away specifically for
| this purpose?
| xNeil wrote:
| We should have something like the Wikipedia list of lists of
| lists, sorted by HN submissions on several topics.
| dang wrote:
| Nope, I just use HN search to find them - but I have software
| that makes it fast to do, including formatting the lists.
| Previous times this came up, if anyone is curious:
|
| https://news.ycombinator.com/item?id=26158300
|
| https://news.ycombinator.com/item?id=26885540
|
| https://news.ycombinator.com/item?id=26244468
|
| I'm thinking of adding code to macroexpand all HN links (to
| submissions) that people post, into the same format I'm using
| above: "Title - <url> - mm/yy - (number of comments)". Can
| anybody think of a downside to doing that?
|
| Longer term, we'd like to make this a community thing so
| everyone can curate these lists collaboratively. There are
| often major related threads that don't show up in the obvious
| HN searches, because their titles didn't include the obvious
| search terms. For any such thread there's probably at least
| one HN user who remembers it, and I'd love to give them a
| chance to add it.
|
| There's also the related (no pun intended) question of how to
| bundle together related articles on current ongoing stories,
| whether or not they have HN threads.
| BlueTemplar wrote:
| Would make sense for classics like these !
| itissid wrote:
| 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=3Blue...
| BlueTemplar wrote:
| Haven't they "just" taken the above explanation, and made a
| video about it ?
| sillysaurusx wrote:
| 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...
|
| Many of the chapters are here:
| 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
|
| 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.
| mhh__ wrote:
| 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.
| tracyhenry wrote:
| Google's FNet seems to apply FT to NNs?
| https://arxiv.org/abs/2105.03824
| sillysaurusx wrote:
| That paper was one of the most misleading papers I've ever
| seen in NNs.
| 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 wrote:
| 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 wrote:
| 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
| 37ef_ced3 wrote:
| For neural nets, 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!
| aj7 wrote:
| That's the discrete Fourier transform.
|
| The difference is quite significant.
| geokon wrote:
| 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 )
|
| 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
| BlueTemplar wrote:
| 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:Com...
|
| See also geometric/Clifford Algebra :
| http://www.av8n.com/physics/clifford-intro.htm (Though note
| that it _does_ require TWO different "multiplication"
| operations to make sense !)
| geokon wrote:
| Oh woah, I've never seen that visualization - very cool. I
| only meant to really highlight that often things are thrown
| on the complex plane and presented in introductory material
| as making the problem in 2D. The few times I've seen this
| (physics, math and signal processing classes) I've never
| actually seen it emphasized anywhere that the complex plane
| is fundamentally different from a cartesian 2D plane. It's
| the crux of the whole spinning unit circle stuff and then why
| you get orthogonality
|
| I still find the visualization completely unnecessary b/c it
| doesn't help illustrate or give any kind of intuition for why
| the basis vectors are orthogonal
| BlueTemplar wrote:
| Actually, that very same website gives it too, and even a
| 2nd visualization !
|
| https://betterexplained.com/articles/understanding-why-
| compl...
|
| Is what bothers you that the complex plane has this very
| specific feature that purely imaginary x purely imaginary =
| real, so you're "mixing" orthogonal dimensions ?
|
| However, I still don't understand your reticence, since
| imaginary numbers _are_ fundamentally about cycles and
| rotations (via exponentiation), and rotations fundamentally
| require having 2 dimensions to represent them : hence a
| plane !
|
| (Like you say, you also need 2 dimensions to be able to
| have orthogonality...)
|
| And I'm getting a bit rusty here, but I guess that
| imaginary being orthogonal to real might be why these
| Fourier basis vectors are orthogonal ?
|
| I mean, it's literally Euler's formula :
|
| exp(taiith) = cos(taith) + i sin(taith)
|
| I don't remember, aren't those 2 orthogonal basis vectors
| "cos" and "sin" ?
| [deleted]
| joppy wrote:
| > The complex plane is a crutch that gives you pretty pictures.
|
| That's a very poor outlook on an incredibly useful mathematical
| tool. Maths is done essentially by finding new ways of viewing
| an old thing, and restricting the set of tools available seems
| like a poor idea in general. As for _teaching_ mathematics,
| finding more ways of looking at something, however imprecise,
| is a huge aid to understanding. Never be afraid to show someone
| a picture that's only 80% true but could potentially aid their
| understanding in how something works!
|
| I also disagree that the "circular paths" visualisation is
| misleading - what is misleading about it? This is a completely
| accurate representation of how a Fourier series is added up to
| get a real part which varies over time. It even makes it
| intuitive that multiplying the series by a fixed complex number
| (corresponding to rotating and scaling the "orbiting" points on
| the left) will have the effect of translating the resulting
| signal to the right or the left.
|
| Also for what it's worth, the product of complex numbers is
| easy to visualise? Add their angles, multiply their magnitudes.
| only_as_i_fall wrote:
| This would explain why Fourier ended The Analytical Theory of
| Heat with his famous afterword:
|
| "and don't even think about using any of this if you haven't
| internalized it as well as I have you fucking idiot."
| nspattak wrote:
| Why is it wrong? I was not lost.
| kortex wrote:
| Why is there always this pushback against "popsci explanations"
| in these threads? Do people not realize every brain is unique
| and people have different learning styles? A few hours of
| 3blue1brown videos gave me a useful intuition about FT, FFT,
| quaternions, and other mathematical things that years of
| courses with equations and homework failed to do.
|
| I'm talking real, useful intuition that improved my work in
| signals processing, using wavelets, filters, convolutions etc.
|
| And yes I can visualize 3.5D pretty easily in my head: a 3D
| volume with layers and colors that overlap. Though usually it's
| easier to picture two 2D frames side-by-side.
|
| I don't fault people when they grok words/equations but visual
| diagrams do nothing for them (blueprints/CAD are an enigma to
| my partner). Don't fault people for needing visualization to
| grok equations.
| anon_tor_12345 wrote:
| >Why is there always this pushback against "popsci
| explanations" in these threads?
|
| because underneath all of the rhetoric about
| entrepreneurialism and "disrupting" thing tech (and by
| extension HN) is one of the most conservative and elitest
| communities that has ever existed. think about what people
| used to say about dynamic languages vs statically typed,
| about frontend vs backend, about sql vs nosql, etc etc etc.
| stodgy old engineers have always (and will always) resist the
| bar being lowered and newcomers being admitted.
|
| edit:
|
| what's funny is that the opposite response shows up,
| invariably, on posts that are very precise and technical.
| i.e. something like "this is too technical i wish
| mathematicians would accommodate us lay folk".
| zaptheimpaler wrote:
| > stodgy old engineers have always (and will always) resist
| the bar being lowered and newcomers being admitted.
|
| I try not be elitist or unwelcoming to newcomers, but yeah
| uh why should we lower the bar? Are the newcomers somehow
| incapable of learning engineering at the same level that
| the old ones did? Its no fun to work with people who aren't
| as motivated and cry for a lower bar instead of rising to
| the challenge. Its easy to work with someone more motivated
| than you but it sucks to work with someone less motivated.
| geokon wrote:
| I didn't mean to imply that there is anything wrong with
| visualization. I feel they're easier to understand than
| equations for the vast majority of people. But as a concrete
| example, to understand the Fourier transform it probably took
| me a couple of weeks of reading different textbooks in my
| spare time to really grok how the math works here.. it took
| some effort and I'm not some autistic savant that sees things
| in equations - so it has nothing to do with learning styles.
|
| Looking at some diagrams and videos for certain topics is a
| lazy and harmful approach to learning because some problems
| are just not conducive to visualization. Efforts to force a
| visualization ends up being actively bad and give viewers the
| wrong idea. My comment was a point by point explanation of
| how this ends up happening. At least in this particular case,
| with the Fourier Transform, the visualizations in effect made
| it harder for me personally to understand how the math works
| b/c they are so sloppy and emphasis all the wrong points.
|
| In the grand scheme of things, having a half-assed popsci
| understanding is generally worse than not know anything. You
| can get a sense of overconfidence and then go on to apply
| these techniques incorrectly and make broken/fragile systems
| that make no mathematical sense (or publish insane papers)
|
| If you really work with signal processing and don't
| understand the mathematics of the fourier transform then
| that's frankly a little scary. I'd really recommend taking
| the time to understand it b/c I think it really pays off -
| but yes, it takes a bit more effort than watching a youtube
| video..
| stainforth wrote:
| >But as a concrete example, to understand the Fourier
| transform it probably took me a couple of weeks of reading
| different textbooks in my spare time to really grok how the
| math works here.. it took some effort and I'm not some
| autistic savant that sees things in equations - so it has
| nothing to do with learning styles.
|
| So you're still claiming your experience covers all.
| anon_tor_12345 wrote:
| >Looking at some diagrams and videos for certain topics is
| a lazy and harmful approach to learning
|
| god my eyes can't roll farther back in my head. your point
| would be less absurd if it weren't for the fact that
| algebraic geometry is an enormously powerful and productive
| area of math whose whole ass founding principle is that
| geometric interpretations of algebraic objects are
| _extremely_ useful.
|
| AND
|
| spectral theory (what fourier analysis is called today) is
| an extremely geometric area owing to the dependence of
| convergence on the metric.
|
| >In the grand scheme of things, having a half-assed popsci
| understanding is generally worse than not know anything
|
| yes because this is a resource for rocket scientists and
| not interested people (probably high school and college
| students)?
|
| >If you really work with signal processing and don't
| understand the mathematics of the fourier transform then
| that's frankly a little scary.
|
| bro this isn't oppenheim. it's just a nice intro for people
| that might be curious or are learning for the first time.
| amitport wrote:
| I kind of wish he used tau instead of Hz here.
___________________________________________________________________
(page generated 2021-05-21 23:02 UTC)