Computer Science Theory Seminar
Xue Chen
Northwestern
Sparse Fourier transform in the continuous setting
Abstract: The Fourier transform is a ubiquitous computational tool in processing a variety of signals, including audio, image, and video. In many practical applications, the main reason for using the Fourier transform is that the transformed signal is approximately sparse, which exhibits structures that could be exploited to speed up the computation. While this has been well studied in the discrete setting (e.g., the Goldreich and Levin algorithm and Hassanieh et al.), it is still poorly understood in the more realistic continuous setting.
We consider the problem of reconstructing a continuous Fourier-sparse signal from noisy samples, where the sampling is done over some continuous interval [0,T] and the frequencies can be arbitrary and ``off-grid''. Previous methods for this problem required the gap between the frequencies to be at least 1/T, the threshold required to robustly identify individual frequencies. In this talk, we show an efficient framework that avoids the need for a frequency gap to interpolate the signal. Moreover, we discuss its implications on the more general problem --- reconstructing continuous signals with arbitrary Fourier structures such as narrow-band and multi-band.
Based on recent papers with Daniel Kane, Eric Price, and Zhao Song.
Wednesday November 13, 2019 at 4:15 PM in 1325 SEO