Lecture by Yaniv Plan, 2019 Andr茅-Aisenstadt Prize Recipient
Title: The role of random models in compressive sensing and matrix completion
Abstract: Random models lead to a precise and comprehensive theory of compressive sensing and matrix completion. The number of random linear measurements needed to recover a sparse signal, or a low-rank matrix, or, more generally, a structured signal, are now well understood. Indeed, this boils down to a question in random matrix theory: How well conditioned is a random matrix restricted to a fixed subset of R^n? We discuss recent work addressing this question in the sub-Gaussian case. Nevertheless, a practitioner with a fixed data set will wonder: Can they apply theory based on randomness? Is there any hope to get the same guarantees? We discuss these questions in compressive sensing and matrix completion, which, surprisingly, seem to have divergent answers.