Non-uniform fast Fourier transform (NUFFT)

[jmontalt]

Describe the feature and the current behavior/state.
I was wondering if TensorFlow Addons might be a good home for a non-uniform fast Fourier transform (NUFFT) operator. This is a special type of fast Fourier transform that can be used for signals that are sampled non-uniformly (i.e. at points not lying in a Cartesian grid).

Although it is much less common than its uniform/Cartesian counterpart (the FFT, implemented in core TensorFlow), the operator is certainly useful for some scientific communities (e.g. medical imaging, astrophysics).

Relevant information

• Are you willing to contribute it (yes/no): Yes
  If you wish to contribute, then read the requirements for new contributions in CONTRIBUTING.md
• Are you willing to maintain it going forward? (yes/no): Yes
• Is there a relevant academic paper? (if so, where): Yes, here. This is the paper for the particular algorithm I propose to incorporate in TF addons, but there are several other papers describing other NUFFT algorithms.
• Does the relavent academic paper exceed 50 citations? (yes/no): Yes
• Is there already an implementation in another framework? (if so, where): Yes. Here is the original C implementation (plus wrappers for other languages). Here is an existing TensorFlow port (which I maintain).
• Was it part of tf.contrib? (if so, where): No.

Which API type would this fall under (layer, metric, optimizer, etc.)
I'm not sure any of the existing submodules is appropriate. The best home might be a new signal submodule that mirrors the one in core TensorFlow.

Who will benefit with this feature?
Scientific communities including medical imaging (MRI, CT) and astrophysics.

Any other info.

• The proposed operator is complex and involves a large amount of C++/CUDA code (you can have a look here to get an idea). It could increase the size of TF addons wheels by a few MB.
• The proposed inclusion would support CPU and GPU natively, but I do not have a pure Python implementation nor the bandwidth to write one anytime soon.
• The CPU implementation depends on FFTW, released under GNU GPL. I'm not sure if there could be any licensing issues with this.
• I'd like to understand whether there is any interest in having this in TF addons so I can plan accordingly, but if there is it will probably take a few months until a PR is ready (the current op seems to be working generally well and very efficiently, but there are still some rough edges).

[bhack]

Thanks you for the proposal but we don't have the bandwidth to maintain the overhead of large custom ops.

I suggest to reopen the same issue in the main TF repo.

[jmontalt]

To be clear, I'd be happy to help maintain this!

[bhack]

I understand, nothing personal, but the condeowners stats are not sponsoring the decision of maintaining large c++/cuda components.
Generally we lost codeowners after few months. So it is ok for relative small components but it is hard for a large codebase with custom ops.

The CPU implementation depends on FFTW, released under GNU GPL. I'm not sure if there could be any licensing issues with this.

I think this is a problem here but also for the main TF repo /cc @yarri-oss

[jmontalt]

I understand. Sorry to hear you haven't had a better experience with codeowners.

Core TensorFlow has previously shown limited interest in the feature, which is understandable since only a small subset of the community would have a use for it.

For now it seems it will need to stay in its own package. For anyone reading this who is interested, there's a fully functional NUFFT implementation for TensorFlow here.

[bhack]

/cc @seanpmorgan