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

Abstract

This work proposes and analyzes a compressed sensing approach to polynomial approximation of complex-valued functions in high dimensions. Of particular interest is the 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 present an innovative weighted ${\ell }_1$ minimization procedure with a precise choice of weights, and a new iterative hard thresholding method, 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 in [5] to the general case of continuous 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 ${\ell }_1$ minimization strategy.

33 pages, 3 figures

References in corpus (2)

• Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies
• Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension

Cited by in corpus (26)

• Least Squares Polynomial Chaos Expansion: A Review of Sampling Strategies
• Sparse Polynomial Chaos Expansions via Compressed Sensing and D-optimal Design
• Compressed sensing with sparse corruptions: Fault-tolerant sparse collocation approximations
• On oracle-type local recovery guarantees in compressed sensing
• Generalization Bounds for Sparse Random Feature Expansions
• Approximating smooth, multivariate functions on irregular domains
• Multi-level Compressed Sensing Petrov-Galerkin discretization of high-dimensional parametric PDEs
• Improved recovery guarantees and sampling strategies for TV minimization in compressive imaging
• The gap between theory and practice in function approximation with deep neural networks
• Multivariate extensions of isotonic regression and total variation denoising via entire monotonicity and Hardy-Krause variation
• A mixed ${\ell }_1$ regularization approach for sparse simultaneous approximation of parameterized PDEs
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• Correcting for unknown errors in sparse high-dimensional function approximation
• Deep Neural Networks Are Effective At Learning High-Dimensional Hilbert-Valued Functions From Limited Data
• On the strong convergence of forward-backward splitting in reconstructing jointly sparse signals
• Gradient Descent-based D-optimal Design for the Least-Squares Polynomial Approximation
• Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing
• Robustness to unknown error in sparse regularization
• The greedy side of the LASSO: New algorithms for weighted sparse recovery via loss function-based orthogonal matching pursuit
• Approximation of Functions: Optimal Sampling and Complexity
• Model Calibration of the Liquid Mercury Spallation Target using Evolutionary Neural Networks and Sparse Polynomial Expansions
• Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension
• Near-optimal sampling strategies for multivariate function approximation on general domains
• Constructing efficient spatial discretizations of spans of multivariate Chebyshev polynomials
• Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements
• GenMod: A generative modeling approach for spectral representation of PDEs with random inputs