Foundations of compressed sensing for learning sparsity of high-dimensional problems

Seminar:

Foundations of compressed sensing for learning sparsity of high-dimensional problems
Tuesday, November 27, 2018
3:30PM – 5PM
POB 6.304

Clayton Webster

This tutorial will focus on compressed sensing approaches to sparse polynomial approximation of complex functions in high dimensions. Of particular interest to the UQ community is the parameterized PDE setting, where the target function is smooth, characterized by a rapidly decaying orthonormal expansion, whose most important terms are captured by a lower (or downward closed) set. By exploiting this fact, we will present and analyze several procedures for exactly reconstructing a set of (jointly) sparse vectors, from incomplete measurements. These include novel weighted $\ell_1$ minimization, improved iterative hard thresholding, mixed convex relaxations, as well as nonconvex penalties. Theoretical recovery guarantees will also be presented based on improved bounds for the restricted isometry property, as well as unified null space properties that encompass all currently proposed nonconvex minimizations. Numerical examples are provided to support the theoretical results and demonstrate the computational efficiency of the described compressed sensing methods.

Hosted by Karen Willcox