In recent years, a number of works have studied methods for computing the Fourier transform in sublinear time if the output is sparse. Most of these have focused on the discrete setting, even though in many applications the input signal is continuous and naive discretization significantly worsens the sparsity level. We present an algorithm for robustly computing sparse Fourier transforms in the continuous setting. Let , where x * has a k-sparse Fourier transform and g is an arbitrary noise term. Given sample access to x(t) for some duration T , we show how to find a k-Fourier-sparse reconstruction x (t) with The sample complexity is linear in k and logarithmic in the signal-to-noise ratio and the frequency resolution. Previous results with similar sample complexities could not tolerate an infinitesimal amount of i.i.d. Gaussian noise, and even algorithms with higher sample complexities increased the noise by a polynomial factor. We also give new results for how precisely the individual frequencies of x * can be recovered. Fourier Transform; Sparse Recovery; Superresolution; v i e 2πifit for some tones {(v i , f i )}. We consider the problem where we can sample some signal x(t) = x * (t) + g(t)
Price and Song REF proposed a way to define k-sparse Fourier transform problem in the continuous setting and also provided an algorithm which requires the frequency gap.
A Robust Sparse Fourier Transform in the Continuous Setting
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
Mathematics Computer Science