Simone Brugiapaglia, Clayton Webster and I have written a chapter that surveys recent trends in high-dimensional approximation using the theory and techniques of compressed sensing:
Polynomial approximation of high-dimensional functions via compressed sensing
In it we demonstrate how the structured sparsity of polynomial coefficients of high-dimensional functions can be exploited via weighted l1 minimization techniques. This yields approximation algorithms whose sample complexities are essentially independent of the dimension d. Hence the curse of dimensionality is mitigated to a significant extent.