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 MM-sparse multivariate trigonometric polynomial with fixed degree and of length DD from the determinant sampling XX, using the orthogonal matching pursuit, and with |X||X| a prime number greater than (MlogD)2(MlogD)2. This result is optimal within the (logD)2(logD)2 factor. The simulations show that the deterministic sampling can offer reconstruction performance similar to the random sampling.