[FoRK] Nearly Optimal Sparse Fourier Transform
sdw at lig.net
Sun Feb 26 02:06:33 PST 2012
Cool! But, if I understand the algorithm correctly, I'm kicking myself for not pursuing my intuition long ago.
My very old idea:
Since I knew that your cochlea sensed sound by sensing vibration in hairs of different lengths, I considered compressing sound
by modeling that vibration. A DFT in essence. My idea was to create bin cycles for different frequencies, then track incoming
signals over those cycles. Adding in decay and some fuzziness handling, the bins would tend to be zero anywhere the frequencies
didn't match consistently. Matching bins would have at least one positive peak, which could be encoded as an activation event
like your auditory nerves use or like a DFT (although I didn't fully understand FFT/DFT/DCTs that long ago). While I kept
thinking about it, I never implemented it.
Anyway, these new sparse DFT methods seem pretty similar to that idea. I want to see an actual implementation. For this kind
of thing, intuition can be a long way from a working implementation.
More information about the FoRK