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

Re:Fourier Transforms – The Math Trick Behind MP3s, JPEGs, a... by pistle on Wednesday November 06, 2013 @01:52PM (#6684577)

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!

[ Parent | on HN ]

Re:Fourier Transforms – The Math Trick Behind MP3s, JPEGs, a... by exg on Wednesday November 06, 2013 @02:13PM (#6684759)

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/ .

[ Parent | on HN ]

Re:Fourier Transforms – The Math Trick Behind MP3s, JPEGs, a... by susi22 on Wednesday November 06, 2013 @03:06PM (#6685107)

I work in this field (though I'm none of the authors). If anybody has any questions about the sFFT, let me know.

[ Parent | on HN ]