Implement NNFFT

[tknopp]

I added the NNFFT in AbstractNFFTs but actually NFFT.jl is missing an implementation. So this is the feature request issue.

[YichengDWu]

Any hints on how to implement it?

[tknopp]

Sure. The question is if you have some experience with the NFFT, which would be necessary to understand the details. Reading https://arxiv.org/abs/2208.00049 would be the first step.

The NNFFT is then described in https://www-user.tu-chemnitz.de/~potts/paper/ndft.pdf section 1.3.

On a high level the NFFT can be written as a product of three matrices BFD. The NNFFT is can be expressed as BQFHD where the H is also a convolution-like matrix and Q is a diagonal correction matrix. So in principle it should be possible to reuse most of the code. In practice, however, I expect this to be quite tedious work since the functions in https://github.com/JuliaMath/NFFT.jl/blob/master/src/convolution.jl and need to be decoupled a little bit from the NFFTPlan. In order to do so, one might need to group certain parts of the NFFTPlan into structs, that capture all the parameters and temporary vectors, that are needed for a certain operation.