Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

nautil.us

Post reply on HN
Print view View original

21–30 of 105 posts

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#21

Post by exg »

pistle wrote: post #12
munificent wrote: post #9

Earlier quoted context omitted.

OK, since you asked: > The sound wave produced by a piano note is a simple sine wave. No, it's not. A piano note is a complicated stack of overtones (some of which are harmonic and some of which aren't) and transients. If it was just a sine wave, it would sound like a sine wave and not like a piano. This is part of why things like Shazam are so difficult: musical notes aren't just a single frequency in the FFT, they…

I love the FFT even more than you and enjoyed that it is getting lauded, but would have found more algorithmic details even more interesting. Breaking down DFT, etc. and then showing the performance magic of FFT is a great way to approach discussion of many issues in problem analysis and algorithm design. So, Nice enough article for slipping into the topic - now give me more! harder! faster!

Sparse fast Fourier transform is even more "magical" than fast Fourier transform (FFT). If you assume that the discrete Fourier transform (DFT) has only k non zero coefficients, then, there exists an algorithm to compute it in O(k log(n)). That's right, you do not have to see the entire signal to compute the DFT, which is pretty awesome.

If you are interested, see http://groups.csail.mit.edu/netmit/sFFT/ .

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#22

Post by itengelhardt »

I like how you make it sound so incredibly easy - especially thinking back to how much I struggled with the math behind this :-) (To be very clear: There's nothing wrong with explaining things in a simple way and leaving out the scary parts)

Great post.

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#23

Post by tobr »

munificent wrote: post #9
aatish wrote: post #3

Hi Hacker News - I'm the author of the piece, also on twitter @aatishb. Look forward to hearing your thoughts. I encourage you to share your thoughts and insights with other readers by leaving a comment on the post, particularly if you know of other interesting applications about the Fourier transform. Cheers!

OK, since you asked: > The sound wave produced by a piano note is a simple sine wave. No, it's not. A piano note is a complicated stack of overtones (some of which are harmonic and some of which aren't) and transients. If it was just a sine wave, it would sound like a sine wave and not like a piano. This is part of why things like Shazam are so difficult: musical notes aren't just a single frequency in the FFT, they…

>> The sound wave produced by a piano note is a simple sine wave.

> No, it's not. A piano note is a complicated stack of overtones (some of which are harmonic and some of which aren't) and transients. If it was just a sine wave, it would sound like a sine wave and not like a piano.

This is really such a fundamental* aspect of frequencies and sound, it should have been the starting point of the article. "Look how noisy and squiggly this wave is, but with FFT we can see that it really only consists of waves at multiples of the same frequency".

* no pun intended

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#24

Post by nilkn »

> You could just tell them a handful of numbers—the sizes of the different circles in the picture above.

Maybe I'm crazy and just missing something, but this feels a little too good to be true. This would put the set of smooth curves in 1-1 correspondence with the set of finite sets (since each curve is being specified completely by a finite set of numbers). But the set of finite sets is countably infinite since it's a countable union (this may require the axiom of choice) and the set of smooth curves is uncountably infinite, a contradiction.

(Disclaimer: I know nothing about Fourier analysis.)

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#26

Post by kevin_rubyhouse »

Coincidentally, I just had a talk with one of our principle developers about Fourier transforms. He's an audio expert and was trying to explain re-sampling and aliasing to me. I understand the high level steps, but the math is all a blur to me. Recently I've been trying to become much stronger in math, as I eventually want to study aerodynamics and astrophysics. So I've been studying calculus (textbook) and dynamics (edx) lately.

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#27

Post by andrewflnr »

nilkn wrote: post #24

> You could just tell them a handful of numbers—the sizes of the different circles in the picture above. Maybe I'm crazy and just missing something, but this feels a little too good to be true. This would put the set of smooth curves in 1-1 correspondence with the set of finite sets (since each curve is being specified completely by a finite set of numbers). But the set of finite sets is countably infinite since it's…

I don't know much more about Fourier analysis than you, but theoretically it's an infinite series. So to describe an arbitrary smooth curve, you need a potentially infinite number of circles (or sin terms). I'm not sure if it's a countably infinite series or not. I think in principle you could have a component for every number in the real line.

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#29

Post by Yen »

nilkn wrote: post #24

> You could just tell them a handful of numbers—the sizes of the different circles in the picture above. Maybe I'm crazy and just missing something, but this feels a little too good to be true. This would put the set of smooth curves in 1-1 correspondence with the set of finite sets (since each curve is being specified completely by a finite set of numbers). But the set of finite sets is countably infinite since it's…

It's not actually a finite set of numbers - a continuous Fourier transform would have an infinite number of amplitudes, for every possible frequency.

However, you can very closely approximate most curves with a relatively small number of amplitudes.

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#30

Post by aatish »

nilkn wrote: post #24

> You could just tell them a handful of numbers—the sizes of the different circles in the picture above. Maybe I'm crazy and just missing something, but this feels a little too good to be true. This would put the set of smooth curves in 1-1 correspondence with the set of finite sets (since each curve is being specified completely by a finite set of numbers). But the set of finite sets is countably infinite since it's…

In the article I described the discrete fourier transform, but there is a continuous version, where a signal is represented by an infinite sum (really an integral) of component frequencies. This is the version that is more generally useful. Here's a great animation by LucasVB of the continuous fourier transform in action: http://upload.wikimedia.org/wikipedia/commons/a/a3/Continuou...
Post reply on HN