[geokon]

On thing that is often overlooked but should be emphasized is that the considered frequencies are fixed values while the phase shifts are continuous values. This creates tons of downstream problems

If your underlying signal is at frequency that is not a harmonic of the sampling length, then you get "ringing" and it's completely unclear how to deal with it (something something Bessel functions)

Actually using DFTs is a nightmare ..

- If I have several dominant frequencies (not multiples of the sampling rate) and I want to know them precisely, it's unclear how I can do that with an FFT

- If I know the frequency a priori and just want to know the phase shift.. also unclear

- If I have missing values.. how do i fill the gaps to distort the resulting spectrum as little as possible?

- If I have samples that are not equally spaced, how am I supposed to deal with that?

- If my measurements have errors, how do I propagate errors through the FFT to my results?

So outside of audio where you control the fixed sample rate and the frequencies are all much lower than the sample rate... it's really hard to use. I tried to use it for a research project and while the results looked cool.. I just wasn't able to backup my math in a convincing way (though it's been a few years so I should try again with ChatGPT's hand-holding)

I recommend people poke around this webpage to get a taste of what a complicated scary monster you're dealing with

https://ccrma.stanford.edu/~jos/sasp/sasp.html

[hasley]

FFT/DFT is not precise if you do not have the exact harmonic in you signal. If you are also (or only) interested in phases you might use a maximum likelihood estimator (which brings other problems though).

And as the previous answer said: compressed sensing (or compressive sensing) can help as well for some non-standard cases.

[geokon]

Do you have any good reference for compressed sensing?

The high level description on wikipedia seems very compelling.. And would you say it'd be a huge task to really grok it?

[ghtbircshotbe]

Article by Terrence Tao: https://terrytao.wordpress.com/2007/04/13/compressed-sensing...

Paper by Stan Osher et al: https://arxiv.org/abs/1104.0262

[adinisom]

A while back I looked at matching pursuit. At first it seemed very complicated, but after staring at it a bit realized it's simple.

- Start with a list of basis functions and your signal.

- Go through the list and find the basis function that best correlates with the signal. This gives you a basis function and a coefficient.

- Subtract out the basis function (scaled by the coefficient) from your signal, and then repeat with this new residual signal.

The Fourier transform is similar using sine wave basis functions.

The key that makes this work in situations where the Nyquist theorem says we don't have a high enough sampling rate is ensuring our sampling (possibly random) is un-correlated with the basis functions and our basis functions are good approximations for the signal. That lowers the likelihood that our basis functions correlating well with our samples is by chance and raises likelihood it correlates well with the actual signal.

[dsego]

You can use single bin DFTs and not FFTs? Basically use precomputed twiddles for a specific frequency. FFT is only fast because it reuses operation across multiple frequencies, but if you need a specific frequency instead of the whole spectrum, then a single-bin DFT makese sense, right?

https://github.com/dsego/strobe-tuner/blob/main/core/dft.odi...

[NL807]

Somewhat related field, compressive sensing, attempts to answer some of those questions (particularly missing data, uneven sampling and errors) using a L1 minimisation technique.

[geokon]

Can you recommend where to learn more about it? It looks like what I should be looking at.. hopefully not a rabbit hole :))

[NL807]

Here is a good lecture on this subject:

https://www.youtube.com/watch?v=rt5mMEmZHfs

[geokon]

That was actually fantastic. The professor is quite goofy, but he really goes over everything from first principles and goes through a real example - constructing a solution without any cheating :))

I was a bit bummed out there weren't a lot of Compressed Sensing libraries around, but it seems you just need a "convex optimization" routine (aka linear programming). And these seem to exist in every language

I'll try to play around with this! Thank you so much

[NL807]

It's a fascinating topic and i'm still trying to get my head around some of the concepts.

Have fun on your discovery journey.

[geokon]

Are there any gotchas you've come across?

From the video tutorial is seems relatively straightforward. I guess the basis selection is a fundamental issue that will be problem-specific.

I will have to try it with some concrete examples. The first question I have is, will it still work if you have a lot of high frequency noise? In the cases I'm thinking either there is measurement noise or just other jitter. So while the lower frequencies are sparse but I guess the higher frequencies not so much. I can't bandpass the data b/c it's got lots of holes or it's irregularly spaced.

Maybe it'll still work though!