View More Publications

A Sparse Multidimensional FFT for Real Positive Vectors

Pierre-David Letourneau, Harper Langston, Benoit Meister, Richard Lethin
05/10/2016
Publication Source: arXiv:1604.06682 [cs.DS]

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.
Google Scholar    Article