Compressed sensing approaches for polynomial approximation of high-dimensional functions
For researchers in high-dimensional approximation, this work provides a theoretical framework and practical guidance for using compressed sensing to overcome the curse of dimensionality.
This survey shows that smooth multivariate functions have structured sparsity in orthogonal polynomial bases, enabling weighted ℓ1 minimization to achieve sample complexity with only logarithmic dependence on dimension d, significantly mitigating the curse of dimensionality.
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 $\ell^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.