Deterministic sampling of sparse trigonometric polynomials

DOI10.1016/J.JCO.2011.01.007zbMATH Open1216.65012arXiv1006.2221OpenAlexW2963868272MaRDI QIDQ2431334FDOQ2431334

Authors: Zhiqiang Xu 

Publication date: 13 April 2011

Published in: Journal of Complexity (Search for Journal in Brave)

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 $$ is a prime number greater than $(MlogD{)}^2$. This result is almost optimal within the $(logD{)}^2$ factor. The simulations show that the deterministic sampling can offer reconstruction performance similar to the random sampling.

Full work available at URL: https://arxiv.org/abs/1006.2221

Recommendations

• Random sampling of sparse trigonometric polynomials
• Random Sampling of Multivariate Trigonometric Polynomials
• Stability Results for Random Sampling of Sparse Trigonometric Polynomials
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials

zbMATH Keywords

compressed sensingWeil sumdeterministic samplingsparse trigonometric polynomials

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical methods for trigonometric approximation and interpolation (65T40) Trigonometric polynomials, inequalities, extremal problems (42A05) Sampling theory in information and communication theory (94A20)

Cites Work

• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Gabor analysis and algorithms. Theory and applications
• On Some Exponential Sums
• Combinatorial sublinear-time Fourier algorithms
• Grassmannian frames with applications to coding and communication
• Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery
• Deterministic constructions of compressed sensing matrices
• Lower bounds on the maximum cross correlation of signals (Corresp.)
• Explicit constructions of RIP matrices and related problems
• Title not available (Why is that?)
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• On the impossibility of uniform sparse reconstruction using greedy methods
• Random sampling of sparse trigonometric polynomials
• Bounds on crosscorrelation and autocorrelation of sequences (Corresp.)

Cited In (11)

• Signal recovery under cumulative coherence
• Stability Results for Random Sampling of Sparse Trigonometric Polynomials
• Weighted random sampling and reconstruction in general multivariate trigonometric polynomial spaces
• A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials
• Robust recovery of signals with partially known support information using weighted BPDN
• Random sampling of sparse trigonometric polynomials
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• Stochastic Collocation vial₁-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification
• The recovery guarantee for orthogonal matching pursuit method to reconstruct sparse polynomials
• Random Sampling of Multivariate Trigonometric Polynomials
• Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials

Uses Software

• CVX

This page was built for publication: Deterministic sampling of sparse trigonometric polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431334)