A Sparse Multidimensional FFT for Real Positive Vectors

We present a sparse multidimensional FFT (sMFFT) randomized algorithm for positive real vectors. The algorithm works in any fixed dimension, requires an (almost)-optimal number of samples (O (R log (N))) and runs in O (R log (N)) complexity (where N is the total size of the vector in d dimensions and R is the number of nonzeros) which we claim is optimal (up to first order). It is stable to noise, exhibits an exponentially small probability of failure and is generalizable to general complex vectors.

For information on Reservoir’s technology related to this paper, visit Algorithms.