  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.
