Visualizing the Discrete Fourier Transform | Hacker News Reader

Visualizing the Discrete Fourier Transform

blog.revolutionanalytics.com

68 pointsrndn18 comments

Rather than funny analogies about signals spinning on poles, I think it's relatively easy to understand what the DFT is with just two things that many people already know: 1) knowledge of the complex exponential definition of Fourier series [1], and 2) how to approximate integrals with the left rectangle rule [2].

Take your continuous signal and represent it with a Fourier series. Since the Fourier series is a linear decomposition into integer frequency sinusoids, the coefficients of the series tell you the amount of each frequency contained in the signal. The DFT gives you an approximation of these.

The coefficients of the Fourier series of a function are integrals. Approximate these integrals with a left Riemann sum. Integrals turn into sums ... sums turn into a linear system ... the linear system turns into a matrix ... bingobango there's the DFT matrix [3].

[1]: http://users.wpi.edu/~goulet/Matlab/overlap/efs.html

[2]: https://en.wikipedia.org/wiki/Riemann_sum#Left_Riemann_Sum

[3]: https://en.wikipedia.org/wiki/DFT_matrix

And to understand this easy explanation, simply get a degree in mathematics or engineering first, simple!

(I appreciate the post though, thanks)

Hence, my reason for prepending "relatively" before "easy" :) I admit the Fourier series part probably isn't standard knowledge. On the other hand, every student of a science-related field has (hopefully!!) at least taken calc one, so should be familiar with the rectangle rule for approximating integrals.

Hum wasn't taught in my calc 1 class. I know what DFT is and studied a lot more calc but I didn't get that until at least cal2 when we started working with integrals regularly.

We did, and yes, we learnt the thing you're mentioning. I however, had absolutely no idea what it was called anymore. But thanks for the links, I now remember.

Yup. I think it's not that hard to understand the continuous time fourier transform -- just imagine every signal ever can be expressed as an infinite integral of sinusoids of varying frequencies (the inverse fourier transform), and reverse that process to coax the fourier transform.

It is trivial to coax the DTFT and DFT derivations if one understands the CTFT.

I like the linear algebra interpretation, where the DFT is a basis change, and the only 'magic' is believing/proving that the Fourier basis is orthogonal. (It's an easy proof.)

I still don't understand how the FFT works though...

If you understand DFT, it should be very easy to understand FFT. It's the same thing but with an infinite-dimensional vector space. The fact that it's a vector space is the important thing. The infinite dimensionality is relatively a minor detail.

No that's not right. The FFT is not infinite dimensional. It's the same dimension as whatever length FFT you take. The FFT is just a set of algorithms for computing the DFT. In general they work by recursively decomposing an N-length DFT into shorter length DFT's.

The DTFT on the other hand is "infinite" dimensional in that it takes an infinite time series as input and outputs a continuous spectrum with period of 2pi.

Sorry, This is embarrassing, I must have not drank my coffee... Of course you are right.

I was talking about the O(n log n) algorithm that computes the DFT.

Yeah, see my other comment.

> I like the linear algebra interpretation, where the DFT is a basis change

Yea. Maybe a loose analogy would be transforming from RGB to HSV space - the difference in how we can interpret the numbers in one versus the other is what's great.

On a similar note, The Engineer Guy's walkthrough of Albert Michelson's Harmonic Analyzer gave me a much better understanding of Fourier analysis in general.

https://www.youtube.com/playlist?list=PL0INsTTU1k2UYO9Mck-i5...

Why not link to the original site? http://www.billconnelly.net/?p=276

Some admin should fix the link, the current article don't contribute anything important over the original.

I found this video to be an incredibly useful explanation of the Fourier Transform: https://www.youtube.com/watch?v=FjmwwDHT98c

I love the way they used color and plain English to describe that function. It would be awesome if a general app for this sort of color coded simple translation were available to help kids learn about mathematics. It'd have to be more inclusive for people with dichromacy and anamalous trichromacy, but there could be settings in the app to compensate for that.

Reply on news.ycombinator.com