Multiscale High-Dimensional Sparse Fourier Algorithms for Noisy Data

07/08/2019
by   Bosu Choi, et al.
0

We develop an efficient and robust high-dimensional sparse Fourier algorithm for noisy samples. Earlier in the paper "Multi-dimensional sublinear sparse Fourier algorithm" (2016), an efficient sparse Fourier algorithm with Θ(ds s) average-case runtime and Θ(ds) sampling complexity under certain assumptions was developed for signals that are s-sparse and bandlimited in the d-dimensional Fourier domain, i.e. there are at most s energetic frequencies and they are in [-N/2, N/2)^d∩Z^d. However, in practice the measurements of signals often contain noise, and in some cases may only be nearly sparse in the sense that they are well approximated by the best s Fourier modes. In this paper, we propose a multiscale sparse Fourier algorithm for noisy samples that proves to be both robust against noise and efficient.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset