A sparse multidimensional FFT for real positive vectors

Pierre-David Letourneau, Harper Langston, Benoit Meister +1

We present a sparse multidimensional FFT (sMFFT) randomized algorithm for real positive vectors. The algorithm works in any fixed dimension, requires (O(R log(R) log(N)) ) samples…