Deterministic sampling of sparse trigonometric polynomials

DOI10.1016/J.JCO.2011.01.007MaRDI QIDQ2431334zbMATHOpenAlexFDO

Authors Zhiqiang Xu

Publication date 13 April 2011

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

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

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)

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.

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

Cites work

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

Cited in

(11)

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

Describes a project that uses

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)