We will consider the problem of computing sparse polynomial approximations of functions defined over high-dimensional domains from pointwise samples, primarily motivated by the uncertainty quantification of PDEs with random inputs. In this context, recently introduced techniques based on sparse recovery and on compressive sensing are able to substantially lessen the curse of dimensionality, thus enabling the effective approximation of high-dimensional functions from small datasets. We will illustrate rigorous error estimates for these approaches by focusing, in particular, on their robustness to unknown errors corrupting the data. Finally, we will demonstrate their effectiveness through numerical experiments and present some open challenges in the field.