A Sparse Multidimensional FFT for Real Positive Vectors
05/10/2016Publication 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