A Sparse Multi-Dimensional Fast Fourier Transform with Stability to Noise in the Context of Image Processing and Change Detection
Pierre-David Letourneau, M. Harper Langston, Richard Lethin
Publication Source: 2016 IEEE High Performance Extreme Computing Conference (HPEC '16), Waltham, MA, USA.
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.