I'm confused about this new sparse FFT ...
First, the Goertzel algo is related to a digital filter. It's good when you know what frequencies you're looking for, and there aren't too many of them. For instance recognizing the small number of frequencies phones use to encode the buttons on the keypad (do they still use this technique?).
The sparse FFT referenced seems to require, as with Goertzel, that you know the frequencies you're looking for. If that's true it's not immediately obvious when you'd use either one. Perhaps the sparse FFT is for when you've got a small range of freq's but are interested in anything within that range (unlike phone pad)? But it didn't sound that way in the brief description.
One thing that confuses me - I thought there were FFT algos optimized for sparse frequency sets, when you don't know which ones you're looking for. I don't find anything on the net about that type (didn't look too hard).
The other confusion - I'm quite sure there are FFT's for sparse data sets - i.e., in the time domain. (Again, a little googling didn't turn up anything). In this case you still want to analyze a full range of frequencies - they're not "sparse" - but the incoming data has lots of zeroes.
So there seem to be four types (at least) which could be called "sparse":
1 - few frequencies, and you know what they are
2 - limited, known frequency band, but within that you want all of them
3 - few / limited frequencies, but you don't know what they are
4 - all frequencies, but few time domain points - that is, most of the time domain is zero's
It seems that the sparse FFT - which Raistlin ref'd - is either type 1 or 2. And, it's common enough that I don't easily find stuff on the net about the others. Wouldn't be surprised if they're called something different today.
Raistlin, I believe, is interested in pulsars. This isn't a case 1. True, you can be sure they're not going faster than (not sure what the limit is - 1000 hz?) nor slower than a certain frequency (not sure of that either - a few seconds per revolution?). But within that frequency band all possibilities exist. It's not quantized, like phone keypad signals. So Goertzel, at least, doesn't seem right. Maybe that's what this "sparse FFT" is for?
But there are two things you can do with pulsars. 1) once you've found it, analyze its frequency - that ought to be easy. 2) comb through a lot of observational data covering broad segment of sky, looking for regularly repeating signals. The first is what I've been mostly thinking about but the second may be the real job in pulsar hunting. And whether the "sparse" concept applies to it at all, I don't know.
As I said I'm confused! But I hope this might help clarify some of the issues involved, for further intense googling efforts by somebody :P
