Live data from Hacker News

The Fourier Transform and its Applications

see.stanford.edu

41–50 of 60 posts

Re: The Fourier Transform and its Applications

#41

30 lectures on Fourier transforms and not one mention of the Fourier transform over compact groups? (Which is arguably the most generalized/abstract formulation of the concept of a Fourier transform.) A lot of recent research has been done on FFTs over groups like the rotation group and the symmetric group, and this work has lead to significant progress on problems that were previously considered intractable.

Do you know of a link that does host such mentions?

I've been using the book Engineering Applications of Noncommutative Harmonic Analysis by by Chirikjian and Kyatkin (https://www.amazon.com/dp/0849307481/ref=wl_it_dp_o_pC_nS_tt...). It's very well-written, and I believe an updated version of the book was recently released.

Re: The Fourier Transform and its Applications

#42
post #33

Earlier quoted context omitted.

the other somewhat confusing thing is that algorithms like discrete fourier transform/fft are actually fourier series.

There are three of them. 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.

you are missing the discrete time fourier transform, which is the dual of your point (2).

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.

Re: The Fourier Transform and its Applications

#43
post #2

In case this is useful to anyone else: 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

Thank you for sharing this! I can't watch a video at normal rate and if I find a video online I try to find it on Youtube to have the speed control. Now I don't need that!

Re: The Fourier Transform and its Applications

#44
post #2

In case this is useful to anyone else: 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; Not tested.

Did it not work?

Re: The Fourier Transform and its Applications

#45
post #33

Earlier quoted context omitted.

the other somewhat confusing thing is that algorithms like discrete fourier transform/fft are actually fourier series.

There are three of them. 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.

[deleted]

Re: The Fourier Transform and its Applications

#46
post #17

There is this hard question that is often glossed over in a first course on Fourier analysis: We learn that the Fourier transform of f(t) is an integral of exp(iwt)f(t) over all t. But when we look at a table of Fourier transform pairs, we find things like the Fourier transform of a constant function (is the Dirac delta). Integral does not converge? WTF? I really think Prof. Osgood hits a sweet spot of not sweeping t…

the other somewhat confusing thing is that algorithms like discrete fourier transform/fft are actually fourier series.

No, this is not what people mean when they say "Fourier series" which is something like "the Fourier series expansion of a periodic function".

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.

Re: The Fourier Transform and its Applications

#47
post #33

Earlier quoted context omitted.

the other somewhat confusing thing is that algorithms like discrete fourier transform/fft are actually fourier series.

There are three of them. 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.

The point being that by your definition of not, DFT is also NOT a Fourier transform. It's only a "transform" in that the two domains are similar (identical, mod complexity). That's quite confusing to engineers who only care about the results. Computationally, the first two are strictly speaking impossible, but effectively, your data come in being modeled as finite real-valued arrays that represent function values, (close enough to "bounded real domain") and need to come out as finite real-valued arrays, represented integer-indexed frequencies, and a DFT on your data will operationally give you that. This is much more realistically described as a discretized pseudo-fourier series.

Re: The Fourier Transform and its Applications

#48
One of the fun ones, and this may or may not be covered by the link, is generating the "cumulants" for probability density functions. The basic idea in (basic, continuous) probability theory is that you have these things called "random variables" X,Y,Z which now need to be thought of taking on values with various probabilities; and the way we do that is to use calculus (where the d- in "dx" is a special notation coming from the word "difference"; "dx" means "a tiny little change in x"). The basic idea is that there is some joint density j(x, y, z) such that the probability that simultaneously x 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.

Re: The Fourier Transform and its Applications

#49

Earlier quoted context omitted.

the other somewhat confusing thing is that algorithms like discrete fourier transform/fft are actually fourier series.

The discrete fourier transform is actually finite-dimensional linear algebra. No infinite series nor convergence problems here.

No, it really is a Fourier series.

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.

Re: The Fourier Transform and its Applications

#50

Earlier quoted context omitted.

The prof noted that it's almost all EE folks, with a few others, but didn't mention Comp Sci. Can anyone comment on why there were seemingly no Comp Sci people in this class? Wouldn't this be 'core' to Comp Sci?

>The prof noted that it's almost all EE folks, with a few others, but didn't mention Comp Sci. Can anyone comment on why there were seemingly no Comp Sci people in this class? Wouldn't this be 'core' to Comp Sci? 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.

I took a class on Scientific Computing (required) which went over a lot of core algorithms in various fields, including FFT. I wouldn't be surprised if a good portion of programs had something similar.
Post reply on HN