Deterministic Sampling of Sparse Trigonometric Polynomials

Abstract

One can recover sparse multivariate trigonometric polynomials from 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 $# X$ is a prime number greater than $(M\log D{)}^2$. This result is almost optimal within the $(\log D{)}^2$ factor. The simulations show that the deterministic sampling can offer reconstruction performance similar to the random sampling.

9 pages

References in corpus (3)

• Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property
• The statistical restricted isometry property and the Wigner semicircle distribution of incoherent dictionaries
• Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms

Cited by in corpus (4)

• Universal Spatiotemporal Sampling Sets for Discrete Spatially Invariant Evolution Systems
• On sparse interpolation and the design of deterministic interpolation points
• Deterministic Compressed Sensing Matrices from Additive Character Sequences
• Deterministic Compressed Sensing Matrices from Multiplicative Character Sequences