Random sampling of sparse trigonometric polynomials

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 ℓ1-minimization. In contrast to their work, where the sampling points are restricted to a grid, we model the random sampling points by a continuous uniform distribution on the cube, i.e., we allow them to have arbitrary position. Numerical experiments show that with high probability 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. We present two theorems that explain this observation. One of them provides the analogue of the result of Candes, Romberg and Tao. The other one is a result toward an average case analysis and, unexpectedly connects to an interesting combinatorial problem concerning set partitions, which seemingly has not yet been considered before. Although our proofs follow ideas of Candes et al. they are simpler.