I really think Prof. Osgood hits a sweet spot of not sweeping this under the carpet, and not becoming a course on functional/integration theory. I'm a postdoc in theoretical physics, and use these transforms regularly, and I have yet to find a more honest but still useful introduction (although I understand that real mathematicians cringe at my abuse of mathematics.. :)

edit: typo

For a concrete instance, he brings up the distributional viewpoint of Laurent Schwartz and talks about the class of decaying functions for which one can operate nicely. This was something I next saw primarily in mathematics texts, with very few engineering books caring to talk about this even though it is not very hard to introduce and gives significant clarity to the process IMHO.

Studying Prof. Osgood's stuff off Stanford SEE during my summer vacation at the end of high school was one of the best learning experiences I have had till date.

1. Fourier transform: unbounded real domain <-> unbounded real domain

2. Fourier series: bounded real domain <-> unbounded integer domain

3. Discrete Fourier transform (DFT): bounded integer domain <-> bounded integer domain

FFT is an algorithm for quick calculation of DFT, which is not Fourier series.

Together, these eight domains can be arranged on a commutative cube, all of whose edges have beautiful meanings: sampling, interpolation, etc. The fact that the cube is commutative gives a lot of theorems relating each transform and these operations.

No infinite series nor convergence problems here.

More precisely take a set of points, do a DFT, then make it infinite by making the rest of the terms 0. You now have the Fourier series of a periodic function that takes hits all of those points. Furthermore it is the "smallest" possible such periodic function in the L2 norm on periodic functions.

Not only that, it's the most interesting kind of linear algebra: it shows that, though every (finite-dimensional if you don't like choice) vector space has a basis—so that we can pretend that all n-dimensional vector spaces are the same for a fixed n—the simple act of changing that basis (which is all the DFT is doing) can have a profound impact.

It's not about whether the values are continuous or discrete, but instead about the domain over which the values are defined. Fourier series maps a periodic function over a continuous domain into a countably infinite number of coefficients.

There's probably an easier way to do it, but if you want to get faster playback (2x is about as fast as I can comprehend this lecturer at), this line seems to do the trick:

    document.getElementById("myElement").querySelector("video").playbackRate = 2

    document.getElementsByTagName('video')[0].playbackRate = 2;

    javascript:void%20function(){document.querySelector(%22video%22).playbackRate=parseFloat(prompt(%22Set%20the%20playback%20rate%22))}();

    javascript:void%20function(){document.querySelector(%22video%22).playbackRate=1.7}();

Of course, because of XSS-prevention rules, they won't help with iframe-embedded players. For that I guess you're gonna need a plugin.

I found this course and printed out the PDF of the lecture notes as I didn't have enough bandwidth for watching the videos. The lecture notes had a wealth of information about the idea of a Fourier Series expansion, it's connection to the Transform and the applications in diverse fields.

Prof. Osgood had great examples. In one such example he showed that the temperature of a ring must be a periodic function of time as the structure of the ring is periodic in space, and then went on to derive an equation for the temperature of the ring that was a Fourier Series.

It was from these notes that I learned a great deal about convolution too. The new website looks much better organized. I'd recommend every CS/EE student to at least watch the first few lectures once.

Out of curiosity, is this really true? Perhaps I misunderstand you, but I have always been under the impression that Fourier Transform was a fundamental building block covered extensively in all EE curriculum?

I took Computer Engineering with some classes shared between Comp. Eng. and EE students. I probably had 2 full-semester classes dedicated to signal processing and fourier transforms. Additionally I took a math course that covered Fourier and Laplace transforms.

As a personal anecdote: I ended up taking three courses: one on signals, one on systems, one on circuits (...and systems!). During those troubled uni years, trying to see if I can still remember the Fourier transform was my "am I too drunk?" benchmark. When I could no longer do it, I went home.

Similar to the person you're replying to, my education is in computer engineering rather than electrical engineering. I took the "signals and systems" course which was a treatment of Fourier series, Fourier transforms and convolutions. Since the final exam was open book, I did well by primarily being able to quickly look up the information relevant to each question on the exam. Convolutions did seem a little bit convoluted but the course didn't seem particularly soul-wrenching (compared to, say, the intro circuits course or the intro electronics course). Perhaps I was spared the soul-wrenching bits (e.g. I took a stats course instead of the course on random signals) or perhaps my university's electrical engineering department is subpar.

My Circuits and Systems professor, on the other hand, wasn't too interested in this. He obviously cared about us knowing the math, but insisted that he was teaching a Circuits class, not a Mathematics course. His course seemed a lot easier as a consequence. I was never that good at math. I learned it because you can't do engineering without it, but it has always been my weak spot.

(Edit: I don't mean it in the "how much is 12% out of 45 USD? zomg I suck at math" way, that's 5.4 USD, I'm not an idiot. I mean it in the "vector calculus made sense, I think, but I could never have made a career out of it as I did with writing software and designing electronic devices" kind of way.)

My Systems professor was smart but had long stopped caring about that course and his students, so I learned most of the material by myself. At the time, I thought he was an idiot, but I've come to understand him in time. His course wasn't too torturous, largely because I skipped most of the classes.

Most of my colleagues (particularly those in CompEng) didn't take separate courses on Signals and Systems though. They had a single, bigger Signals & Systems course, that was taught by a couple of hardcore professors, both well into their sixties and both of them very draconian. One of them also taught an introductory Electronic Devices and Circuits course that I took, so I knew him firsthand: he was a very good professor, but he was about as flexible as a chopstick. An year when less than 1/3rd of his students failed the final exam was a really good year.

Not in my experience.

As an undergrad MechE, I spent a lot of quality time with Fourier transforms in control theory, vibrations, solving pde's, and math classes. As a graduate CS student, the FFT got a lot of attention in algorithms (for the DFT), computer vision, and robotics (signals filtering) classes.

Doing this one now.

Funny - I did Fourier in Comp. Eng. - but it was jammed together with so many other things, I felt overwhelmed by all of it, I did enough to do decently on the exam, but I feel a lot of it was lost on me, and I forgot much of it.

Using fourier in most computer applications is very rare!

I'm excited to have a project I need to use it for - and weirdly stocked to be watching this video.

I love it when I have a reason to learn something awesome ...

It's only relevant for some application domains (and has no "pure" CS use case I can think of), so a basic idea what it does, as a single lecture in a maths course or so, is probably enough in many cases. If you go in an field that uses it, you hopefully learn it in more detail there (or go googling for resources like this...).

Why would it? Core CS deals primarily with discrete mathematics. Outside of a DSP or image processing course, there's little reason for a CS student to encounter the Fourier or other transforms.

https://www.youtube.com/watch?v=nfoudtpBV68

It's on youtube.

Since analog lines may not have the same frequency response when it comes to interference, the modem usually tests the analog lines at various frequencies, and only keeps the intervals who are good enough to transmit.

I wonder if the FFT is used for wifi, since wifi passes through an analog signal.

Although I'm not even sure of what I'm talking about is true or relates to fourier.

A good-spirited correction: anyone who knows enough to know this much generality knows that calling anything mathematical the "most generalised" version of a concept is begging to be corrected. Source: I do harmonic analysis on non-compact groups, and suspect that the folks over at the n-category café probably regard my kind of work as dangerously pedestrian (see, for example, https://golem.ph.utexas.edu/category/2010/11/integral_transf...).

That's interesting that you do harmonic analysis on non-compact groups; I've been meaning to learn more about that actually. I've been working on group synchronization problems related to the ideas in this paper (http://arxiv.org/pdf/1505.03840.pdf), which briefly mentions how one might extend the concept to non-compact groups, but doesn't elaborate further.

> I did qualify my statement with "arguably"

I always tell my students—and, though it's a joke, I think that it's more true than casual consideration might suggest—that the correct answer (though not one that they're allowed to use on tests!) to any question in mathematics is "it depends." The more elementary the question, the more profound it sounds that you can see angles from which different answers can be correct. (Of course, backing this up with actual profound re-interpretations is the hard part. :-) )

> That's interesting that you do harmonic analysis on non-compact groups; I've been meaning to learn more about that actually. I've been working on group synchronization problems related to the ideas in this paper (http://arxiv.org/pdf/1505.03840.pdf), which briefly mentions how one might extend the concept to non-compact groups, but doesn't elaborate further.

As a decidedly pure mathematician, that's outside my wheelhouse, although I did have the pleasure of having some of the applications explained to me by one of the authors of one of the papers on cryo-electron microscopy cited in the linked article. I'm afraid that the idea of embedding a non-compact group in a larger, compact group is foreign to my way of thinking about things, so (in case you were implicitly asking) unfortunately I can't shed any light there.

With a bit of calculation you conclude that if we want to analyze Z = X + Y, then the probability-density for Z alone must be h(z) = ∫ dx j(x, z - x); there are a couple ways to do this but my favorite is to use Z = X + Y as a schematic to write a Dirac δ-function j(x, y, z) = j(x, y) δ(z - x - y), then the standard "what is the probability-density for Z alone? integrate over both x and y!" rule comes into play. But you can also reason it out by hand, if you want.

Anyway, then you come up with this cool definition of independence; X and Y are independent if j(x, y) factors nicely into f(x) g(y); independent probabilities tend to multiply. So that's cool.

Now here's where the Fourier transform comes in; consider using a convention where we denote the Fourier transform and with the same function-name but using square brackets rather than parentheses for its application,

f[q] = ℱ{p → q} f(p) = ∫ dp exp(-i p q) f(p).

When we Fourier-transform h(z) for Z = X + Y we get:

h[a] = ∫ dz exp(-i a z) h(z) = ∫ dx dy exp(-i a (x + y)) j(x, y)

and if the two are independent random variables we find that h[a] = f[a] g[a]; the sum of independent random variables has a product of Fourier transforms precisely because the above sum takes the form of a convolution.

Taking a logarithm, we have that the χ(a) = log h[a] = log f[a] + log g[a] and any properties of the logarithm of the Fourier transform of the density function must be additive amongst independent random variables. And this gives the cumulants of the random variables: pseudo-linear expressions (linear in independent random variables f(X + Y) = f(X) + f(Y), with f(k X) = q(k) * f(X) for some fixed q) which characterize the different "moments" of the random variables in question. In fact if we look carefully at the definition h[a] = ∫ dz exp(-i a z) h(z) we see that the variable P = k Z, having distribution b(p) = h(p/k) / k, generates b[a] = h[k a].

Calculating the zeroth, χ(0) = log h(0) = log 1 = 0. No biggie. Continuing the Maclaurin expansion gives χ'(a) = h'(a)/h(a) and at a=0 that's -i E(Z). We knew that the expectation value was linear, so no surprise there. The next term is (-i)^2 [h''(a) h(a) - h'(a) h'(a)]/[h(a) h(a)] which works out to just E(Z^2) - E(Z)^2, the familiar expression for the variance; so variance is pseudolinear (in this case q(k) = k^2). The point is, then you can just go on. There are in fact infinitely many pseudolinear cumulants which scale like q(k) = k^n, coming from this Maclaurin series, with a pattern based in fact entirely on the pattern of derivatives that comes out of log(f(x)).

As a freebie you have a proof of the central limit theorem. Take N independent identically-distributed random variables with characteristic functions χ(a), call them each X_i, form their sum S = sum_i X_i / N, and from the properties we've already seen in this comment its characteristic function must be ψ(a) = N χ(a / N). Do the Maclaurin series to 2nd order and ignore the latter terms for large N; you get convergence to a parabola, which means that the Fourier transform of the probability density is... a Gaussian! And the inverse Fourier transform of that Gaussian is just another Gaussian, so for large N the result must be a normal random variable with mean μ and variance σ²/N, which of course is what they must be, because means are linear and variances are pseudolinear.

Something I've never seen rigorously explored: Cumulants appeared in my Master's work in condensed matter, where they at times seemed to have a mysterious tie to Feynman diagrams; that is, there seems to be some sort of analogy between how the Nth cumulant "subtracts out" all of the components of the Nth moment which are just products of the previous N-1 moments to obtain something "additive", and a Feynman diagram containing a vertex joining N particles. In particular Feynman diagrams for pairwise interactions seemed to be eerily similar to cumulant expansions which did not have any 3rd or higher moments. I confess I totally forgot this until I Googled today and saw a question on Math Overflow about it, but it was too sketchy to show me a real satisfying resolution of my mental curiosity. Similarly I remember seeing Young tableaux in some lecture notes on cumulants and then the day after I was working with Marcin Dukalski on some crazy approach he was taking in his thesis, and he spontaneously started talking about "hm, what do the Young tableaux look like for that?" and I was only able to help at all because of some limited understanding from the previous day's reading! So... there's definitely some mathematical resonances when you get to quantum theory.