Nov 13 2019

Computer Science Theory Seminar: Sparse Fourier transform in the continuous setting, by Xue Chen

November 13, 2019

4:15 PM - 5:05 PM


1325 SEO


Chicago, IL

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.

Please click here to make changes to, or delete, this seminar announcement.


Will Perkins

Date posted

Nov 12, 2019

Date updated

Nov 12, 2019


Xue Chen | (Northwestern)