A Sparse Multi-Dimensional Fast Fourier Transform with Stability to Noise in the Context of Image Processing and Change Detection

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 Reservoir Labs and runs in Reservoir Labs complexity (to first order) for  Reservoir Labsunknowns and Reservoir Labs 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 toReservoir Labs 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.