Open emd opened 7 years ago
Thanks!
The FFT uses a different frequency convention than the standard form of the DFT, which manifests either as a frequency shift, or a phase shift, or both.
Because this package gives a fast approximation of the DFT, I think sticking with the current form makes the most sense. It might be useful to add some documentation about this difference when it comes to the FFT, though, because it can be a bit confusing if you're not used to the convention used by the FFT.
In your implementation walkthrough, you show that your
nfft
implementation agrees with yourndft
implementation. However, you never show that either agree with the FFT in the limit of a uniform grid, and, having never considered the NFFT before, I figured this would be a natural place for me to start before I began using non-uniform grids. I am particularly interested in transforming measurements made on a non-uniform grid into Fourier space, so my discussion below will be focused on the adjoint transform.Using the below MWE, I find that, in the limit of a uniform grid, the
ndft_adjoint
implementation disagrees with the FFT:Making a simple modification to your
ndft_adjoint
code, as detailed below, and re-running the above MWE produces agreement with the FFT.I hope the commentary around my modifications is clear, but please let me know if more details would be helpful or if you have further questions.
Just as you test the equivalence of your
ndft
andnfft
implementations in your walkthrough, I've also verified the equivalence of yourndft_adjoint
andnfft_adjoint
implementations. Thus, the above phase-computation error also plaguesnfft_adjoint
. I've glanced through the Keiner, Kunis, & Potts paper, but I can't even pretend that I understand it, so I'm not sure if the fix fornfft_adjoint
is as simple as what I've suggested above forndft_adjoint
...Thanks for starting this package, and I look forward to seeing where it goes!