PIMS- SFU CS Seminar: Clayton Webster

In this talk, we present a compressed sensing approach to sparse polynomial approximation via convex and non-convex optimization of functions in high dimensions. Of particular interest 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 develop a novel weighted minimization procedure with a precise choice of weights, and a modification of the iterative hard thresholding method, for imposing the downward closed preference. We will also present theoretical results that reveal our new computational approaches possess a provably reduced sample complexity compared to existing compressed sensing, least squares, and interpolation techniques. In addition, the recovery of the corresponding best approximation using our methods is established through an improved bound for the restricted isometry property. In addition, we will also present a new theory for compressed sensing that reveals that nonconvex minimizations are at least as good as $\ell_1$ minimization in exact recovery of sparse signals. Our theoretical recovery guarantees are developed through a unified null space property based-condition that encompasses all currently proposed nonconvex functionals in literature. Several nonconvex functionals will be explored and the specific conditions in order to guarantee improved recovery will be given. Numerical examples are provided to support the theoretical results and demonstrate the computational efficiency of the new weighted convex minimization method and the computational efficiency of nonconvex minimizations.