Compressed sensing approaches for polynomial approximation of high-dimensional functions

arXiv1703.06987MaRDI QIDQ6284584FDOQ6284584

Ben Adcock, Clayton G. Webster, Simone Brugiapaglia

Publication date: 20 March 2017

Abstract: In recent years, the use of sparse recovery techniques in the approximation of high-dimensional functions has garnered increasing interest. In this work we present a survey of recent progress in this emerging topic. Our main focus is on the computation of polynomial approximations of high-dimensional functions on $d$-dimensional hypercubes. We show that smooth, multivariate functions possess expansions in orthogonal polynomial bases that are not only approximately sparse, but possess a particular type of structured sparsity defined by so-called lower sets. This structure can be exploited via the use of weighted $el{l}^1$ minimization techniques, and, as we demonstrate, doing so leads to sample complexity estimates that are at most logarithmically dependent on the dimension $d$. Hence the curse of dimensionality - the bane of high-dimensional approximation - is mitigated to a significant extent. We also discuss several practical issues, including unknown noise (due to truncation or numerical error), and highlight a number of open problems and challenges.

This page was built for publication: Compressed sensing approaches for polynomial approximation of high-dimensional functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284584)