First, many thanks for your amazing posts https://jakevdp.github.io/blog/2015/06/13/lomb-scargle-in-python/ and http://jakevdp.github.io/blog/2017/03/30/practical-lomb-scargle/ , and your contributions to a number of libraries - this is all super useful for people like me who want to learn about non uniform FFTs and very helpful materials together with other online resources.
This issue is summarizing some of the understanding I got after a bit of time reading online and thinking about the different forms non uniform fft comes in. I hope I did not misunderstand too much, I am not a specialist of the topic. I wonder if having a post about these questions and clarifying them would be useful. I think you are much more experienced than me on the topic, I am just a n00b on these questions, so I would like to discuss a bit with you here first to check I understand things correctly, and if you want to write a post about these points that would be amazing and would probably help many other people, or if you do not have the time / interest I will try to find time to write a post on my own gihtub.io site some day, to help the "future me" if I have to come back to these questions later, and possibly other people out there :) .
missing data on a regular grid vs truly non uniform FFT
First (that may seem obvious to you, but it took me a bit of time to understand it), having a problem with 1) missing data on a truly regular grid, vs 2) truly non uniform FFT, are two quite different problems, right? I.e. in 1), if I understand well, it is enough to take the usual FFT setting the missing values to 0 and scaling the resulting FFT spectrum to reproduce the exact summation formula. Applying a "true" non uniform FFT is only needed when the sampling coordinates are truly non uniform, ie do not fall on a regular grid (possibly with some missing points). This is more or less what should be illustrated now by https://github.com/gauteh/concepts/blob/main/Waves-Non-uniform_frequency_spectra_and_moments.ipynb . Of course, applying a "FFT on regular grid with zeroed missing points" approach means that the Nyquist criterion still applies in this case. This should be the case you have @gauteh . The usual tricks, i.e. averaging (Welch methods), windowing, etc, should apply out of the box.
truly non regular grid
The other case is for the truly non regular grid, as you describe in your posts. Your posts make this very clear to me what the main take home message are (in particular, the Nyquist criterion does not apply etc).
However, there is still one thing that confuses / puzzles me: the wide variety of methods available, and what the tradeoffs are between them. I can wrap my head quite well around the different "subvariants" of FFT algorithms I have heard of, but not around the different variants of ways to get a non uniform fft.
For example, it looks to me like the methods implemented by { https://github.com/flatironinstitute/finufft , https://github.com/flatironinstitute/cufinufft (just a cuda version of the same algorithm), vs. { https://github.com/jyhmiinlin/pynufft } vs { https://github.com/PrincetonUniversity/FastTemplatePeriodogram }, vs. { https://github.com/astropy/astropy/blob/main/astropy/timeseries/periodograms/lombscargle/implementations/fast_impl.py } and related, and as described in a variety of papers (https://arxiv.org/pdf/2101.12348.pdf , https://www.researchgate.net/publication/258561369_Fast_calculation_of_the_Lomb-Scargle_periodogram_using_nonequispaced_fast_Fourier_transforms , https://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/PIRODDI1/NUFT/node7.html , among many others), are relying on quite different properties of the transform to be calculated / accelerated. Is this correct? Any hope you could explain to us at a "high level" the working of these different methods, and what their strengths and weaknesses are? Or are they all more or less "as powerful", and we users do not need to care about exactly which N.log(N) method is used under the hood by a library or another?
First, many thanks for your amazing posts https://jakevdp.github.io/blog/2015/06/13/lomb-scargle-in-python/ and http://jakevdp.github.io/blog/2017/03/30/practical-lomb-scargle/ , and your contributions to a number of libraries - this is all super useful for people like me who want to learn about non uniform FFTs and very helpful materials together with other online resources.
This issue is summarizing some of the understanding I got after a bit of time reading online and thinking about the different forms non uniform fft comes in. I hope I did not misunderstand too much, I am not a specialist of the topic. I wonder if having a post about these questions and clarifying them would be useful. I think you are much more experienced than me on the topic, I am just a n00b on these questions, so I would like to discuss a bit with you here first to check I understand things correctly, and if you want to write a post about these points that would be amazing and would probably help many other people, or if you do not have the time / interest I will try to find time to write a post on my own gihtub.io site some day, to help the "future me" if I have to come back to these questions later, and possibly other people out there :) .
missing data on a regular grid vs truly non uniform FFT
First (that may seem obvious to you, but it took me a bit of time to understand it), having a problem with 1) missing data on a truly regular grid, vs 2) truly non uniform FFT, are two quite different problems, right? I.e. in 1), if I understand well, it is enough to take the usual FFT setting the missing values to 0 and scaling the resulting FFT spectrum to reproduce the exact summation formula. Applying a "true" non uniform FFT is only needed when the sampling coordinates are truly non uniform, ie do not fall on a regular grid (possibly with some missing points). This is more or less what should be illustrated now by https://github.com/gauteh/concepts/blob/main/Waves-Non-uniform_frequency_spectra_and_moments.ipynb . Of course, applying a "FFT on regular grid with zeroed missing points" approach means that the Nyquist criterion still applies in this case. This should be the case you have @gauteh . The usual tricks, i.e. averaging (Welch methods), windowing, etc, should apply out of the box.
truly non regular grid
The other case is for the truly non regular grid, as you describe in your posts. Your posts make this very clear to me what the main take home message are (in particular, the Nyquist criterion does not apply etc).
However, there is still one thing that confuses / puzzles me: the wide variety of methods available, and what the tradeoffs are between them. I can wrap my head quite well around the different "subvariants" of FFT algorithms I have heard of, but not around the different variants of ways to get a non uniform fft.
For example, it looks to me like the methods implemented by { https://github.com/flatironinstitute/finufft , https://github.com/flatironinstitute/cufinufft (just a cuda version of the same algorithm), vs. { https://github.com/jyhmiinlin/pynufft } vs { https://github.com/PrincetonUniversity/FastTemplatePeriodogram }, vs. { https://github.com/astropy/astropy/blob/main/astropy/timeseries/periodograms/lombscargle/implementations/fast_impl.py } and related, and as described in a variety of papers (https://arxiv.org/pdf/2101.12348.pdf , https://www.researchgate.net/publication/258561369_Fast_calculation_of_the_Lomb-Scargle_periodogram_using_nonequispaced_fast_Fourier_transforms , https://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/PIRODDI1/NUFT/node7.html , among many others), are relying on quite different properties of the transform to be calculated / accelerated. Is this correct? Any hope you could explain to us at a "high level" the working of these different methods, and what their strengths and weaknesses are? Or are they all more or less "as powerful", and we users do not need to care about exactly which N.log(N) method is used under the hood by a library or another?