Polynomial approximation via compressed sensing of high-dimensional functions on lower sets

This work proposes and analyzes a compressed sensing approach to polynomial approximation of complex-valued functions in high dimensions. In this context, the target function is often smooth and characterized by a rapidly decaying orthonormal expansion, whose most important terms are captured by a lower (or downward closed) set. Motivated by this fact, we present an innovative weighted ℓ₁-minimization procedure with a precise choice of weights for imposing the downward closed preference. Theoretical results reveal that our computational approaches possess a provably reduced sample complexity compared to existing compressed sensing techniques presented in the literature. In addition, the recovery of the corresponding best approximation using these methods is established through an improved bound for the restricted isometry property. Our analysis represents an extension of the approach for Hadamard matrices by J. Bourgain [An improved estimate in the restricted isometry problem, Lecture Notes in Math., vol. 216, Springer, 2014, pp. 65-70] to the general bounded orthonormal systems, quantifies the dependence of sample complexity on the successful recovery probability, and provides an estimate on the number of measurements with explicit constants. Numerical examples are provided to support the theoretical results and demonstrate the computational efficiency of the novel weighted ℓ₁-minimization strategy.