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. Moreover, the recovery of the correspondingbest approximation using our methods is established through an improved bound for therestricted isometry property. In addition, we will also present a new theory revealing that nonconvex minimizations are at least as good as $\ell_1$ minimization in exact recovery of sparsesignals. These theoretical recovery guarantees are developed through a unified null space property based-condition that encompasses allcurrently proposed nonconvex functionals in literature. Numerical examples are provided to support the theoretical results and demonstrate the computational efficiency of our new weighted approach, as well as nonconvex minimizations.