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 (9)

• A non-adapted sparse approximation of PDEs with stochastic inputs
• Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies
• A weighted L1-minimization approach for sparse polynomial chaos expansions
• On Polynomial Chaos Expansion via Gradient-enhanced ${\ell }_1$-minimization
• Stochastic collocation on unstructured multivariate meshes
• Iterative Hard Thresholding for Weighted Sparse Approximation
• Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients
• Infinite-dimensional compressed sensing and function interpolation
• Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension

Cited by in corpus (28)

• 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
• 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
• Multi-level Compressed Sensing Petrov-Galerkin discretization of high-dimensional parametric PDEs
• 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
• Infinite-dimensional ${\ell }^1$ minimization and function approximation from pointwise data
• 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
• Infinite-dimensional compressed sensing and function interpolation
• Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing
• Gradient Descent-based D-optimal Design for the Least-Squares Polynomial Approximation
• On the strong convergence of forward-backward splitting in reconstructing jointly sparse signals
• 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
• Near-optimal sampling strategies for multivariate function approximation on general domains
• 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
• Constructing efficient spatial discretizations of spans of multivariate Chebyshev polynomials
• GenMod: A generative modeling approach for spectral representation of PDEs with random inputs
• Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements