Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements

Abstract

We consider the sparse polynomial approximation of a multivariate function on a tensor product domain from samples of both the function and its gradient. When only function samples are prescribed, weighted ${\ell }^1$ minimization has recently been shown to be an effective procedure for computing such approximations. We extend this work to the gradient-augmented case. Our main results show that for the same asymptotic sample complexity, gradient-augmented measurements achieve an approximation error bound in a stronger Sobolev norm, as opposed to the $L^2$-norm in the unaugmented case. For Chebyshev and Legendre polynomial approximations, this sample complexity estimate is algebraic in the sparsity $s$ and at most logarithmic in the dimension $d$, thus mitigating the curse of dimensionality to a substantial extent. We also present several experiments numerically illustrating the benefits of gradient information over an equivalent number of function samples only.

References in corpus (5)

• Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies
• Least Squares Polynomial Chaos Expansion: A Review of Sampling Strategies
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Compressed Sensing and Parallel Acquisition
• Correcting for unknown errors in sparse high-dimensional function approximation