Speaker: Mark Iwen (IMA)
Title: Interpolation with Sparsity Assumptions: From Syphilis Testing to Sparse Fourier Transforms
Abstract: I will discuss the application of group testing techniques to compressed sensing problems and sparse signal recovery. From this general framework I will narrow focus down to the specific problem of recovering a periodic function that is well approximated by the sum of a small number of sinusoids using as few function samples as possible. We will see that these considerations lead to sublinear-time Fourier algorithms capable of quickly recovering sparse superpositions using a smaller number of samples than required by straightforward application of the Nyquist/Shannon sampling theorem. Finally, we will conclude with a brief discussion of other compressed sensing applications to function learning/interpolation with sparsity assumptions.