In this talk, we present a compressed sensing approach to polynomial approximation of complex-valued 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. Numerical examples are provided to support the theoretical results and demonstrate the computational efficiency of the new weighted minimization method.