Recovering sparse Fourier signals, with application to system identification


Speaker(s): Holden Lee (Duke, Math)
The problem of recovering a sparse Fourier signal from samples comes up in signal processing, imaging, NMR spectroscopy, and machine learning. Two major challenges involve dealing with off-grid frequencies, and dealing with signals lacking separation between frequencies. Without a minimum separation condition, the problem of frequency recovery is exponentially ill-conditioned, but the signal can still be efficiently recovered in an "improper" manner using an appropriate filter. I will explain such an algorithm for sparse Fourier recovery, and the theory behind why it works - involving some clever analytic inequalities for Fourier-sparse signals. Finally, I will discuss recent work with Xue Chen on applying these ideas to system identification. Identification of a linear dynamical system from partial observations is a fundamental problem in control theory. A natural question is how to do so with statistical rates depending on the inherent dimensionality (or order) of the system, akin to the sparsity of a signal. We solve this question by casting system identification as a "multi-scale" sparse Fourier recovery problem.

Zoom link