Computer Science Theory Seminar: Sparse Fourier transform in the continuous setting, by Xue Chen
November 13, 2019
4:15 PM - 5:05 PM
CalendarDownload iCal File
Xue Chen (Northwestern): Sparse Fourier transform in the continuous setting
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.
Nov 12, 2019
Nov 12, 2019