[FoRK] Nearly Optimal Sparse Fourier Transform

Stephen Williams 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 mailing list