Live data from Hacker News

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

nautil.us

101–105 of 105 posts

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

#101
post #80
post #77

The Shazam algorithm -- I don't want to be all cynical and dumpy because it's not like I remember exactly how it works either (it's proprietary, after all... and even the explanation I was given was not definitive) but one of my Music Information Retrieval professors once described his anecdotal knowledge of it. It was based on some features derived from FFT for sure but didn't seemed very concerned with note identif…

There is a paper [1] describing the algorithms used by Shazam. [1] http://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf

awesome I will give this a read for sure. Thanks!

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

#102
post #94

They really are a beautiful thing, it is unfortunate that most computer science majors don't get at least a basic introduction to signal processing as part of their standard curriculum. Especially because in my experience, the best way to understand a Fourier transform is to implement it in a program, feed in different signals, and wait for the light in your mind to go off. Images and audio signals provide a particul…

They don't? At University of Sydney every engineering degree does 2 years of maths and that includes Fourier Series.

Nope, I only learned about it because my cousin went to the same school and was doing his electrical engineering graduate degree at the time. He had a book on signal processing lying around and that's where I was introduced to it.

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

#103

There is also an extremely important property that would be worth an article of it's own. Namely the fact that pointwise multiplication of 2 fourier transformed functions is the same as convolution of the functions themselves. What does this mean in practice? Let's take a simple gaussian blur for images. A single output pixel is formed by overlapping the gaussian kernel on top of the image, multiplying then pointwise…

Do you have any write-up on the accelerometer data processing? I'd be interested. Thanks!

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

#104
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!

I liked your article, however, it is not so much the Fourier Transform itself that makes possible all these wonderful applications, but rather the Fast Fourier Transform, which you fail to mention even once.

The "naive" Fourier Transform has a pleasing mathematical simplicity and makes it very useful for deriving all sorts of theoretical properties for scientific analysis, but in practice it has a computational complexity of O(N^2), that would quickly make all those applications you name in your article utterly infeasible.

Instead, only with the discovery of the Fast Fourier Transform algorithm roughly halfway the 20th century[0], lowered the complexity to a very manageable O(N log N). And only then all these applications and properties of the Fourier Transform came within computational reach. Without the FFT, the Fourier Transform would mostly just be useful on paper for functional analysis and math proofs, things like that, but not in practice and we'd be missing out on all those MP3s, JPGs and speech recognition.

It's definitely not an overstatement when the WP article says: Fast Fourier transforms have been described as "the most important numerical algorithm[s] of our lifetime".

[0] or 1805, depending: https://en.wikipedia.org/wiki/Fast_fourier_transform "The basic ideas were popularized in 1965, but some FFTs had been previously known as early as 1805."

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

#105
post #46
post #20

Earlier quoted context omitted.

> This is actually the exact same number of numbers as in the time-domain series. In a way, it's twice as many, since they have both real and imaginary components.

Nope - the amount of numbers is in fact identical. The discrete Fourier transform has redundant information in bins above NFFT/2 (where NFFT is the size of the transform/number of samples in the signal) for purely real valued input. This means the "number of numbers" is the same - NFFT/2 bins of necessary complex values after transformation, versus NFFT real values in the original series.

Ah yeah, forgot about that. Thank you.
Post reply on HN