  We study the problem of reconstructing a multivariate trigonometric
polynomial having only few non-zero coefficients from few random samples.
Inspired by recent work of Candes, Romberg and Tao we propose to recover the
polynomial by Basis Pursuit, i.e., by $\ell^1$-minimization. Numerical
experiments show that in many cases the trigonometric polynomial can be
recovered exactly provided the number $N$ of samples is high enough compared to
the ``sparsity'' -- the number of non-vanishing coefficients. However, $N$ can
be chosen small compared to the assumed maximal degree of the trigonometric
polynomial. Hence, the proposed scheme may overcome the Nyquist rate. We
present two theorems that explain this observation. Unexpectly, they establish
a connection to an interesting combinatorial problem concerning set partitions,
which seemingly has not yet been considered before.
