  We analyze the convergence of compressive sensing based sampling techniques
for the efficient evaluation of functionals of solutions for a class of
high-dimensional, affine-parametric, linear operator equations which depend on
possibly infinitely many parameters. The proposed algorithms are based on
so-called "non-intrusive" sampling of the high-dimensional parameter space,
reminiscent of Monte-Carlo sampling. In contrast to Monte-Carlo, however, a
functional of the parametric solution is then computed via compressive sensing
methods from samples of functionals of the solution. A key ingredient in our
analysis of independent interest consists in a generalization of recent results
on the approximate sparsity of generalized polynomial chaos representations
(gpc) of the parametric solution families, in terms of the gpc series with
respect to tensorized Chebyshev polynomials. In particular, we establish
sufficient conditions on the parametric inputs to the parametric operator
equation such that the Chebyshev coefficients of the gpc expansion are
contained in certain weighted $\ell_p$-spaces for $0<p\leq 1$. Based on this we
show that reconstructions of the parametric solutions computed from the sampled
problems converge, with high probability, at the $L_2$, resp. $L_\infty$
convergence rates afforded by best $s$-term approximations of the parametric
solution up to logarithmic factors.
