Deterministic sampling of sparse trigonometric polynomials

One can recover sparse multivariate trigonometric polynomials from a few randomly taken samples with high probability (as shown by Kunis and Rauhut). We give a deterministic sampling of multivariate trigonometric polynomials inspired by Weil's exponential sum. Our sampling can produce a deterministic matrix satisfying the statistical restricted isometry property, and also nearly optimal Grassmannian frames. We show that one can exactly reconstruct every M-sparse multivariate trigonometric polynomial with fixed degree and of length D from the determinant sampling X, using the orthogonal matching pursuit, and with vertical bar X vertical bar a prime number greater than (M log D)(2). This result is optimal within the (log D)(2) factor. The simulations show that the deterministic sampling can offer reconstruction performance similar to the random sampling. (C) 2011 Elsevier Inc. All rights reserved.