Not so fast, Mr. Fourier(lcamtuf.substack.com)
lcamtuf.substack.com
Not so fast, Mr. Fourier
https://lcamtuf.substack.com/p/not-so-fast-mr-fourier
9 comments
> In any case, I've seen so many engineers insist in the time to frequency explanation that it must somehow be easier to understand for people.
Fourier may have used his eponymous transform for working on the heat equation, but for many generations now the primary engineering applications of it have been in electric circuit theory and acoustics, both of which live in constant need for time <-> frequency conversions.
Effectively all the literature in fourier analysis in engineering is written by or for someone whose background is in either electronics or acoustics.
e.g., the bible for many engineers is Oppenheim, Willsky and Nawab, “Signals and Systems”; all three authors are primarily EE (Nawab is BME, but trained by EEs)
Fourier may have used his eponymous transform for working on the heat equation, but for many generations now the primary engineering applications of it have been in electric circuit theory and acoustics, both of which live in constant need for time <-> frequency conversions.
Effectively all the literature in fourier analysis in engineering is written by or for someone whose background is in either electronics or acoustics.
e.g., the bible for many engineers is Oppenheim, Willsky and Nawab, “Signals and Systems”; all three authors are primarily EE (Nawab is BME, but trained by EEs)
> I studied math, so I can never understand the insistence that the truth of the fourier transform is that it converts from the time domain into the frequency domain. What if you apply the fourier transform twice? Something similar is done in voice processing, and it's perfectly valid.
And I never understood the insistence of mathematicians to open with the generalized case when literally 99% of the use cases of a thing involve the more specialized use case. That is like a car mechanic telling you a part can be also used as a paperweigth when that is nearly never what it is used for.
Don't get me wrong here – I like to hear about other usecases of something – I also like to hear generalized explainations of a thing – but that isn't how you should start when you explain a mathematical concept. It is nearly always better to start with a common special case in which the gory details don't apply and explain why the concept is important and what it does for us to then branch out than the other way around. Turns out most people first need a motivation why they should invest their brain in a thing and only then they are willing to do it. I could have strangled my maths teacher when they consistently mentioned the application in a side comment after weeks of theory and then did as if that wasn't that important. Yeah if all you do is teaching math or doing math for maths sake, it isn't, but that isn't going to be many people. And the Fourier analysis was famously the solution to a few actual real world problems that were very hard to tackle otherwise – why not tell that story?
As I said, function spaces are cool, but maybe it is better to start with something else so people can appreciate it.
And I never understood the insistence of mathematicians to open with the generalized case when literally 99% of the use cases of a thing involve the more specialized use case. That is like a car mechanic telling you a part can be also used as a paperweigth when that is nearly never what it is used for.
Don't get me wrong here – I like to hear about other usecases of something – I also like to hear generalized explainations of a thing – but that isn't how you should start when you explain a mathematical concept. It is nearly always better to start with a common special case in which the gory details don't apply and explain why the concept is important and what it does for us to then branch out than the other way around. Turns out most people first need a motivation why they should invest their brain in a thing and only then they are willing to do it. I could have strangled my maths teacher when they consistently mentioned the application in a side comment after weeks of theory and then did as if that wasn't that important. Yeah if all you do is teaching math or doing math for maths sake, it isn't, but that isn't going to be many people. And the Fourier analysis was famously the solution to a few actual real world problems that were very hard to tackle otherwise – why not tell that story?
As I said, function spaces are cool, but maybe it is better to start with something else so people can appreciate it.
Are you trying to acquire a tool for your toolbox, or are you trying to understand the concepts that allow you to invent such tools?
Teaching math is all about the latter, while some people are only interested in the former and struggle.
Teaching math is all about the latter, while some people are only interested in the former and struggle.
When I studied group theory, I would have been so much happier if someone told me we were talking about nonzero numbers, or invertible matrices, or functions. A little of bit of concreteness would have helped enormously to motivate the topic.
When I took real analysis, I would have been so much happier if the teacher had presented some historical context: what pitfalls had mathematicians fallen into by misunderstanding infinity?
That’s just how my brains work. I need some context. I suspect other brains are like mine too.
When I took real analysis, I would have been so much happier if the teacher had presented some historical context: what pitfalls had mathematicians fallen into by misunderstanding infinity?
That’s just how my brains work. I need some context. I suspect other brains are like mine too.
I'm sympathetic to that view but most engineering disciplines are just interested in having the tool for their toolbox. Their interest in understanding the concepts that allow them to invent such tools is focused on their own discipline, which is not mathematics.
Motivating students with real world applications first is IMO the only real chance to potentially spark their interest in learning broader concepts.
Motivating students with real world applications first is IMO the only real chance to potentially spark their interest in learning broader concepts.
Your metaphor works both ways. If you teach the kids in kindergarden the theory of intricate japanese wood joints before they know which end of the saw to hold you are wasting your (and their) time.
As I said, all things have their place, but some mathematicians have the habbit of starting at the most general (and therefore most abstract and most distant from the layperson) point to then move to more concrete applications. My suggestion wasn't to skip the general perspective, it was to teach it at a point where people already know and maybe even use the thing that is being generalized.
That being said, not everybody is a mathematician. For some (and I'd argue: most) people using the fourier transformation as "just" a means to figure out the partials of any given signal is the tool they are looking for.
As I said, all things have their place, but some mathematicians have the habbit of starting at the most general (and therefore most abstract and most distant from the layperson) point to then move to more concrete applications. My suggestion wasn't to skip the general perspective, it was to teach it at a point where people already know and maybe even use the thing that is being generalized.
That being said, not everybody is a mathematician. For some (and I'd argue: most) people using the fourier transformation as "just" a means to figure out the partials of any given signal is the tool they are looking for.
without leading with the general case we end up with nonsense like "Tai's method"; endless reinvention and rediscovery through ignorance.
Isn't that depensing on whom you are teaching and for what purpose?
Or does that consideration really not exist in math world?
Or does that consideration really not exist in math world?
Dusde honestly I think its a personal preference thing. Like personally, calculus never clucked for me at all until I took a rigourous course with a skilled lrofessor who derived many important theorems in front of the class. After that I was able to contextualize all the real world examples and things fell inti place. I think some people really do learn better in the abstract first.
I guess you are right, yet seen from the perspective of an educator you might see the advantage of choosing a teaching approach that gets more people going in a faster way. I am not talking about people who are studying maths, but people for whom maths is an means to an end, or maybe even just an obstacle they are forced to deal with.
Imagine a language class where the teacher only engaged with those who already know how to speak the language, that would be seen as bad teaching, especially if it is a course for pre-school-kids.
Imagine a language class where the teacher only engaged with those who already know how to speak the language, that would be seen as bad teaching, especially if it is a course for pre-school-kids.
Some people think top-down (general to specific); some people think bottom up (specific to general). You cannot specialize your teaching for one group or the other - not unless you know that you only have one kind of people that you're teaching.
Yeah but with top down we are talking about the question how it fits into the students known world not about how it is defined in the most basal abstract way.
I think it’s just that the time/frequency analogy is so strongly rooted in signals processing applications
In the physics and crystallography literature the Fourier transform is framed in terms of real space and reciprocal space, which personally I think is much more natural in the context of computing a structure factor or diffraction pattern for example. Many measurements (like diffraction) most directly measure reciprocal space, and one applies the inverse Fourier transform to recover the real space information of interest.
Sometimes I think instead of time and frequency it would be more clear to frame signal processing applications in terms of time and reciprocal time just to highlight the symmetry and make it more clear that there’s nothing special about time and frequency vs some other dimension
In the physics and crystallography literature the Fourier transform is framed in terms of real space and reciprocal space, which personally I think is much more natural in the context of computing a structure factor or diffraction pattern for example. Many measurements (like diffraction) most directly measure reciprocal space, and one applies the inverse Fourier transform to recover the real space information of interest.
Sometimes I think instead of time and frequency it would be more clear to frame signal processing applications in terms of time and reciprocal time just to highlight the symmetry and make it more clear that there’s nothing special about time and frequency vs some other dimension
Starting with the most abstract explanation may work for mathematicians, but most other people prefer starting with concrete examples.
> What if you apply the fourier transform twice?
You're back in the time domain except reversed in time.
You're back in the time domain except reversed in time.
> On both plots, the horizontal axis represents time. In the bottom image, the vertical axis represents frequency and pixel color represents intensity.
The author criticizes the Wikipedia article on the subject being too complex, and yet dives straight into the spectrogram of the audio signal as the first picture on the page! And the first equation is the complex exponential representation of the Fourier sum...
The Digital Signal Processing book of Proakis and Manolakis does a perfectly good job of explaining what DFT (and everything else around this matter) is. But there are no shortcuts around it; you still have to understand the Sampling Theorem (aliasing), Fourier series of continuous periodic signals, frequency-domain sampling of Fourier transforms, etc.
It took me a while to (somewhat) understand all the nuances of Fourier series and transforms of continuous and discrete signals. And the DFT is a whole layer of theory on top of that. I don't imagine a simple explanation of that begin feasible. However, a more readable or coherent explanation is, of course, always possible.
The author criticizes the Wikipedia article on the subject being too complex, and yet dives straight into the spectrogram of the audio signal as the first picture on the page! And the first equation is the complex exponential representation of the Fourier sum...
The Digital Signal Processing book of Proakis and Manolakis does a perfectly good job of explaining what DFT (and everything else around this matter) is. But there are no shortcuts around it; you still have to understand the Sampling Theorem (aliasing), Fourier series of continuous periodic signals, frequency-domain sampling of Fourier transforms, etc.
It took me a while to (somewhat) understand all the nuances of Fourier series and transforms of continuous and discrete signals. And the DFT is a whole layer of theory on top of that. I don't imagine a simple explanation of that begin feasible. However, a more readable or coherent explanation is, of course, always possible.
> For a nonsensical but amusing demo that lets you watch what happens if you apply JPEG-style lossy compression to text, check out this post.
The link seems broken, since it points back to the same article at https://lcamtuf.substack.com/p/not-so-fast-mr-fourier
The link seems broken, since it points back to the same article at https://lcamtuf.substack.com/p/not-so-fast-mr-fourier
Needs to be fixed to go to
https://lcamtuf.substack.com/p/afternoon-project-jpeg-dct-te...
So I can feed a lossy text to an LLM and it can “delossy” it?
Does the lossy text take up less space so this could work as a weird compression?
Does the lossy text take up less space so this could work as a weird compression?
Use an embedding, then quantize (i.e. rounding) maybe?
I wonder how that would look like if it used word2vec.
Meh. The author confuses DFT with STFT. They refer to the STFT as "DFT", but then introduce the usual IDFT as the inverse transform, which is not the inverse of the STFT (the inverse STFT can be computed with the overlap-add method).
I don't think your comment is accurate. The formulas appear to be DFT and IDFT, in line with:
https://home.engineering.iastate.edu/~julied/classes/ee524/L...
https://home.engineering.iastate.edu/~julied/classes/ee524/L...
Did you even read the article, or just looked at the LaTeX formulas?
I'll give you a hint: Cmd+F "window". See any results? Because the DFT doesn't have a window function. The STFT does have a window function.
Second hint: look at the image in the article (https://substackcdn.com/image/fetch/w_1456,c_limit,f_webp,q_...). Do you think this shows the time domain and frequency domain representations (i.e. the DFT) of a signal? No, it does not. It shows the time domain representation, and the STFT of the signal, aka the spectrogram.
Do you have any questions?
I'll give you a hint: Cmd+F "window". See any results? Because the DFT doesn't have a window function. The STFT does have a window function.
Second hint: look at the image in the article (https://substackcdn.com/image/fetch/w_1456,c_limit,f_webp,q_...). Do you think this shows the time domain and frequency domain representations (i.e. the DFT) of a signal? No, it does not. It shows the time domain representation, and the STFT of the signal, aka the spectrogram.
Do you have any questions?
Consider ordinary 3 dimensional space: Go to a corner of the room, where the floor and two walls meet, and see three lines, each line the intersection of the two walls or a wall and the floor. In usual building architecture, these three lines are mutually perpendicular, i.e., orthogonal.
Regard each of these three lines as an axis of a coordinate system. In particular, pick a point on each of the three axes to give us points with coordinates:
(1,0,0) -- the X axis
(0,1,0) -- the Y axis
(0,0,1) -- the Z axis
Soooo, now we have a standard coordinate system for ordinary 3 dimensional space.
Now consider a point P in the room (in my case, the end of the pony tail of that sweet, gorgeous blond I keep looking at!) with coordinates
(x,y,z)
for some numbers x, y, z.
For the X coordinate of point P we make use of the X axis and our point P: We take the dot (inner) product of
(1,0,0) and (x,y,z)
and get, presto, bingo, wonder of wonders, no doubt, x.
Similarly for y and z.
Or, for each axis, our inner product projects point P on that axis. And from those projections we can reconstruct the coordinates of point P. Beginning to sound like Fourier theory????
This stuff of projections onto orthogonal and then reconstructions from that generalizes.
In Fourier theory, those sine waves are mutually perpendicular -- project one on another and get 0. That summation is the inner product for that projection.
And if not a summation, then an integration -- same stuff, use an inner product to do projections onto mutually perpendicular axes.
For the finite stuff, and just summation signs, it's fairly elementary.
For the integral stuff, with the Riemann integral of calculus, can see Baby Rudin, Principles of Mathematical Analysis and Fourier series, over finite lengths of time. For the Fourier integral, over the whole real axis, see the Lebesgue integral (partition on the Y axis instead of the X axis and get nicer properties) in Rudin's Real and Complex Analysis. For a version that uses Schwartz distributions, there Rudin's Functional Analysis.
Net, it's all about inner products and projections as we saw in the corner of a room.
Soooo, for some of the generalization, are working in an inner product space. A nice introduction is, of course, Halmos, Finite Dimensional Vector Spaces: Soooo, that's ordinary linear algebra, finite dimensional, but done with techniques that mostly generalize to infinite dimensions, e.g., as in Fourier series, integrals, distributions.
Rudin's Real and Complex Analysis also does Fubini's theorem that helps with doing Fourier theory on surfaces, e.g., the ocean.
History: Halmos had gotten his Ph.D. under Doob, of Stochastic Processes (e.g., the stock market, weather, medical EGK, ...), and got a position under John von Neumann at the Institute for Advanced Study in Princeton; so, apparently Halmos wrote his finite dimensional book borrowing from von Neumann's work on the infinite dimensional case, e.g., as in von Neumann's Quantum Mechanics.
Right, a complete inner product space is a Hilbert space -- the complete is essentially as also in the real numbers, sequences that appear to converge in the distance (from the inner product) used always do have something to converge to.
Sooo, Hilbert space has a lot, asks a lot, making the examples restricted -- Rudin has a nice theorem that shows that really there's only one Hilbert space!
Halmos is my favorite author. Rudin is a close second.
Education Technique: While starting my career in computing, I studied both Halmos and Rudin carefully, independently. In linear algebra, also E. Nering. At the time, did a lot with the FFT (fast Fourier transform, mostly of J. Tukey), and, thus, at one point got "sole source" on some work for the US Navy. Then in grad school, the backgrounds in Halmos, Nering, Rudin, and the computing got me the best in the class on the three Ph.D. qualifying exams -- linear algebra, analysis, computing.
As I recall, Nering was a student of E. Artin, at Princeton. Nering's book also considers the case of finite fields, that is, not only the rational, real, complex numbers. That helped in a course in error correcting codes.
Why is the FFT "fast"? Well, if all you want is some one Fourier coefficient, it's not "fast". If you want all the coefficients, then just write a Do-loop and find them all one at a time -- easy enough to do. Get the discrete Fourier transform. But if go for all the coefficients this way very often on fairly long streams of data, then can slow down even a fast computer. BUT: If the number of points in time is a power of 2, commonly 1024 = 2^10, and look carefully at elementary trigonometry, can see how to do a little on all the computing, then a little more on all of it, ..., for ~10 such passes, and, presto, bingo, be really a LOT faster, essentially n log(n) instead of n^2.
There's more at
https://www.youtube.com/watch?v=nmgFG7PUHfo
with the role of Richard Garwin working to do Fourier analysis on seismic data as part of detection of underground nuclear tests.
Much of the faculty was really, REALLY torqued that (1) I didn't fail the exams and (2) led the class. REALLY torqued!
Halmos, Rudin -- can be good stuff.
Regard each of these three lines as an axis of a coordinate system. In particular, pick a point on each of the three axes to give us points with coordinates:
(1,0,0) -- the X axis
(0,1,0) -- the Y axis
(0,0,1) -- the Z axis
Soooo, now we have a standard coordinate system for ordinary 3 dimensional space.
Now consider a point P in the room (in my case, the end of the pony tail of that sweet, gorgeous blond I keep looking at!) with coordinates
(x,y,z)
for some numbers x, y, z.
For the X coordinate of point P we make use of the X axis and our point P: We take the dot (inner) product of
(1,0,0) and (x,y,z)
and get, presto, bingo, wonder of wonders, no doubt, x.
Similarly for y and z.
Or, for each axis, our inner product projects point P on that axis. And from those projections we can reconstruct the coordinates of point P. Beginning to sound like Fourier theory????
This stuff of projections onto orthogonal and then reconstructions from that generalizes.
In Fourier theory, those sine waves are mutually perpendicular -- project one on another and get 0. That summation is the inner product for that projection.
And if not a summation, then an integration -- same stuff, use an inner product to do projections onto mutually perpendicular axes.
For the finite stuff, and just summation signs, it's fairly elementary.
For the integral stuff, with the Riemann integral of calculus, can see Baby Rudin, Principles of Mathematical Analysis and Fourier series, over finite lengths of time. For the Fourier integral, over the whole real axis, see the Lebesgue integral (partition on the Y axis instead of the X axis and get nicer properties) in Rudin's Real and Complex Analysis. For a version that uses Schwartz distributions, there Rudin's Functional Analysis.
Net, it's all about inner products and projections as we saw in the corner of a room.
Soooo, for some of the generalization, are working in an inner product space. A nice introduction is, of course, Halmos, Finite Dimensional Vector Spaces: Soooo, that's ordinary linear algebra, finite dimensional, but done with techniques that mostly generalize to infinite dimensions, e.g., as in Fourier series, integrals, distributions.
Rudin's Real and Complex Analysis also does Fubini's theorem that helps with doing Fourier theory on surfaces, e.g., the ocean.
History: Halmos had gotten his Ph.D. under Doob, of Stochastic Processes (e.g., the stock market, weather, medical EGK, ...), and got a position under John von Neumann at the Institute for Advanced Study in Princeton; so, apparently Halmos wrote his finite dimensional book borrowing from von Neumann's work on the infinite dimensional case, e.g., as in von Neumann's Quantum Mechanics.
Right, a complete inner product space is a Hilbert space -- the complete is essentially as also in the real numbers, sequences that appear to converge in the distance (from the inner product) used always do have something to converge to.
Sooo, Hilbert space has a lot, asks a lot, making the examples restricted -- Rudin has a nice theorem that shows that really there's only one Hilbert space!
Halmos is my favorite author. Rudin is a close second.
Education Technique: While starting my career in computing, I studied both Halmos and Rudin carefully, independently. In linear algebra, also E. Nering. At the time, did a lot with the FFT (fast Fourier transform, mostly of J. Tukey), and, thus, at one point got "sole source" on some work for the US Navy. Then in grad school, the backgrounds in Halmos, Nering, Rudin, and the computing got me the best in the class on the three Ph.D. qualifying exams -- linear algebra, analysis, computing.
As I recall, Nering was a student of E. Artin, at Princeton. Nering's book also considers the case of finite fields, that is, not only the rational, real, complex numbers. That helped in a course in error correcting codes.
Why is the FFT "fast"? Well, if all you want is some one Fourier coefficient, it's not "fast". If you want all the coefficients, then just write a Do-loop and find them all one at a time -- easy enough to do. Get the discrete Fourier transform. But if go for all the coefficients this way very often on fairly long streams of data, then can slow down even a fast computer. BUT: If the number of points in time is a power of 2, commonly 1024 = 2^10, and look carefully at elementary trigonometry, can see how to do a little on all the computing, then a little more on all of it, ..., for ~10 such passes, and, presto, bingo, be really a LOT faster, essentially n log(n) instead of n^2.
There's more at
https://www.youtube.com/watch?v=nmgFG7PUHfo
with the role of Richard Garwin working to do Fourier analysis on seismic data as part of detection of underground nuclear tests.
Much of the faculty was really, REALLY torqued that (1) I didn't fail the exams and (2) led the class. REALLY torqued!
Halmos, Rudin -- can be good stuff.
[deleted]
It's not a great start to begin with an introduction of time domain and frequency domain and then show unlabeled graphs of same.
Albert Michelson's mechanical Fourier analyzer/synthesizer: https://www.youtube.com/watch?v=NAsM30MAHLg
(Yes, that Michelson)
(Yes, that Michelson)
I think the concept of the basis of functions, a series of functions which you can combine to approximate any other function is something that engineers should be able to understand. Then you can see the time to frequency as a (very useful) application.
BTW, the visualization in the post as to how the transform works is awesome, and can also work with the function basis explanation instead of the frequency one. In fact, it might make even more sense! And the posterior mention of the cosine transform wouldn't need to be hand wavy about real and imaginary parts.
In any case, I've seen so many engineers insist in the time to frequency explanation that it must somehow be easier to understand for people. I just lament that the beauty of function spaces is lost in these explanations, as well as the underlying understanding of why Fourier transform is not only useful but deep.