We present the sparse multidimensional FFT (sMFFT) for positive real vectors with application to image processing. Our algorithm works in any fixed dimension, requires an (almost) – optimal number of samples and runs in complexity (to first order) for unknowns and nonzeros. It is stable to noise and exhibits an exponentially small probability of failure. Numerical results show sMFFT’s large quantitative and qualitative strengths as compared to minimization for Compressive Sensing as well as advantages in the context of image processing and change detection.
For information on Reservoir’s technology related to this paper, visit Algorithms.